Feladatok‎ > ‎

Random (Lineáris kongruencia generátor)


Bevezetés

Hogy tud a számítógép egy random számot előállítani? Hiszen az áramkörei működése teljesen logikus, a bemenetek függvényében egyértelműen kiszámítható kimenetet adnak, bármilyen esetben.

Mik számítanak egyáltalán randomnak a természetben? Ezen sokat lehet filozofálni, mert az sem egészen bizonyos, hogy létezik random, de próbáljuk valahogy mégis megfogni!

  • Egy jó véletlenszám-generátor nem mutat semmilyen mintázatot
  • Nem periodikus
  • Minden értéket egyenlő valószínűséggel vesz fel
  • Egy érték ismeretében nem tudunk következtetni se a következő, sem az előző értékre
  • Lehetőleg legyen gyors, hogy pl szimulációknál rengeteget lehessen generálni másodpercenként
Ezeket az igényeket (részben) kielégíti a Lineáris kongruencia generátor, amely egy kezdőértékből tud rengeteg elemet kiszámolni.

Implementáld saját kóddal! A részleteket megtalálod az angol Wikipedián és szerte az interneten.

Technikai részletek

A lineáris kongruencia generátor egy számsorozatot generál (Xn). Minden tag az előzőből számolható a következő rekurzív képlettel:

a, c, m egy-egy jól meghatározott konstans, hogy minél tovább "jó" legyen a véletlen generátor.

Például:

a=3
c=2
m=17
x0=11

x1 = 3*11+2 mod 17 = 35 mod 17 = 1
x2 = 3*1+5 mod 17 = 8

Mit használjunk x0-nak?