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

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?)}

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.

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.

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.