jumping ahead in sequence of random numbers


rd1971
11-20-2008, 08:58 AM
Hi,

I'm looking for some recommendation with regard to a pseudo random number generator which permit (fast) jumps to the nth draw in a sequence.

I've tried one from L'Ecuyer (streams/substreams c++ paper, circa 2001) which seems to work very nicely but is a little slow when compared to what I'm trying to replace (Marsaglia/KISS).

I'm aware of the gray code shifting technique applicable to sobol sequences, but I'm only currently considering pseudo random number generators.

I didn't notice any explicit discussion of this in NR3 (many apologies if I missed this - just give me a slap and a reference and I'll be on my way) - does anyone have any recommendations or references I could take a look at?

In my case I'd like to be able to spawn multiple threads and have the generator in each thread suitably configured to draw exactly the same numbers (overall) as I would have obtained had I done the whole calc in a single thread - if you see what I mean. For the two threaded case, I would want to offset the generator for the second thread by the exact number of draws which the first thread is configured to make.

thanks in advance,
Richard.

GravityGuy
12-05-2008, 05:18 PM
It seems to me that any pseudo-random number generator will generate the same sequence of numbers given the same starting seed value. So, why not start the same random number generator in each thread and keep track of the count of the number of times you ask for a number. You can keep them synchronized if the n count is the same.

Otherwise, you could just generate a static number of them and store them in a vector and use the index to locate the nth one. Why go to anymore trouble?

Bill Press
12-05-2008, 10:06 PM
Actually, this is in NR3, though it is a little bit obscure. Check out section 7.1.4 on random hashes. If you instantiate a Ranhash object, say by

Ranhash ran;

then you can get the nth value of a random sequence by (e.g.)

x = ran.doub(n);

You can call different n's in any order, and you'll always get the same value for the same n.

If you want mm different sequences, labeled 0 to mm-1, then the nth value of the mth sequence is

x = ran.doub(n*mm + m);

There are of course other ways to do this using the hash algorithm Ranhash.