Uniform random numbers

Random numbers are used extensively in modern computing, for example they are used in testing programs, simulations, cryptology and in randomized algorithms like randomized primality testing.

True randomness on a computing machine is impossible, because the numbers are generated by an algorithm, but it is sufficient to produce numbers that appear to be random, these are called pseudo random numbers, they satisfy many of the properties of true random numbers. Algorithms used to generate random numbers are called pseudo random number generators (PRNG). To be sure that the numbers are "random enough", they must pass some statistical tests.

Uniformly distributed random numbers
A uniformly distributed random sequence A₁, A₂, ..., A_m generated from X₁, X₂, ..., X_n satisfies:

1. A_i is equally likely to be X₁, X₂, ..., X_n, i = 1, 2, ..., m.
2. The average of the generated numbers is (∑_{i = 1} A_i)/ m.

After generating n numbers, the previous two properties hold, more stronger properties do not:

1. The sum of any two consecutive numbers is equally likely to be even or odd.
2. When n numbers are generated, there should be duplicates in the sequence.

Unfortunately, the number of times the sum of two consecutive integers is even is always more than the number of times the sum is odd, and the sequence is duplicate free. All pseudo random number generators fail some statistical tests.

The simplest uniform generator: Linear Congruential Generator
This generator was first introduced in 1951, it is a pseudo random number generator, the generated sequence X₁, X₂, ..., X_n satisfies:

X_i+1 = A[X_i (mod M)]

The (i+1)th number is generated by multiplying its previous number by a constant

A and computing the remainder of the division of the result be another constant M. It is easy to see that all of the generated numbers are less than M. To start generating the numbers, we must start with an initial value called the seed, say X₀, but take care that if X₀ = 0 then, you have a sequence of zeroes (which is not random).

If M is prime
Notice that if M is prime, then no zeroes are generated because, primes have no non-trivial divisors, let M = 7, A = 5 and X₀ = 1, the first 8 numbers are:
5, 25, 20, 30, 10, 15, 5, 25, ...

value Notice that the sequence is repeated after 6 (which is M - 1) numbers are generated, this is called the period of the sequence, the choice of A matters, not all values of A will generated a full-period sequence, but several choices of A are valid. A full-period is achieved of all the non-zero integers less than M are generated.

To generate a long sequence with a full-period, choose M to be a large prime, very popular choice of A and A are 2³¹ - 1 and 48,271.

Overflow problem
If we use 32-bit integers in our computation, overflow will occur after a sufficient number of values are generated, so, we would no longer be sure if a full-period is achieved. A solution to this problem is to use 64-bit integers (called long in Java), but this is inefficient computationally, a slight change in the main equation helps us overcome the overflow problem:

X_i+1 = A[X_i (mod ℑ)] - ℜ⌊X_i / ℑ⌋ + Mδ(X_i)

Where ℑ and ℜ are the quotient and the remainder of M / A.

• δ(X_i) = 0, if A[X_i (mod ℑ)] - ℜ⌊X_i/ℑ⌋ ≥ 0
• δ(X_i) = 0, if A[X_i (mod ℑ)] - ℜ⌊X_i/ℑ⌋ ≤ 0

When the difference between the first two terms is less than zero, then δ(X_i) is defined to be 1, and when the difference is greater than 0, δ(X_i) is defined to be 0.

Pseudo code
M ← 19
A ← 5
ℑ ← ⌊M/A⌋
ℜ ← M (mod A)
for i = 1 to i = n step 1
begin

• X_i ← A×[X_i-1 (mod ℑ)] - ℜ×⌊X_i-1/ℑ⌋
• if X_i ≤ 0 then X_i ← X_i + M

end

References

1. Data Structures & Problem Solving Using Java (1998).
2. Wikipedia.