Jumping in at random... which I guess is appropriate in this case...

From: Marc LeBrun <mlb@well.com>

...

="J.P. Grossman" <jpg@alum.mit.edu> There's a good paper on parallel random number generation here: http://www.thesalmons.org/john/random123/papers/random123sc11.pdf

Very interesting, thanks for the link! I will plan to read it more carefully, but already I'm intrigued that one of the authors is *that* David Elliot Shaw: http://en.wikipedia.org/wiki/David_E._Shaw Small valley! ...

I don't know yet how this compares to what's in the cited paper, but another thing Bill Gosper noted about the word-vector shift-register upstream (Algorithm A) part of generator I described is that each step is effectively a multiplication of the vector by a sparse 01 matrix whose non-zero entries are simply the coefficients of the primitive polynomial (or the feedback taps in the delay line, to use signal-processing lingo).

Thus one can jump n steps simply by multiplying by the n-th power of that matrix instead.

Done that part! ...

Of course the downstream (Algorithm M) part is specifically intended to mess up even this vestigial "autocorrelation".

Not that part. Anyway, I have on and off thought about the problem of random-access randomness for virtual worlds. This is probably a separate problem from the parallel-generation problem unless that includes nodes being recruited in an unpredictable, local-communication, spreading way. In the virtual world or unpredictable spreading case one would like (I think) unlimited, repeatable drill-down without weakening the randomness. An obvious but wrong approach is to treat nodes in a tree as seeds for their subtrees, but this has a kind of fixed-point problem. It would shrink the space of seeds at every downward step. The last I was thinking about this, the solution seemed to be to take a strong hash (like maybe one of the SHA's) of the full path from the root. So thanks J.P., Marc, and Joerg, I will read the paper. --Steve