Predicting outcome of rand() at 'x' iterations ahead?

[treefitty]

Hello!

I had an idea about random generation based on seeded rand(), but there is one caveat to make it work correctly (I think). I need to be able to predict rand() at any positive offset based on its seed, without actually having to call it every single time inbetween.

Let us assume that this code:

unsigned int max_iters = 5;

srand(SEEDVALUE);

for(int i = 0; i < max_iters; ++i)
{
  cout << rand() % 100 << endl;
}

assume that this code outputs the values: 59, 3, 12, 34, 95

And it would always output the same exact numbers, provided that SEEDVALUE is the same value every time you run it. This means if I change "max_iters" to 100, the very last generated number (100th, or value #99) will always be the same value, too.

This means, if I wanted to store ONLY what the first ten values, and the last ten values were (when using a certain SEEDVALUE), I could "always know" those results, provided that I actually run rand() the full 100 times. I just don't care about those 80 results in the middle, but that's fine, I'll just run rand() the first 10 times, store the first 10 values, run it 80 more times, throw away those 80 values, and run it 10 more times, and store those last 10 values. No problem, right?

But is that the only way? Forcing rand() to run every single time in the middle and ignoring the values, OR, can I somehow 'simulate' running the function, without actually calling the function? The reason I ask is this:

What if I want to know what the 24,419,019,005 th output of rand() is, when using a seed of 10? Whatever it is, it will always be the same value. If it's always the same value, is the ONLY way of doing it to literally call rand() 24,419,019,005 times, ignoring the values every time until you get to the iteration that you care about? Or is there some way I can say: Seed rand at 10, but then offset into the outputs 24,419,019,005 times -- i.e. PRETEND that I called rand that many times, and show me what that rand() result is, without actually calling it that many times.

Hope this makes sense. :(

Thank you for any advice!! :)

[keskiverto]

From man rand http://linux.die.net/man/3/rand

Example

POSIX.1-2001 gives the following example of an implementation of rand() and srand(), possibly useful when one needs the same sequence on two different machines.

    static unsigned long next = 1;

    /* RAND_MAX assumed to be 32767 */
    int myrand(void) {
        next = next * 1103515245 + 12345;
        return((unsigned)(next/65536) % 32768);
    }

    void mysrand(unsigned seed) {
        next = seed;
    }

Note though, that in http://www.cplusplus.com/reference/cstdlib/rand/

Compatibility
In C, the generation algorithm used by rand is guaranteed to only be advanced by calls to this function. In C++, this constraint is relaxed, and a library implementation is allowed to advance the generator on other circumstances (such as calls to elements of <random>).

You could populate a (huge) array once for the possible values of 'next' and then hop on that array until you reach the desired location. That has merely a different cost to calling the rand() for N times.

[treefitty]

I'm a little confused at what is happening in the example posted, but I understand what you mean about populating a list beforehand and indexing that table which would be slower on load, faster on run.

Follow up question though? is the max value that rand can output 32767? If I say rand() % 50000, will it still only ever return 0 through 32767 ?

Could I then "get around" that by using a custom rand function which calls rand twice, i.e.

srand(userseed);
int value1 = rand() % RAND_MAX;

srand(userseed + 1);
int value2 = rand() % RAND_MAX;

__int64 total = value1 + value2;

return total;


Aside from optimizations like doing that with less lines, would that be a fine way of 'getting around' that limitation of rand_max or is that somehow faulty?

[keskiverto]

RAND_MAX is library-dependent: http://www.cplusplus.com/reference/cstdlib/RAND_MAX/

The <random> has pseudo-random generators too and larger max():
http://www.cplusplus.com/reference/random/linear_congruential_engine/
minstd_rand0, minstd_rand

[JLBorges]

For leap ahead in logarithmic time, see '3.2 Leap Ahead For Linear Congruential Generator' in
http://www.cs.fsu.edu/research/projects/nirajproject.pdf

Appendix B has sample C code based on the algorithm from
Knuth's 'The Art of Computer Programming, Vol. 2: Seminumerical Algorithms'.