Top
Previous
Next
# 5. A simple RNG: linear congruential

### Lehmer (1949)

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

where a, c and m are constants. An example:

Set a=7, c=7 and m=10:
X_{n} |
aX_{n} + c |
X_{n+1} |

7 |
7*7 + 7 = 56 |
6 |

6 |
7*6 + 7 = 49 |
9 |

9 |
7*9 + 7 = 70 |
0 |

0 |
7*0 + 7 = 7 |
7 |

This is obviously not a great RNG: it cycles back to the original seed
value after just 4 values.

### Lewis, Goodman, Miller (1969)

A minimal standard RNG, according to Park and Miller (1988):

a = 16807
c = 0
m = 2^{31}-1 = 2147483647

Period: 2^{31}-2 = approx 2.1*10^{9}

**Note** that an ordinary Pentium III will exhaust this
period in less than one CPU hour!

Copyright © 2000
Per Kraulis
$Date: 2000/12/04 12:20:05 $