A.S.: Igen, úgy tűnik, hogy a “kocka” egyes száma a “kocka”. 😉
Egy trükkös programozási feladat kering az interneten, amely, mint azt a pragmatikus címadási kísérletemből már kitalálhattad, a következőképpen formalizálható:
Adott egy függvény, amely egy egyenletesen véletlenszerű számot ad vissza 1 és 5 között (beleértve), tervezz egy olyan függvényt, amely egy egyenletesen véletlenszerű számot ad vissza 1 és 7 között (beleértve).
Ha az algoritmusok és a statisztika metszéspontja a te műfajod, próbáld ki bátran! Extra kihívás, hogy az algoritmusodat időben korlátossá tedd. Ezt szórakoztató feladatnak találtam, csakhogy rájöttem, hogy itt alapvető korlátok játszanak közre.
A kocka itt természetesen egy tökéletesen egyenletes véletlengenerátort jelent, ami csak elméletben létezik. A valós világ kockáit a természeti törvények és a környezet tökéletlenségei úgy szabályozzák, hogy csak egy (bár jó) közelítése ennek az absztrakt modellnek.
Egy korlátlan megoldás
Nézzük meg a korlátlan algoritmusok egy családját. Ahhoz, hogy olyan véletlengenerátort hozzunk létre, amelynek legalább 7 kimenetele van, legalább kétszer kell dobnunk az 5 oldalú kockával. A kétszeri dobás 5^2=25 lehetséges kimenetet hoz létre, és bár ez nem 7-szeres, az első 21 kimenetet 7 azonos méretű 3 csoporthoz tudjuk rendelni. Ha azonban a fennmaradó 4 kimenetel valamelyikénél kötünk ki, akkor az eljárást újra kell kezdeni. Nem rendelhetjük egyszerűen e 4 szerencsétlen végállapot bármelyikét egy kimenethez, mert ezzel elrontjuk az egyenletes véletlenszerűség tulajdonságát.
A fenti ábrán a körök a programunk “állapotait” jelölik, a benne lévő szöveg pedig a dobott kocka legutóbbi értékét. A zöld dobozok ezután azt a kimenetet jelölik, amelyet a végállapottól függően (= a kocka kétszeri dobása után) rendelünk hozzá. Az esetek 84%-ában két dobás után kapunk egy kimenetet, és az algoritmus befejeződik. Mint látható, egy ciklus van jelen, és korlátlanná teszi az algoritmust. Ez azt jelenti, hogy minden egész szám esetén, függetlenül attól, hogy mekkora, van egy kis, de nem nulla valószínűsége annak, hogy a dobások teljes száma meghaladja ezt az összeget, hogy egy kimeneti értéket számítsunk ki. Szigorú időigényű valós idejű alkalmazásokról tehát szó sem lehet, hacsak nem vagyunk hajlandóak kompromisszumokat kötni az algoritmus statisztikai pontosságát illetően.
A megoldás egy változata kezdetben legfeljebb három kockát dob, mielőtt újraindul: ez 5^3=125 végállapotot hoz létre, és ezek közül legfeljebb 119-et tudunk 7 azonos méretű 17 csoporthoz rendelni. Most már 95,2% a valószínűsége annak, hogy maximum három dobás után célba érünk. Vegyük észre, hogy átlagosan kevesebbszer kell dobnunk, mint korábban (280/119 ≈ 2,35 szemben 50/21 ≈ 2,38), mert a legtöbbször már az első két dobás után rövidíthetünk, és ezeket a köztes állapotokat közvetlenül leképezhetjük egy kimenetre. Ez az átlagos dobásszám folyamatosan csökken, ahogy folytatjuk a tendenciát.
Ha ismered az információelméletet, akkor gondolj arra, hogy egy dobás 5 oldalú kockával (= rand5) log2(5) ≈ 2,32 bit információt generál, és egy dobás 7 oldalú kockával (= rand7) log2(7) ≈ 2,81 bit információt generál. Kiderül, hogy a határesetben csak log(7)/log(5) ≈ 1,21 rand5 hívásra van szükségünk minden egyes rand7 értékhez, amelyet meg szeretnénk kapni. A pontos megvalósítás, amely tetszőlegesen közel működik ehhez a határértékhez, meglehetősen bonyolult, és nem tartozik ennek a cikknek a tárgykörébe. A rand7 többszöri hívása között állapotinformációkat kellene tárolnunk, és az általam elképzelt algoritmus nemcsak időben, hanem memóriában is korlátlan. Szívesen felkérem, hogy tájékoztasson egy olyan módszerről, amely ez utóbbi problémát megoldja!
Egy korlátos megoldás
Nem létezik olyan korlátos algoritmus, amely 1 és 7 közötti tökéletesen egyenletes véletlen értéket számol ki, ha csak 1 és 5 közötti véletlengenerátorral rendelkezünk. Tekintsük a fenti korlátlan megoldások családját. Ahogy utaltam rá, minden ponton mindig lesz egy bizonyos mennyiségű “maradék” állapot (1 és 6 között), ami miatt az algoritmus újraindul. Ennek az az oka, hogy az 5 és a 7 prímszámok, és az 5 egyetlen hatványa sem lehet soha 7 többszöröse. Bármilyen csábító is lenne Fermat kis tételét használni, az ilyen próbálkozások egyről a kettőre való hibához vezetnek, mivel az alapvető számelmélet lehetetlenné teszi a korlátos megoldást ebben a családban.
Megállapíthatjuk joggal, hogy a végállapotok száma nem mindig 5 hatványa, például a “legfeljebb három dobás” esetében, ahol már két dobás után rövidíthetünk. Esetleg úgy rendezhetnénk az állapottáblázatot, hogy változó hosszúságú utakkal és 7n végállapottal rendelkező korlátos algoritmust hozzunk létre? Vegyük azonban figyelembe a következőket:
- Ezek a végállapotok nem lesznek egyformán valószínűek, mert nem minden út ugyanolyan hosszú (= a rand5 hívások száma).
- Egyszerűen kibővíthetjük a fát úgy, hogy minden út egyformán hosszú legyen, ha haszontalanul megfelelő számúszor hívjuk meg a rand5-öt, amikor egy korai végállapothoz érünk. Ekkor a végállapotok száma ismét 5 hatványa lesz, és minden végállapot egyformán valószínű.
Ez persze nem formális bizonyítás, de remélem, adtam némi intuíciót a problémához. Mint látjuk, néha egy probléma nagyon is reálisnak tűnhet, hogy aztán ilyen matematikai tényekbe botoljunk. Az elemzés után rá tudsz jönni, hogy lehetséges-e szimulálni egy 8 oldalú kockát egy 4 oldalú kockából kiindulva?