create a random sequence, skip to any part of the sequence

Question

Hi everyone,

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

Lets say, I want to store this pseudo random sequence by remembering this seed value.

Furthermore, let's say I want the 100 thousandth number in this pseudo random sequence later.

One way, would be to supply the seed number using srand(), and then calling random() 100 thousand times, and remembering this number.

Is there a better way of skipping all 99,999 other numbers in the pseudo random list and directly getting the 100 thousandth number in the list.

thanks,

m

Answer 1

If you always want the 100,000th item, just store it for later.

Or you could gen the sequence and store that... and query for the particular element by index later.

Answer 2

I'm not sure there's a defined standard for implementing rand on any platform; however, picking this one from the GNU Scientific Library:

— Generator: gsl_rng_rand

This is the BSD rand generator. Its sequence is

x_n+1 = (a x_n + c) mod m

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

So to "know" x_n requires you to know x_n-1. Unless there's some obvious pattern I'm missing, you can't jump to a value without computing all the values before it. (But that's not necessarily the case for every rand implementation.)

If we start with 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

It gets out of hand pretty quickly. Is that function easily reducible? I don't think it is.

_{(There's a statistics phrase for a series where xn depends on xn-1 -- can anyone remind me what that word is?)}

Answer 3

If they're available on your system, you can use rand_r instead of rand & srand, or use initstate and setstate with random. rand_r takes an unsigned * as an argument, where it stores its state. After calling rand_r numerous times, save the value of this unsigned integer and use it as the starting value the next time.

For random(), use initstate rather than srandom. Save the contents of the state buffer for any state that you want to restore. To restore a state, fill a buffer with and call setstate. If a buffer is already the current state buffer, you can skip the call to setstate.

Answer 4

This is developed from @Mark's answer using the BSD rand() function.

rand1() computes the nth random number, starting at seed, by stepping through n times.

rand2() computes the same using a shortcut. It can step up to 2^24-1 steps in one go. Internally it requires only 24 steps.

If the BSD random number generator is good enough for you then this will suffice:

#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));
}

It's not hard to adapt to any linear congruential generator. I computed the tables in a language with a proper integer type (Haskell), but I could have computed them another way in C using only a few lines more code.