	Source Code and Discussion of Newer & Better Portable Random Number Generators		REFERENCES
		index
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:
http://random.mat.sbg.ac.at/ "Random number generators -- The pLab Project Home Page"
http://homepages.cwi.nl/~paulv/ "PRNG's and Kolmogorov Complexity"
http://www.taygeta.com/random.html "Random Number Generation, Taygeta Scientific Inc."
http://www.agner.org/random/ "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.

AES
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, www.counterpane.com, 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):
http://web.archive.org/web/20030426143419/http://www.rocksoft.com/rocksoft/papers.shtml "Rocksoft Guide to CRCs"
http://www.oonumerics.org/ "The Object-Oriented Numerics Page"
http://www.7stones.com/ "7Stones (Heavy Math)"
http://www.llnl.gov/ "Lawrence Livermore National Laboratory"
http://chrishecker.com/ "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)

RANDOM (Fortran-90 pseudo-random number generator based on normal number paper)
Unix-based systems: random.tar.gz (version date 2004-08-10)

A Fortran-90 pseudo-random number generator, based on the recently discovered class of provably normal numbers -- see paper "Random Generators and Normal Numbers", by DHB and Richard Crandall, in the papers directory. In particular, subroutine bcnrand generates a sequence of IEEE 64-bit floating-point numbers uniformly in (0,1), with period (if parameters are properly selected) = 2x3^32 = 3.7060404e15. It is completely self-contained -- the required double-double arithmetic subroutines are included in the Fortran-90 source file. The bcnrand routine is designed for simple parallelization, yielding the same overall sequence as with a one-processor program. Also included here is a memory-testing program based on the bcnrand generator.
- David H. Bailey and Richard E. Crandall, "On the Random Character of Fundamental Constant Expansions," Experimental Mathematics, vol. 10, no. 2 (Jun 2001), pg. 175-190; LBNL-45583. PDF.
- David H. Bailey and Richard E. Crandall, "Random Generators and Normal Numbers," Experimental Mathematics, vol. 11, no. 4 (2002), pg. 527-546; LBNL-46263. PDF
- David H. Bailey, "A Pseudo-Random Number Generator Based on Normal Numbers," manuscript, Dec 2004; LBNL-57489. PDF

New addition (2011)

Generate Batter Random Numbers
In C# the standard way to generate random numbers is with the System.Random class, which produces numbers that appear random, based on a seed value (often the current time). That usage is shown below:

Random rand = new Random();
Int32 randomNumber = rand.Next();

If you just need an arbitrary numbr for noncryptographic purposes, this is perfectly fine. However, if you are doing anything security related, you should never use Random. Instead, use System.Security.Cryptography.RNGCryptoServiceProvider. Here's an example:

System.Security.Cryptography.RNGCryptoServiceProvider cryptRand =
new System.Security.Cryptography.RNGCryptoServiceProvider();
byte[] bytes = new byte[4];
cryptRand.GetBytes(byte);
Int32 number = BitConverter.ToInt32(bytes, 0);

Note: Both methods of generating random numbers are actually pseudorandom (that is, not truly random). Pseudorandom numbers are based on some seed, or known data. System.Random usees a seed value (often the current time), and RNGCryptoServiceProvider uses a combination of processor info, operating system counters, cycle counters, time, and other information to generate cryptographically secure bytes. True randomness can generally be achieved only through more complicated phenomena (static noise, mouse movement, network traffic patterns, and so on).

—Ben Watson C# 4.0 How-To: Real Solutions for C# 4.0 Programmers (2010)

index

Back to Deley's Homepage

Links for Further Research

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

New addition (2011)

index

Back to Deley's Homepage