Linearni generatori slučajnih brojeva
(Linear congruential generator: LCG)

Linearne generatore slučajnih brojeva (LCG) je smislio Lehmer 1948. Ovaj generator pseudoslučajnih brojeva se služi sljedećom rekurzijom:

y_n+1=ay_n+b (mod m).

Početni y_o i ostali parametri se zadaju sa:

LCG (m, a, b, y_o).

Klasični LCGovi

ANSIC

LCG(2³¹,1103515245,12345,12345)

ANSIC je generator kojeg koristi ANSI c rand() funkcija, BSD verzija. Neke verzije UNIX-a u online priručniku netočno tvrde da je period generaotra 2³².

MINSTD

LCG(2³¹-1, a= 7⁵ = 16807, 0, 1)

RANDU

LCG(2³¹, 2¹⁶ + 3 = 65539, 0, 1)

SIMSCRIPT

LCG(2³¹-1,630360016, 0, 1)

Implementirano u programskom jeziku za simulacije SIMSCRIPT II.

BCSLIB

LCG(2³⁵, 5¹⁵,7261067085, 0)

Implementirano u programskom jeziku SIMULA, te verzija sa modulom m=2⁴⁷ na CDC računalima.

BCPL

LCG(2³², 2147001325, 715136305, 0)

Ovaj generator se koristio u jeziku BCPL.

URN12

LCG(2³¹, 452807053, 0, 1)

Ovaj generator se koristio u CUPL jeziku.

Zanimljivost je da je

5¹⁵ (mod 2)³¹ = 452807053, gdje je 5¹⁵ m kod BCSLIBa.

APPLE

LCG(2³⁵, 5¹³ = 1220703125, 0, 1)

Implementirano na računalima APPLE.

Super-Duper

LCG (2³², 69069, 0, 1)

Ovaj generator je dio kombiniranog generator SUPER-DUPER (kombiniran sa generatorom pomicanja registara udesno). Ovaj LCG sam se ponekad naziva Super-Duper.

Bio je implementiran na IBM računalima.

HoaglinLCGs (Hoaglinovi LCGovi)

LCG(2³¹ – 1, a, 0, 1)

a Î {1078318381, 1203248318, 397204094, 2027812808, 1323257245, 764261123}

Ovi brojevi su rezultat studija koje je proveo Hoaglin, a imaju najbolje spektralne rezultate.

FishmanLCGs (Fismanovi LCGovi)

Parametri a navedeni u tablici određuju najboljih 5 LCGova u odnosu na m u analizama što su ih proveli Fishman i Moore.

Rb.	m	a
1 2 3 4 5	2^31 - 1	742938285 950706376 1226874159 62089911 1343714438
Rb.	m	a
6 7 8 9 10	2^32	1099087573 2396548189 2824527309 3934873077 392314069
Rb.	m	a
11 12 13 14 15	2^48	68909602460261 33952834046453 43272750451645 127107890972165 55151000561141

Knuth–ovi i Borosh i Niederreiter-ovi LCGovi

Ova lista 30 LCGova uključuje RANDU, BCSLIB, APPLE, Super-Duper i DERIVE. Ovi LCGovi su selektirani po različitim kriterijima.

LCG(2^n, a, 0, 1)
n	a
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35	13821 47458 82669 160461 217293 387645 886269 3067221 3513381 12268885 21149085 41430805 96801245 169764749 338335805 777138309 906185749 3039177861 6223592213 10618587253 21733031525

Neki noviji LCGovi

NAG

LCG(2⁵⁹, 13¹³ , 0, 123456789(2³² +1))

Ovo je osnovni generator pseudoslučajnih brojeva u mnogim distribucijama NAG Fortran biblioteka.

DRAND48

LCG(2⁴⁸, 25214903917, 11, 0)

DRAND48 je generator koji se koristi u ANSI C-u, funkcija drand48().

CRAY

LCG(2⁴⁸, 44485709377909, 0, 1)

Ovaj generator je implemetiran u CRAY sistemima, te se nalazi u PASCLIB-u, kolekciji potprograma koji se mogu pozvati iz Pascala na CD CYBER računalima.

MAPLE

LCG(10¹² –11, 427419669081, 0, 1)

Implementirano u matemačkom softwareu Maple.

DERIVE

LCG(2³², 3141592653, 1, 0)

CRAND

LCG(m, a, 0, 1)

Rb.	m	a
1 2 3 4 5	2^32 2^54 2^54 2^54 2^54	663608941 2783377641436325 2783377640906189 2783377640450829 2783377640871525

Ovi generatori su implementirani u raznim verzijama C-RANDa, paketa za generiranje neuniformnih random brojeva.

L'EcuyerLCGovi

Pierre L'Ecuyer koristi spektralne testove i Bayerove dijeljitelje da dobije dobre a za LCG(m,a,0,1) sa izabranim primarnim modulom m.

L'Ecuyer je predložio sljedeće LCGove:

Rb.	m	a
1 2 3 4 5	2^31 – 1 2^31 – 1 2^47 – 115 2^47 – 115 2^63 – 25	1385320287 41358 71971110957370 -10018789 2307085864

MATH

LCG(m = a⁴⁸ – a⁸ +1, a= 2³¹, 0, 1)

Implementiran u Mathematica-i.

CARRY

LCG(m = a²⁴ – a¹⁰ +1, a= 2²⁴, 0, 1)