Most recent comments
Liveblogg nyttårsaften 2017
Tor, 11 months, 3 weeks
Jogging og blogging
Are, 1 year, 11 months
Liveblogg nyttårsaften 2016
Are, 1 year, 11 months
Reading in dark times
Are, 2 years, 1 month
Moldejazz 2016
Camilla, 2 years, 4 months
Dørskilt
Karoline, 2 years, 5 months
Halifax
Tor, 2 years, 6 months
Sony Smartwatch 3 review
Tor, 2 years, 6 months
Numerikk, takk
Tor, 2 years, 6 months
Topp tur
Camilla, 2 years, 8 months
50 book challenge
Camilla, 11 months, 3 weeks
Ten years ago
Musikklinjas julekonsert 2008
Camilla
Controls
Register

Tilfeldige tall

Å kunne generere tilfeldige tall er viktig i veldig mange sammenhenger, for eksempel til engangsnøkler innen kryptert kommunikasjon og til forskjellige varianter av statiskiske beregninger. Men hva mener man egentlig med «tilfeldige» tall, og hvordan kan datamaskiner, som i utgangspunktet er deterministiske vesener, generere tilfeldige tall?

Når man snakker om tilfeldige tall mener man i praksis ofte tilsynelatende tilfeldige tall. Det er gjerne tall man finner ved en deterministisk prosess, som betyr at de ikke er tilfeldige, men at de kan se tilfeldige ut for en person som ikke vet hvordan tallene blir funnet. Det finnes ulike varianter av slike prosesser, og noen er mer tilsynelatende tilfeldige enn andre. Et enkelt eksempel er desimaler i pi.

Pi er et irasjonalt tall, som betyr at tallene bak komma aldri vil ende opp som en repeterende sekvens. Disse tallene er tilsynelatende tilfeldige i den betydning at de er jevnt fordelt (alle tallene fra 0 til 9 dukker opp like ofte i gjennomsnitt) og uten noe system, men hvem som helst kan regne dem ut.

En annen lettvint måte å finne tilsynelatende tilfeldige tall er algoritmen med det festlige navnet Blum Blum Shub. Den sier enkelt og greit at du skal ta to primtall og gange dem sammen, så du får et stort tall. Dette tallet kaller vi M. Så velger du deg et annet tall, som vi kaller x0, kvadrerer det, og tar resten av kvadratet delt på M. Eller sagt på en mer konsis måte,

For eksempel, si at vi velger

og at vi begynner med

Kvadratet av 500 er 250000, og resten av 250000/223693 er 26307 altså

26307 er dermed det første tilfeldige tallet vårt. Så gjentar vi prosessen:

Ogsåvidere. Denne måten å finne tilfeldige tall på er såkalt kryptografisk sikker, som betyr at hvis du velger tilstrekkelig store primtall til å begynne med kan ikke noen med sikkerhet si hvilken prosess du bruker for å generere tilfeldige tall uten å først observere og analysere fordømt mange tall. Graden av sikkerhet er naturligvis knyttet til størrelsen på primtallene du starter med, og det er lett å sjekke med en kalkulator eller hoderegning at hvis du begynner med for eksempel 13 og 17 er det lett å havne i et repeterende mønster. Og sant å si vil man alltid havne i et repeterende mønster, men hvis mønsteret er så langt at du aldri ser mer enn en repetisjon går det greit likevel. Her er et plot av de 1000 første tallene i rekken vi begynte på:

Men hva så med ekte tilfeldige tall? Det kan man åpenbart ikke lage med en deterministisk prosess, og dermed kan man heller ikke lage dem i et programmeringsspråk. Hvis man derimot involverer en eller annen uforutsigbar fysisisk prosess er det ganske lett å lage ekte tilfeldige tall. Som et eksempel, la oss tenke oss at du har en klokke og en Geigerteller. En Geigerteller er en dings som «goes ding when there's stuff» i betydningen at den lager lyd når den registrerer stråling fra en radioaktiv prosess. Det er alltid litt radiokativitet rundtomkring, så hvis man har en Geigerteller påslått i et vanlig rom vil man høre et klikk i ny og ne. Så tenker vi oss at hver gang du hører et klikk noterer du ned tallet sekundviseren på klokken din står på. Det er ingen måte du kan forutse når detektoren vil plukke opp noe, så dette er helt ekte tilfeldige tall, i betydningen at ingen, selv ikke du, kan vite hva det neste tallet vil bli.

Hvis du sitter på en skikkelig datamaskin har du lettvint tilgang til ekte tilfeldige tall fra /dev/random, som du kan lese ved å skrive noe slikt som
head /dev/random | uuencode -m -

Disse tallene genererer datamaskinen fra uforutsigbare fysiske prosesser som temperaturmålinger, spenningsmålinger og brukerdata som tastetrykk og musebevegelser, så dette er kvalitet.

Moralen er at hvilken type tilfeldige tall du bør bruke kommer an på hva du skal gjøre. Driver du med kryptografi er sikkert Blum Blum Shub et utmerket valg. Driver du derimot med simuleringer som baserer seg på tilfeldige tall, såkalte Monte Carlo-simuleringer, vil du sannsynligvis bruke en som går raskere å regne ut, som for eksempel Mersenne twister. Ekte tilfeldige tall er ikke alltid så enkelt å bruke hvis man trenger mange tall, fordi maskinen bruker litt tid på hente inn tilfeldige tall fra de fysiske prosessene den måler.

Sånn. Ferdig. Fornøyd nå, Ulf?

-Tor Nordam
Matteus, Kjellove, Ulf likes this

Comments

ingen av dem er spesielt relevante.

Den ene er at du har minnet meg på min gamle ambisjon om å reise tilbake i tid, møte Pythagoras og bevise for ham at π er et irrasjonalt tall. Og kanskje filme ansiktsuttrykket idet jeg gjør det.

Det andre er denne languagelog-posten. Det har ikke så mye med tall å gjøre, men jeg føler linken hører hjemme her.

Ulf,  29.04.11 13:36

Ja, Tor. Veldig.

Pi er fascinerende på mange måter. Artig er det i alle fall at man kan regne ut en tilnærming til Pi ved å kaste rettlinjede objekter (f.eks fysrtikker) på et område som består av parallelle linjer (med avstand større enn lengden på fyrstikkene). Sannsynligheten for at fyrstikken i et tilfeldig kast vil krysse en av linjene er proporsjonal med Pi.

Se Buffons nål for en forklaring. Obs! Her har de brukt nåler, ikke fyrstikker. Det er nok fordi man brukte svovelstikker den gangen, og da ble det som regel krevd risikotillegg.
Tor,  15.05.11 15:42

Arne, min gode mann! Lenge siden sist.

En annen måte å regne ut pi er å tegne en firkant med en sirkel inni, og så kaste ting på den. Forholdet mellom antall ting som lander inni og utenfor sirkelen er det samme som forholdet mellom arealet av firkanten og arealet av sirkelen, som også er proporsjonalt med pi.
Camilla,  15.05.11 15:45

om at når matematikere og fysikere driver og snakker om hvor hardt de jobber er det ikke helt sant. Vi humanister sitter i alle fall ikke og prøver å finne π ved å kaste ting på ting.
Kjellove,  15.05.11 20:49

:P
Tor,  15.05.11 20:52

Det er det motsatte av rasjonalt. Rasjonale tall kan skrive som en brøk av to heltall, irrasjonale tall kan ikke skrives på denne måten. Og man kan vise at pi er et irasjonalt tall, uten at jeg kan si at jeg husker hvordan man gjør det.
Kjellove,  15.05.11 22:07

Skulle bare påpeke at det bøyes «irrasjonelle» i flertall. Hihi!
Tor,  15.05.11 22:42

I alle fall ikke i følge Store Norske. Og mattebøker.
Kjellove,  16.05.11 12:26

Nå er ikke Store norske noen ordbok, men du har nok rett. Hm, mener jeg å huske noe fra matematikktimene om et fornuftig grammatisk skille her? Hvis ikke, er det et falskt minne som funker. Flaut å korrigere ting som ikke er feil.
Jørgen,  16.05.11 18:09

Irrasjonalt skrives ikke med kun én r.
Arne,  19.06.11 15:51

Ja... jeg har falt ut av the loop dessverre. Men jeg skal prøve å komme meg inn igjen! Frekvensen på mine kommentarer skal øke jevnt og trutt.

Veldig bra å se at det fremedles er full aktivitet på calcuttagutta!