Source Code and Discussion of Newer & Better Portable Random Number Generators REFERENCES
Back to Deley's Homepage

Links for Further Research

There's been further research since this paper was originally written in 1991, most of which I haven't kept up with. An excellent overview of changes is at the beginning of Chapter 7 in the latest edition of the Numerical Recipies book.

My thanks to Reid Sweatman for providing the following comments and links.

A couple of more recent PRNGs, such as, say, the Mersenne Twister or R250. Their power distribution characteristics and behavior in the low-order bits is vastly better than any linear-congruential generator, or Riemann-Zeta-based generator. The Twister also has the virtue of being quite fast. I've written 3D weather simulations where no linear-congruential generator, even coupled with all the tricks for suppressing short-term periodicity in certain bit patterns, was sufficiently well-behaved to prevent very obvious visual artifacting. At the time, I switched to R250 (which is, admittedly, slow, but which still handled the fairly dense particle system I was using), and the artifacts vanished.

One other possible problem you could mention is that when you scale floating-point numbers to fit a range, you can mess up the power distribution for certain values due to how the processor normalizes such numbers, the amount of precision available, and the fact that the numbers expressible as floats are not only not topologically dense within the reals for your range, but aren't even linearly distributed. I suppose a final bit of completeness would point out that it's possible to apply a perfectly uniform generator to a problem space in a way that introduces non-linearities. The classic example of that I've seen (quite frequently in game programming, actually) is to try to get a uniform distribution of points in a spherical volume by applying a uniform generator to a bounding cube, then tossing out-of-range values. Computationally much cheaper, but if, for instance, you're computing fog values, or particle placement, you end up with "thin" lines of sight from the center through the vertices of the bounding box. This can be quite visually obvious. The place where non-uniformity can really be important is in generating key schedules for encryption algorithms; the rand() problem you mention was how the 40-bit RSA in Netscape was originally broken, as it reduced the size of the keyspace by several binary orders of magnitude.

Some sites you might look at on PRNGs: "Random number generators -- The pLab Project Home Page" "PRNG's and Kolmogorov Complexity" "Random Number Generation, Taygeta Scientific Inc." "Pseudo random number generators"

I'm sure there are newer sites, as these are ones I archived when I wrote my PRNG modules I use for most everything. Knuth has lots of material on PRNGs, but it's mostly linear congruential stuff, which he analyzes to death.

Bruce Schneier has some material on his site, which I list below, because PRNGs are of critical importance to encryption algorithms (read his Yarrow-160 whitepaper; the implementation has problems, but the theory is fascinating). And Vegas gambling machines; I once almost took a position writing code for slot machines. They had to have someone who really understood how the things worked, and all the myriad ways implementation errors could mess up their distribution properties (hey, that's exactly how the 40-bit RSA encryption in Netscape was broken around 1996). You really don't want to run foul of the Las Vegas Gaming Commission.

Probably the best intro source on AES is Bruce Schneier's "Applied Cryptography," 2nd ed. The AES was formalized after it went to print, but it's in there under it's original name, Rijndal (and I likely mis-spelled that). There's considerably more discussion on the various algorithms that competed for AES on Schneier's website,, since he had an entry in it himself (which I personally think should have won), called TwoFish.

Some other sites somewhat related to this material (mostly numeric kinds of stuff): "Rocksoft Guide to CRCs" "The Object-Oriented Numerics Page" "7Stones (Heavy Math)" "Lawrence Livermore National Laboratory" "Chris Hecker's Home Page"
I don't know if Chris' page is still reachable, but there used to be some really meaty stuff there, mostly physics. Continuum dynamics, integration techniques for systems of differential equations, tensor analysis, calculus of variations, you know, the fun stuff. Chris has a sort of god-like status among game coders.

—Reid Sweatman

New addition (2007. I haven't studied this closely)

New addition (2011)

Other Links:
Source Code and Discussion of Newer & Better Portable Random Number Generators REFERENCES
Back to Deley's Homepage