RANDU is an infamous linear congruential

Linear congruential generator

A Linear Congruential Generator represents one of the oldest and best-known pseudorandom number generator algorithms. The theory behind them is easy to understand, and they are easily implemented and fast....

 pseudorandom number generator

Pseudorandom number generator

A pseudorandom number generator , also known as a deterministic random bit generator , is an algorithm for generating a sequence of numbers that approximates the properties of random numbers...

 of the Park–Miller type

Park–Miller random number generator

The Lehmer random number generator , sometimes also referred to as the Park–Miller random number generator , is a variant of linear congruential generator that operates in multiplicative group of integers modulo n...

, which has been used since the 1960s. It is defined by the recurrence

Recursion

Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...

:

with odd

Even and odd numbers

In mathematics, the parity of an object states whether it is even or odd.This concept begins with integers. An even number is an integer that is "evenly divisible" by 2, i.e., divisible by 2 without remainder; an odd number is an integer that is not evenly divisible by 2...

. It generates pseudorandom integers  in the interval that in practical applications are often mapped into pseudorandom rationals

Rational number

In mathematics, a rational number is any number that can be expressed as the quotient or fraction a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer is a rational number...

  in the interval (0,1) by the formula:

It is widely considered to be one of the most ill-conceived random number generators designed. Notably, it fails the spectral test badly for dimensions greater than 2, and every result is odd.

The reason for choosing these particular values is that with a 32 bit integer word size the arithmetic of mod and calculations could be done quickly. To show the problem with these values consider the following calculation where every term should be taken mod , we start by writing the recursive relation as:


which becomes, after expanding the quadratic factor:

because mod

and allows us to show the enormous correlation between three points as:


As a result of this correlation, the points in three dimensional space (mod ) fall in a comparatively small number of planes, 15 to be exact. As a result of the wide use of RANDU in the early '70s, many results from that time are seen as suspicious.

This misbehavior was already detected in 1963 [ ref. 7 of http://portal.acm.org/citation.cfm?id=363827 ] on a 36-bit computer, and carefully reimplemented on the 32-bit IBM360.

Sample output

The start and end of the RANDU’s output period for the initial seed is:

1, 65539, 393225, 1769499, 7077969, 26542323, …, 2141591611, 388843697, 238606867, 79531577, 477211307, 1

Quotations