[ edellinen ] [ Tekijänoikeuksista ] [ Sisällys ] [ seuraava ]

Ohjelmoinnin alkeet: Vastauksia usein esitettyihin kysymyksiin
Luku 4 Satunnaislukuongelmia


4.1 Satunnaislukugeneraattori arpoo aina saman sarjan

On melkeinpä vale puhua satunnaisuudesta samassa yhteydessä ohjelmointikielten erilaisten rand-käskyjen tai -kirjastoaliohjelmien kanssa. Näiden tuottama satunnaisuus on näennäistä: takana on täysin toistettavissa oleva matemaattinen metodi, joka pyrkii tuottamaan suhteellisen satunnaisilta näyttäviä lukuja. Yksi tämän aiheuttama ongelma on se, että generaattori on alustettava. Alustustapa riippuu kielestä; kohtuuhyvä metodi on uudehkoissa Pascal-murteissa randomize-käsky sekä C:ssä srand(time(0)) (tässä tarvitaan stdlib.h- ja time.h-headerfileitä).


4.2 Satunnaislukugeneraattori arpoo aina samaa lukua

On ehkä liiankin hyvin opetettu ihmisiä sanomaan ``randomize'' tai ``srand(time(0))'' (tai mikä se nyt milläkin kielellä onkaan), jotta satunnaislukugeneraattori antaisi hyvän tuloksen. Nimittäin on helppo ymmärtää tämä väärin, loitsu lausutaan joka kerta, kun halutaan satunnaisluku. Esimerkki virheestä tuottaa ajettaessa mainitun tuloksen.

Pääsääntö on yksinkertainen: Käytä satunnaisluvun alustajaa (randomize, srand tms) vain kerran ohjelmassa. Yleensä hyvä paikka tälle on juuri ohjelman alussa. Käytä alustajaa useita kertoja vain, jos ymmärrät sekä ohjelmointitekniikan että tilastomatematiikan kannalta, mitä olet tekemässä.


4.3 Miten saan satunnaisen kokonaisluvun väliltä 42..512?

VAROITUS: Tässä annettu vastaus voi olla väärä. Keskustele oman satunnaisuuden asiantuntijasi kanssa ennen kuin käytät tässä annettuja ohjeita.

Tyypillinen standardikirjastossa oleva satunnaislukugeneraattori palauttaa joko kokonaisluvun joltakin ennalta määrätyltä väliltä taikka sitten liukuluvun nollan ja ykkösen välistä. Yleensä kuitenkin kaivataan satunnaista kokonaislukua joltakin tietyltä väliltä.

Jos kirjaston satunnaislukugeneraattori palauttaa liukuluvun f, jonka tiedetään olevan välillä 0 <= f < 1, on suhteellisen yksinkertainen tapa skaalata tämä halutulle välille MIN <= f' < MAX kaavan f' := (MAX - MIN) * f + MIN käyttäminen. Tässä toki pitää käytetyn liukulukutyypin olla riittävän tarkka. Jos haluat tuloksen olevan kokonaisluku väliltä MIN...MAX, käytä kaavaa tulos := int( (MAX - MIN + 1) * f) + MIN, missä funktio int tekee liukuluvusta kokonaisluvun katkaisemalla (poimimalla suurimman kokonaisluvun, joka ei ole suurempi kuin kyseinen liukuluku).

Mikäli satunnaislukugeneraattori palauttaa kokonaisluvun väliltä 0...RAND_MAX ja haluat tulokseksi liukuluvun väliltä MIN <= tulos < MAX, voit käyttää kaavaa tulos := double(MAX - MIN) / (RAND_MAX + 1) * f + MIN. Jos haluat tuloksen olevan kokonaisluku väliltä MIN...MAX, ongelma on hankalampi: mikä tahansa skaalaustapa saattaa tehdä huonoa satunnaislukujen satunnaisuudelle. Käytetyin tapa, jakojäännöksen ottaminen, suosii satunnaisluvun alimpia bittejä ja (mikäli generaattori on huono, kuten valitettavan usein on) saattaa jopa tuhota saatavien lukujen satunnaisuuden täysin. Hieman parempi tapa on käyttää "Numerical Recipes in C" -kirjan (Press, Flannery, Teukolsky ja Vetterling; Cambridge University Press, 1992) ohjetta ja käydä liukulukujen kautta. Tämä metodi toimii C:llä kirjoitettuna seuraavasti:

        MIN + (int)((MAX - MIN + 1.0) * rand() / (RAND_MAX + 1.0))

missä MAX ja MIN ovat halutun luvun ylä- ja alaraja, ja RAND_MAX satunnaislukugeneraattorin rand() tuottama suurin kokonaisluku (pienin on nolla). Tämän metodin hankaluutena on liukulukujen käytön aiheuttama laskentaepätarkkuus.

Toinen tapa on seuraava: Toinen tapa on seuraava: Olkoon ensin N := MAX - MIN + 1 ja RM := RAND_MAX + 1 (missä RAND_MAX on suurin luku, jonka satunnaislukugeneraattori tuottaa). Jaetaan väli 0..RAND_MAX N+1:een osaan, joista N ensimmäistä ovat yhtä pitkiä. Viimeinen osa saa olla tyhjä. Viimeisestä osasta kannattaa tehdä lyhyt, mutta sen ei välttämättä tarvitse olla lyhyin mahdollinen. Sitten tuotetaan valesatunnaislukuja kunnes tulos f osuu johonkin muuhun kuin viimeiseen osaan eli f < N * osan_koko, ja palautetaan f / osan_koko + MIN. Valmis C-koodi löytyy Niemitalon artikkelista <iznpv693fk8.fsf@stekt38.oulu.fi> (Google: Re: Satunnaislukujen generointi C++:ssa?).

Edellämainituissa menetelmissä täytyy halutun välin pituuden olla enintään RAND_MAX.

Vielä yksi tapa on käyttää omaa satunnaislukugeneraattoria. Tässä pitää olla todella tarkkana: on helppoa keksiä surkea satunnaislukugeneraattori ja vaikeata keksiä hyvä sellainen. Satunnaiseen (!) käyttöön sopivan C-kielisen generaattorin on kirjoittanut Antti Valmari, ja se on saatavissa verkosta.


4.4 Lottorivin arvonta

Lottoriviä arvottaessa olennaista on, että samaa lukua ei arvota kahta kertaa. Tätä ei pidä toteuttaa arpomalla joka kierroksella luku väliltä 1..39 ja hylkäämällä jo arvotut numerot. Tuo nimittäin voi johtaa umpiluuppiin.

Hyvä ja yksinkertainen lottorivin arvonta-algoritmi on tässä (kiitokset Kimmo Surakalle): Kootaan taulukkoon kaikki 39 lukua, joista arvonta suoritetaan. Arvotaan ensimmäinen luku hakemalla satunnaisluku väliltä 1..39 ja katsotaan, mikä luku tämän numeron osoittamassa kohdassa on: se on ensimmäinen lottonumero. Poistetaan tämä numero taulukosta, ja arvotaan luku väliltä 1..38, jonka taulukosta osoittama luku on seuraava lottonumero, joka poistetaan. Toistetaan, kunnes kaikki seitsemän numeroa on arvottu. Algoritmin C-kielinen toteutus löytyy Surakan alkuperäisestä nyysiartikkelista <u1lbtaksryk.fsf@mustahaikara.cs.tut.fi> (Google: Re: Lotto C++:lla), jossa on pieni virhe: ohjelman kolmanneksi viimeinen ja toiseksi viimeinen rivi pitää vaihtaa.


[ edellinen ] [ Tekijänoikeuksista ] [ Sisällys ] [ seuraava ]
Ohjelmoinnin alkeet: Vastauksia usein esitettyihin kysymyksiin
$Revision: 1.38 $ $Date: 2001/06/12 19:19:36 $
Antti-Juhani Kaijanaho gaia@iki.fi
Jori Mäntysalo jm58660@uta.fi