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

3
votes

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

4
mathrandomsrand
Note that srand seeds rand, and srandom seeds random. – outis
I'd be interesting in knowing the use case behind this - I think I'm missing something, as I can't see why the 100,000th sequence is more random than the first. – HorusKol
@HorusKol It's been a while, but ending up here via google when interested in something related, I do feel like giving you a use case. Imagine a game that gives you a series of puzzles, each generated from a single number. To make sure that each person gets different puzzles, you use a random generator and you remember the initial seed. Now, you may want the user be able to continue where he left (at which time the seed is known, which makes things easier) or even to replay any puzzle as long as he remembers its number. – Jasper
(Yes, I had to stretch it a little to get a complete use case. However, the idea is that it isn't about "more random" but about "recreating" something "random" (thus actually turning the pseudo-part of the randomness into an advantage) – Jasper

4 Answers

2
votes

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

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

with a = 1103515245, c = 12345 and m = 231. The seed specifies the initial value, x1. The period of this generator is 231, and it uses 1 word of storage per generator.

So to "know" xn requires you to know xn-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 x1...

  • x2 = (a * x1 + c) % m
  • x3 = (a * ((a * x1 + c) % m) + c) % m
  • x4 = (a * ((a * ((a * x1 + c) % m) + c) % m) + c) % m
  • x5 = (a * (a * ((a * ((a * x1 + 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?)

1
votes

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.

1
votes

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.

0
votes

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.