2015. január hónap bejegyzései

Lineáris kongruencia véletlenszám-generátorok

Az egyik legelterjedtebb véletlenszám-generátor típus a lineáris kongruencia típusú véletlenszám-generátor (LCG). A véletlenszám-generátort meghatározó rekurziós képlet a következő:

 \xi_n= (m \cdot \xi_{n-1} + a) \textrm{mod} M

A véletlenszám-generátor működését meghatározzák az m, a és M paraméterek. Amennyiben rosszul választjuk meg őket, akkor a véletlenszám-generátor minősége elfogadhatatlan lesz. Az M változó megadja a generátor maximális ciklusidejét. Általában kettő hatványként van választva, így az algoritmus könnyű bináris számítógépen implementálni.

Az LCG legfontosabb előnye, hogy implementációja egyszerű és kevés erőforrást igényel. Viszont a módszernek több hátránya is van. Egyrészt, korlátozott a ciklushossz, tipikusan 264 alatti. Ha M kettő hatvány, akkor az alacsonyabb helyértékű bitek ciklushossza még rövidebb. További hátránya, hogy bizonyos dimenziószám felett, mely a paraméterektől függ, a véletlen számok térbeli elhelyezkedése nem egyenletes, hipersíkok mentén csoportosulnak az adatok. Ezek a hátrányok nem minden gyakorlati esetben jelentenek problémát, így megfelelő körültekintéssel jól használhatók az LCG generátorok.

A következő táblázat bemutat néhány egyszerű példát az m, a és M paraméterekre.

m a       M      Megjegyzés
1664525 1013904223 232 Forrás: Numerical Recipies
25214903917 11 248 JAVA véletlenszámgenerátora
6364136223846793005 1442695040888963407 264 Forrás: Donald Knuth