Statistikk og Simulering

Økt 25. Slumptalsgeneratorar

Statistikk og Simulering

18. Økt 25. Slumptalsgeneratorar

Den mest populære metoden for å generera slumptal på ein datamaskin er lineære kongruensgeneratorar. Dei har mange lytar, men dei har vore velkjende over lang tid, dei er enkle å implementera, og dei er effektive. Der er ein del alternativ, og mange er betre sjølv om dei heller ikkje er lytefrie. Me tek for oss den lineære kongruensgeneratoren for å illustrera nokre generelle fenomen og utfordringar.

Definisjon 15 Ein lineær rekurrens er gjeve ved formelen

si = a si1 + cmodm,

for konstante heiltal a, c og m. Dersom me startar med eit frø (seed) s0, kan me bruka rekkurensen til å generera ei fylgje av slumptal x1,x2,x3,. Denne slumptalsgeneratoren er kjend som Lehmers algoritme og som en lineær kongruensgenerator.