I wrote an article titled “Lightweight Random Number Generation” in the August 2016 issue of Microsoft MSDN Magazine. See https://msdn.microsoft.com/magazine/mt767700.

In the article I describe four different algorithms to generate random-appearing integers. The Linear Congruential algorithm expressed symbolically is:

X(i) = [a * X(i-1) + c] % m

In words, “the next random number is the current random number times a constant a, plus a constant c, modulo a constant m.” There are three questions. First, what values of a, c, and m should you use? Second, how do you get started? Third, how can you prevent arithmetic overflow when a and X(i-1) are large?

The Lehmer algorithm, also known as the Park-Miller algorithm, is a simplified version of Linear Congruential:

X(i) = [a * X(i-1)] % m

The Wichmann-Hill algorithm basically uses Linear Congruential three times, then combines the three new numbers into a final new result number.

The Lagged Fibonacci algorithm is:

X(i) = [X(i-7) + X(i-10)] % m

In words, the new random number is the random number generated 7 times ago, plus the random number generated 10 times ago, modulo some large value m.

Generating random numbers looks pretty simple, but it’s some of the trickiest code in all of computer science.