Random Number Generators

Generating random numbers is an important task for Monte-Carlo simulations. The quality of random numbers decides over the quality of the simulation results. Bad random numbers (with “bad” defined appropriately) can produce results which are simply wrong. Therefore it is important to choose a “good” random number generator. This is not an easy task: xkcd has a comic which deals with this.

First we should be clear of what properties define a “good” random number generator (RNG), and for which field of work. As an example, RNGs for cryptographic applications must have properties that are simply irrelevant for Monte-Carlo simulation in high-performance computing.

Random number generators for Monte-Carlo simulations in the field of high-performance computing

We want the following:

We want to be able to repeat our simulations, yielding the exact same results. Therefore, we need to be able to reproduce the exact same sequence of random numbers at will. This rules out “true” random numbers, i. e., randomness produced by physical processes like thermal noise, radioactive decay, etc. Therefore, we do not want a true random number generator, but a pseudo-random number generator (PRNG).
We need lots of random numbers. Some of my simulations generated 10¹⁵ random numbers for a single run. Therefore, storing random numbers beforehand is out of the question: we need to generate them on the fly.
We need speed. If you produce 10¹⁵ random numbers, it is worth haggling over nanoseconds. As a basic rule, generating a random number should be faster than the rest of the algorithm which uses it; at least it should not be much slower, or otherwise you waste computing time on random numbers, but not on simulating.
The correlations present in your sequence of random numbers must not spoil the physics of your model. This one is really hard. Many people speak of the quality of a PRNG when referring to this property. As a rule of thumb, higher-quality generators are slower than lower-quality ones.

The simplest useful random number generator

Well, xkcd's random number generator is simpler, but it is not useful. But a useful one is not much more difficult (I present examples in Fortran 90 [1]):

ibm = 2 * seed - 1    ! Initialization
...
ibm = ibm * 16807     ! Generation of a random number

I was introduced to the generator by Prof. Stauffer. You can see his style of programming clearly (he takes the Gerling criterion very seriously [2]). Okay, let's pretty it up:

integer, save :: rnd_value

subroutine initRand(seed)
  integer, intent(in) :: seed
  rnd_value = seed
end subroutine

integer function getRand()
  rnd_value = rnd_value * 16807
  getRand = rnd_value
end function

So we blew up the number of lines of code, and hopefully the compiler reduces the more “modern” code to the same binary result as the old one.

Notes

[1] If you really take high-performance computing seriously, you must learn Fortran. In general, Fortran programs compile to more efficient code, as you can do less nasty things in Fortran than in C (aliasing arrays or other such nonsense). Furthermore, a huge body of knowledge is coded in Fortran; you want to tap it.

[2] The Gerling criterion states that published programs shouldn't contain more lines than authors have years in their lives. When growing old, you may publish long programs, but while being young, you must be concise.