Linear congruential generators

Formula

The generator is defined by the recurrence relation:

x(n+1) = (x(n) * multiply + add) % modulo

Known LCG

Generators sorted by modulo.

Name multiply add modulo bits
ZX Spectrum 75   2^16 + 1  
Park-Miller (1) 16807   2^31 - 1  
ANSI C (2) 1103515245 12345 2^31 30..16
IBM RANDU 65539   2^31  
Another Park-Miller 279470273   2^32 - 4  
Numerical Recipes 1664525 1013904223 2^32  
VAX 69069 1 2^32  
GCC 69069 5 2^32 30..16
Microsoft (3) 214013 2531011 2^32 30..16
Borland Delphi (4) 134775813 1 2^32 63..32
Borland C/C++ (5) 22695477 1 2^32 30..16
CRAY 44485709377909   2^48  
GNU libc rand48 25214903917 11 2^48 48..17

Full names:

    1. Park-Miller and Apple CarbonLib
    1. ANSI C: Watcom, Digital Mars, CodeWarrior, IBM VisualAge C/C++
    1. Microsoft Visual, Microsoft Quick C/C++, PHP (on Windows)
    1. Borland Delphi and Virtual Pascal
    1. Borland C/C++: rand() uses bits 30..16 whereas lrand() uses bits 30..0

Notes:

  • 2^16 + 1 (65537) is a Fermat prime F4, and 75 is a primitive root modulo F4
  • To get bits 30..16, use rand() = (x(n) >> 16) & 0x7fff

Park-Miller

A Park-Miller generator is a special case of a LCG: add=0. The seed have to be correctly generated to get the maximal period:

  • if seed=0, all numbers will all zero
  • if gcd(seed, modulo) != 1, the period will be smaller than the maximum