Linear congruential generator

PROBLEM
Generate random number from given interval. In standard Rexx we can use the RANDOM built-in function. It returns an integer chosen uniformly from the interval [Min,Max], Min>=0. In Regina Max<=100000.

ALGORITHM
A very standard technique for generating pseudorandom numbers is the use of linear congruential generators (LCG) which were first introduced D. H. Lehmer in 1948. LCGs compute the Ith integer in a pseudorandom sequence via the iterative equation

Im1=I-1;X.I=(X.Im1*A+C)//M

where multiplier A, increment C, and modulus M determine the statistical quality of the generator. If A and M are not relatively prime, the sequence probably will not be very random.

A=16807, C=0 and M=2**31-1 (M=2147483647) define a generator which has a full period and is demonstrably random. It has been exhaustively tested. The resulting sequence will be statistically indistinguishable from a sequence drawn at random from the set 1,2,...,M-1. Here 16807 and 2**31-1 are relatively prime and

GCD(16807,2**31-1)=1.

 

IMPLEMENTATION
Unit: internal function, external function without procedure statement
 
Parameter: integer X, between 1 and M-1
 
Returns: number uniformly random in [1,M-1]

 

LCG: procedure
parse arg X
numeric digits 14
A = 16807; M = 2147483647
return A * X // M

 

EXAMPLE

Literature
Knuth D. E. Seminumerical Algorithms, vol. 2 of The Art of Computer Programming
Addison-Wesley, 1973
Park S. K., Miller K. W. Random Number Generators: Good ones are hard to find
CACM October 1988 Vol. 31 No. 10, pp. 1192-1201


Cover Contents Index Main page

last modified 1st August 2001
Copyright 2000-2001 Vladimir Zabrodsky
Czech Republic