Random Numbers
		Home « Hobbies « Random Numbers

Preamble

The subjects of randomness, random numbers and random number generation are so large that it's impossible for me to explore them fully in this hobby page. I hope to present some anecdotes and light theory that might be of interest to hobby mathematicians and programmers. Follow the links to explore more technical information.

History

My interest in randomness and random numbers started sometime back in early high-school when we were introduced to elementary statistics and probability theory. We studied simple systems like roulette wheels and tumbling dice, then permutations and combinations, then normal distribution, correlation, etc. The word random used to occur often in the lessons, but a detailed discussion of exactly what "random" meant never occurred. At about the same time in physics classes we were learning about the randomness in radioactive decay, turbulence and other natural phenomena (this was before chaos theory was well known). We would apply our probability knowledge to random events, but once again, the deep meaning of random wasn't discussed. I was amused to occasionally see list of random numbers in printed mathematical tables (see the pop-up image), and I wondered how they were generated (I had this image in my head of hundreds of monkeys throwing dice or hammering away at typewriters).

Random Numbers Table Click to enlarge

It turns out of course that good random numbers are vital in many areas of research for modelling and simulation, and.exactly what good means in this case I'll come back to later. With the arrival of the computer age, printed tables of random number could be thrown aside and seemingly endless streams of pseudo-random numbers could be generated on computers using quite simple algorithms. The prefix "pseudo" is important here because deterministic computers cannot produce true randomness (ignorning computer peripherals that tap randomness from some natural source like the wind or background radio noise and make it available to software). It turns out though that computers using some modern well-crafted algorithms can generate incredibly long random number sequences of astonishing fidelity that are indistinguishable from real randomness.

One of the first beginner student programs I wrote in 1973 using the Minitran (miniature Fortran) language generated random numbers using the built-in RAND function and plotted them as asterisks on the 15x11 inch fan-fold paper. In 1992, the very first C program I wrote with Microsoft C/C++ 7 under DOS 5.0 generated random coloured pixels on the screen. A few months later, the first Windows program I wrote with the Microsoft SDK 3.1 filled the window client area with random lines. My first Windows screen saver filled the screen with customisable random shapes and colours. This old screen saver was modernised over the years and is still working under Windows XP when compiled with Visual Studio .NET. The C++ screen saver source and project are available for download (see links below). The first Java applet I wrote in early 1996 was the one at the bottom of this page that mimics the workings of my screen saver in miniature. It seems that every "hello world" program I have written in the last 30 years when learning a new programming language seems to play with random numbers.

L'Ecuyer's 1988 MLCG

The most popular algorithm for generating random numbers on computers is the MLCG (Multplicative Linear Congruential Generator). Starting with a seed value S₀ the following formula is iterated:

All MLCGs must eventually cycle back to the seed value, but if a and m are chosen carefully so that m is prime and a is a primitive root modulo m then you get a maximal generator with period m - 1. In his 1988 article Efficient and Portable Combined Random Number Generators, Pierre L'Ecuyer exposes the poor quality of simple 32-bit MLCGs, finds the best ones possible and then combines them to produce a generator with a period of length 2.3 x 10¹⁸. The new combined generator is subjected to a battery of statistical tests and passes them all to prove that it's a good quality random number generator. Even more impressive, the code for the combined generator is tiny and can be coded in minutes. Anyone who wants a simple and effective random number generator that is far superior to those supplied with standard libraries should consider using the following skeleton C code instead to generate random uniform variables in the range [0,1].

float Uniform()
{
  int z,k;
  k = s1 / 53668;
  s1 = 40014 * (s1 - k * 53668) - k * 12211;
  if (s1 < 0) s1 = s1 + 2147483563;
  k = s2 / 52774;
  s2 = 40692 * (s2 - k * 52774) - k * 3791;
  if (s2 < 0) s2 = s2 + 2147483399;
  z = s1 - s2;
  if (z < 1) z = z + 2147483562;
  return z * 4.65661305956E-10;
}

This algorithm is quite old now, but it's very brief and reliable. This is the one to use if you're in a hurry and want random numbers that are probably far superior to the ones generated by you compiler's library routines. The next section demonstates this.

May 2007 Note: The Numerical Recipies in C book implements the algorithm above, but adds a Bayes-Durham shuffle to remove any possible bit correlations. The code is only slightly more complicated, but they claim that the improved algorithm is practically perfect. C# source code HERE, translated from the original C code.

Comparing MLCGs

As a programming exercise I used Mathematica to plot the structure of four MLCGs:

1. A good MLCG.
2. The standard C runtime rand() function.
3. L'Ecuyer's combined MLC.
4. The Visual Basic Rnd function.

Following L'Ecuyer's technique in his 1988 paper, random pairs were generated in the unit square until 1000 were collected in a strip 0.001 wide. This strip was then stretched out to show any lattice structure in the generated sequential value pairs. The following images show the results of the plots. I have taken this plotting idea further and created a general purpose Windows application that plots the lattice structure of many famous types of random number generators (see Downloads below).

L'Ecuyer Updates

In 2000 I found that Pierre L'Ecuyer had a web site. I emailed him to ask if there were updates to the 1988 article and if there were 64-bit code versions suitable for the Java language. He replied and told me to look at Pierre L'Ecuyer's publications. Amongst the links in the page are code samples that combine MRGs (Multiple Recursive Generators) for 32-bit and 64-bit integer operations as well as for 48-bit integers in floating-point. The new generators produce sequences with astonishing period lengths that easily pass all known statistical tests of randomness. Sample code and notebooks can be found below under Downloads and technical details can be found under Links.

Mersenne Twister

In late 2004 I was shocked to discover that a whole new class of random number generator existed that I had not heard of, even through it had been published for about 5 years. This new algorithm called Mersenne Twister (MT) is a linear-feedback shift register with a very large period and excellent statistical properties in 623 dimensions.

This generator is so good that it crushes the previous ones I have described into insignificance. Rather than discuss MT here, I'll simply supply a few links to articles which in turn lead further into technical discussions of MT.

I used to have some links here to the home page of Makoto Matsumoto and Takuji Nishimura, and to John Savard's cryptographic compendium page, but they have both vanished from their original URLs and can't quickly be found at new locations. In the meantime I recommend sticking any of the keyworks and surnames mentioned into a web search engine to find out more about the Mersenne Twister.

Quick and Dirty

This small section was added on 19-May-2007 to describe how impressed I am with the "quick and dirty" random number generator described in the book Numerical Recipies in C. At the end of chapter 7 they suggest the following one-liner based upon the fact that if you multiply two 32-bit unsigned integers then the result is the low 32-bits of the full product:

uint idnum = [some 32-bit seed]
: // C# sample code
idum = 1664525u * idum + 1013904223u;

Despite the simplicity, this generator is amazing good. Download the randplot application below and compare the output of the "minimal" MLCG with the code. The following thumbnails from randplot show the difference in distribution.

Minimal MLCG

Quick and Dirty

If you need a really simple but effective bit of code to "shuffle things up" without the overkill need for high-quality random numbers, then you can't go past the Quick and Dirty generator.

Downloads

Newer Downloads (May 2007)

	randplot_proj.zip - (40KB) A complete Visual Studio 2005 project containing a forms application that plots the lattice structure of a variety of RNG algorithms. See the description on the randplot page. Code to generate random numbers using all famous generators is supplied in the C# source code.
	randplot_exe.zip - (54KB) A zip of the executable files for randplot.

Downloads (December 2004)

	RandEcuyer.cs - C# class that implements the raw L'Ecuyer's 1988 MLCG and his later CMRG with 2 components of order 3.
	RandMT.cs - C# class that implements the Mersenne Twister 19937. This file is a part of the Nancy Street utility library which is available for download on the csutylib page. An NUnit test verifies the MT19937 code is working to specification.

Old Downloads

	UtilsRand.java - Java source for 64-bit CMRG with 2 components of order 3. The period length is about 10^113.
	rand.cpp - C++ source for 32-bit CMRG with 2 components of order 5. The period length is about 10^96.
	rand.h - Header file for rand.cpp.
	randplot.nb - Mathematica notebook to generate the four random "slice" plots above.
	Web page about Greg's random Screen Saver, with downloads.

Links

• Pierre L'Ecuyer's publications
• Using and Creating Cryptographic-Quality Random Numbers
• THE WWW VIRTUAL LIBRARY:
  RANDOM NUMBERS and MONTE CARLO METHODS
• Random Number Generators

Random Fun Java Applet

Here is the first Java applet I wrote in early 1996 to generate various types of randomly coloured images that flash or walk across the screen in different ways. In this code I use L'Ecuyer's 1988 algorithm. Click the button to Stop/Start the animation. Select the animation image type from the first drop-down list. Select the animation speed from the second drop-down list. Click the Smooth box to perform a random walk through the colour palette for each animation step, otherwise random colours are used. The Netscape check box might need to be ticked for Netscape V4 browsers if the colours occasionally all turn black due to resource exhaustion. TIP: The Trigonometric + Smooth option is quite hypnotic.

Source: randfun.java, randcnvs.java

Please note that I do not write production Java code like this
sample. In real life I use proper variable names, neat structured
code and I always include comprehensive Javadoc comments.

Technical Notes:

• The random rectangles and ellipses are constrained to be a nice size with a width and height that is between 10-60% of the dimensions of the enclosing applet window.
• The random polygons have from 3-8 randomly positioned vertices.
• The trigonometric randomiser draws lines between two independent curves that are calculated from sums of Sin and Cos of rationals (more details coming soon...).