Lage en tilfeldighetsgenerator

Introduksjon

I denne oppgaven skal dere lage en pseudotilfeldig tallgenerator, LCG-klassen i lcg.py, og undersøke hvor tilfeldig tallene den lager faktisk er. Plottefunksjonene er gitt i filen plott.py.

Kort om pseudotilfeldige tall

En datamaskin er deterministisk: gitt samme input gir den alltid samme output. Den kan derfor ikke lage ekte tilfeldige tall (de må hentes fra fysiske prosesser, for eksempel støy i maskinvare). I stedet bruker vi en pseudotilfeldig tallgenerator (PRNG): en klasse som starter med en intern tilstand, kalt frø, og regner ut en ny tilstand hver gang vi ber om et tall. Tallene ser tilfeldige ut, men hele rekken er bestemt av frøet. Samme frø gir samme tallfølge, noe som er nyttig for å teste og gjenskape resultater.

Gode generatorer skal ha noen egenskaper:

• Tallene skal være jevnt fordelt over et definert intervall.
• Et tall skal ikke kunne forutsies fra de forrige uten kjennskap til tilstanden (ingen synlige mønstre).
• Perioden, altså hvor mange tall som kommer før følgen starter på nytt, skal være lang.

En lineær kongruensgenerator (LCG) er en av de enkleste generatorene. Den bruker formelen

x[n+1] = (a * x[n] + c) mod m

der m er modulus, a multiplikator, c inkrement og x[0] er frøet. Alle tallene ligger i intervallet 0 til m - 1, og deler vi på m får vi et desimaltall mellom 0 og 1. Valget av m, a og c avgjør hvor god generatoren blir. LCG-er har blitt brukt i mange programmeringsspråk og operativsystemer, og noen av dem hadde kjente svakheter. En av de mest beryktede er RANDU (m = 2^31, a = 65539, c = 0), som dere skal undersøke.

Klassegrensesnitt

from lcg import LCG

generator = LCG(1 << 31, 65539, 0, 1444) # 1 << 31 er bitskifting, altså at vi flytter 1 31 plasser til venstre. Dette er det samme som 2^31 (2 ** 31 i Python)
print(generator.rand())
print(generator.random())
print(generator.randint(1, 6))
print(generator.distrubusjon(["mynt", "krone"], [0.5, 0.5]))

Del 1: Selve generatoren

1. Implementer __init__ og rand slik at hvert kall bruker formelen over og lagrer resultatet som nytt frø.
2. Implementer random ved å dele resultatet fra rand på modulus.
3. Lag to generatorer med samme frø og kontroller at de gir samme tallfølge. Lag så en med et annet frø og se hva som skjer.
4. Kall random 100 ganger og skriv ut tallene. Ser de tilfeldige ut?

Del 2: Heltall og sannsynligheter

1. Implementer randint(gulv, tak). Resultatet skal være et heltall i [gulv, tak], og begge endepunktene skal kunne forekomme.
2. Kast en terning 60000 ganger med randint(1, 6) og tell hvor mange ganger hvert tall forekommer. Ble det som forventet?
3. Implementer distrubusjon(muligheter, dist). Lista dist skal summere til 1 og ha like mange elementer som muligheter. Metoden skal returnere et element fra muligiheter utfra distrubusjonen i dist. Et eksempel kan for eksempel være mulighetene ["bil", "geit"] med distrubusjonen [0.33, 0.67].

Del 3: Undersøk kvaliteten til generatoren

Bruk funksjonene i plott.py til å se på tallene.

1. Kjør plott_histogram_og_par(generator). Venstre figur viser et histogram av tallene, og høyre figur viser hvert tall mot det neste. Ser det tilfeldig ut?
2. Kjør plott_tripler(generator). Figuren viser de laveste bitene i de første tallene, påfølgende tripler (x[n], x[n+1], x[n+2]) i 3D, og tripler sett fra en bestemt vinkel. Hva ser dere?
3. Prøv å endre a, c og mod. Hva skjer med plottene hvis mod = 2^16, eller a = 5?

Tips

• Bruk % for modulo.
• Heltallsdivisjon // ungrå avrundingsdeil. Nyttig i randint()
• Samme frø gir samme tall hver gang. Dette er en egenskap, ikke en feil.
• Plottene bruker numpy og matplotlib. Installer dem med pip install numpy matplotlib hvis dere ikke har dem.
• Dere kan rotere på 3D-plottet som blir tegnet for å se på det fra forskjellige vinkler.

Utvidelser

• Lag en metode som finner perioden til generatoren ved å telle til frøet kommer tilbake. Prøv med små verdier for mod.
• Sammenlign med random-modulen i Python. Hvordan ser plottene ut for den?
• Prøv parameterne mod = 2^32, a = 1664525, c = 1013904223. Ser dere noen forskjeller i plotene?
• Bruk bare de høyeste bitene i resultatet i stedet for hele tallet.

hoyestebit = random.rand() >> 16 # Kaster de 16 laveste bitene

• Skriv en prosedyre som beregner pi ved å trekke tilfeldige punkter i et kvadrat og telle hvor mange som havner i en sirkel. Hvor nøyaktig ble svaret? Hint: En sirkel med radius 1 med senter i origo (0, 0) har formelen x^2 + y^2 = 1. Trekk ett tall for x, og ett tall for y.
• Lag en shuffle-metode som stokker en liste (Fisher–Yates) med generatoren.