="Warren Smith" <warren.wds@gmail.com> a randomness property of the Marsaglia type of pseudorandom number generator
Apologies for a sideways rant, but this thread keeps picking at a pet peeve: First let me say that I don't want to disparage anyone's interest in the number theory or various PRNGs for their own sake--that can be fascinating and illuminating. Nor do I claim that there are no other interesting applications for them, say in some kind of complexity analysis or proof. However I've long felt Don Knuth did the world a well-meaning disservice with his extensive and scholarly--but highly distracting--analysis of the linear congruential generator in TAoCP. Such tiny-footprint methods were of course of practical interest in the "classic" computing era where we'd dare only use a few registers, but as soon as even relatively small tables are an option I think such methods are at best irrelevant. Ironically, Knuth in that same chapter gives brief descriptions (in his Algorithms "A" and "M") of a basis for what I believe is a much better and more straightforward (and therefore perhaps too pedestrian) generator. I will describe this briefly for those interested in such arcana:
="Joerg Arndt" <arndt@jjj.de> This rings the "shift register sequences"-bell for me.
The key idea (which Bill Gosper brought to my notice) is to use one of these well-studied shift register generators, but operate on a vector of entire words, rather than a vector of single bits (basically Knuth's Algorithm A). That is, X_n+1 = sum of some earlier X_n-k for some fixed set of k chosen by the usual primitive polynomial criteria. The LSBs of the outputs then follows an exact bitwise shift register sequence, and the more significant bits try to, but are increasingly perturbed by the "chaotic" carries bubbling up from below. The X table is initialized with arbitrary junk. (Heh. For example, I have used the ASCII for a copyright notice, arguably enhancing the IP protection of the object code). A few dozen words should be plenty (but on today's platforms you could easily make it big enough to store an entire EULA). Xn is easy to compute (no multiplies), hard to invert, and obviously has monstrously long period. However the output sequence X_n admittedly DOES still have SOME detectable patterns and "auto correlations" (eg the LSBs). So to be "extra EXTRA random" we can scramble and mangle it as follows (a variation on Knuth's Algorithm M): Make another table Y also initialized with junk. Use the previous algorithm to generate pairs X and X'. Use X to pick an index into Y in the usual way, call it k. Then increment Y_k by X', store that back and output it. Knuth notes that this downstream process can make even lame generators (eg Fibonacci) viable. Note that there's no feedback, so it can't get hung up on a pathological fixpoint. Given that the upstream generator is already excellent this is going to produce an essentially endless source of super hi-fi noise. And it's easy to code and cheap to run. There may be plenty of interesting number theory to explore around other generators, but as a practical matter I claim this recipe makes PRNGs pretty much a solved problem.