Create a random sequence, skip any part of the sequence

Question

On Linux There is a srand () function in which you supply the seed, and it will guarantee the same sequence of pseudorandom numbers in subsequent calls to the random () function.

Let's say I want to keep this pseudo-random sequence, remembering this value of the seed.

Also, let's say I want the 100,000th number in this pseudo-random sequence later.

One way is to specify the number of seeds using srand (), and then call random () 100 thousand times and remember this number.

Is there a better way to skip all 99,999 other numbers in a pseudo-random list and directly get the 100,000th number in the list.

thank,

t

Answer 1

I am not sure that there is a specific standard for implementation randon any platform; however, choosing this from the GNU Science Library :

- Generator: gsl_rng_rand

This is the rand BSD generator. His sequence

x _{n + 1} = (ax _n + c) mod m

with a = 1103515245, c = 12345 and m = 2 ³¹ . The segment defines the initial value, x ₁ . The period of this generator is 2 ³¹ and it uses 1 storage word per generator.

"" x _n, x _n-1. - , , , . ( rand.)

x ₁...

• x ₂= (a * x ₁ + c)% m
• x ₃= (a * ((a * x ₁ + c)% m) + c)% m
• x ₄= (a * ((a * ((a * x ₁ + c)% m) + c)% m) + c)% m
• x ₅= (a * (a * ((a * ((a * x ₁ + c)% m) + c)% m) + c )% m) + c)% m

- . ? , .

_{( , x n x n-1 - - , ?) >}

Answer 2

, rand_r rand srand, initstate setstate random. rand_r unsigned * , . rand_r .

random() initstate, srandom. , . , setstate. , setstate.

Answer 3

@Mark, BSD rand().

rand1() n- , seed, n .

rand2() . 2 ^ 24-1 . 24 .

BSD , :

#include <stdio.h>

const unsigned int m = (1<<31)-1;

unsigned int a[24] = {
    1103515245, 1117952617, 1845919505, 1339940641, 1601471041,
    187569281 , 1979738369, 387043841 , 1046979585, 1574914049,
    1073647617, 285024257 , 1710899201, 1542750209, 2011758593,
    1876033537, 1604583425, 1061683201, 2123366401, 2099249153,
    2051014657, 1954545665, 1761607681, 1375731713
};

unsigned int b[24] = {
    12345, 1406932606, 1449466924, 1293799192, 1695770928, 1680572000,
    422948032, 910563712, 519516928, 530212352, 98880512, 646551552,
    940781568, 472276992, 1749860352, 278495232, 556990464, 1113980928,
    80478208, 160956416, 321912832, 643825664, 1287651328, 427819008
};

unsigned int rand1(unsigned int seed, unsigned int n)
{
    int i;
    for (i = 0; i<n; ++i)
    {
        seed = (1103515245U*seed+12345U) & m;
    }
    return seed;
}

unsigned int rand2(unsigned int seed, unsigned int n)
{
    int i;
    for (i = 0; i<24; ++i)
    {
        if (n & (1<<i))
        {
            seed = (a[i]*seed+b[i]) & m;
        }
    }
    return seed;
}

int main()
{
    printf("%u\n", rand1 (10101, 100000));
    printf("%u\n", rand2 (10101, 100000));
}

. (Haskell), C, , .

Answer 4

If you always need the 100,000th element, just save it later.

Or you can generate a sequence and store it ... and query for a specific element by index later.