Class RandomLCG

Pseudo-random number generator using a Linear Congruential Generator (LCG).

This class is designed to give same numbers in both Java and Javascript, so that tests using this class will have the same results. In Java we use floating point double numbers to match how Javascript stores numbers.

Linear Congruential Generator (LCG)

From http://en.wikipedia.org/wiki/Linear_congruential_generator

The generator is defined by the recurrence relation:

X_{n+1} = ( a X_n + c ) mod m
Copy

where X is the sequence of pseudorandom values, and

m, 0 < m  – the 'modulus'
a, 0 < a < m – the 'multiplier'
c, 0 <= c < m – the 'increment'
X_0, 0 <= X_0 < m – the 'seed' or 'start value'
Copy

Period Length

From http://en.wikipedia.org/wiki/Linear_congruential_generator

Provided that the offset c is nonzero, the LCG will have a full period for all seed values if and only if:

c and m are relatively prime,
a - 1 is divisible by all prime factors of m,
a - 1 is a multiple of 4 if m is a multiple of 4.
Copy

These three requirements are referred to as the Hull-Dobell Theorem. While LCGs are capable of producing pseudorandom numbers which can pass formal tests for randomness, this is extremely sensitive to the choice of the parameters c, m, and a.

The numbers chosen for RandomLCG satisfy the above conditions.

m = 2 ^ 32 = 4,294,967,296
Copy

Here are the prime factors of the multiplier, a

a = 1,664,525 = 5 x 5 x 139 x 479
a - 1 = 1664524 = 2 x 2 x 71 x 5861
c = 1,013,904,223 is a prime number
Copy

Floating Point Number

The double number format allows exact representation of all integers with absolute value less than 2^53. We need to avoid making numbers larger than 2^53 to avoid loss of accuracy. Every number generated will be between 0 and m-1. The maximum number that can be made in the algorithm is (m-1)*a + c. So we have to ensure that

(m-1)*a + c < 2^53.
Copy

For the numbers chosen this works out to:

(2^32-1)*1664525 + 1013904223 = 3.5745412314269e15
Copy

This is less than 2^53 = 9.00719925474099e15, so we should stay within the range of exact integers.

Warning About Usage

The series of numbers generated by a particular instance of RandomLCG will be pseudo-random. But if you make another instance of RandomLCG with a seed that is close to the first, the two RandomLCG instances will produce a highly correlated series. For example, repeatedly calling the following will produce a pretty much linear non-random sequence because Date.now() returns the current time in milliseconds which doesn't change much between invocations.

new RandomLCG(Date.now()).nextFloat();
Copy