A Mersenne Twister algoritmusnak hogy lehet ennyire nagy periódus hossza?
Adott az implenetáció ami az "etalon" : [link]
Az mti értéke 625 ha inicializálatlan a generátor, ez után sose lehet 625. Ha innen indul a generálás akkor 5489 seed értékkel inicializálja ( azaz init_genrand(5489UL) ), így gyakorlatilag minden generáláskor kivétel nélkül 1-624 érték között mozog mti értéke. Az mt 32 bites előjel nélküli egészekből álló 624 elemű tömb.
Vagyis ha nincs korlátozó tényező akkor mt 2^(32*624) féle állapotot felvehet, míg mti 624+1 féle állapotot, generáláskor 624 félét. Így a generáláskor a lehetséges állapotok száma maximum 624*(2^(32*624)) darab állapot lehet.
Viszont 624*(2^(32*624)) az durván 2^185410.91 ami jóval kevesebb mint (2^19937)-1. Továbbá mint tudjuk 2^32 féle kezdőállapotot lehet beállítani az init_genrand-al, ezért van az init_by_array hogy ennél több lehessen a kezdőállapotok száma. Ugyanakkor pedig tetszőlegesen bármit az mt-nek nem állíthatunk be. Vagyis nem valid állapota mind a 2^(32*624) darab állapot, ha nem így van akkor meg minek az init_by_array ?
Ennek ellenére hogy az életbe lehet hosszabb a Mersenne Twister algoritmus periódusa mint a teljes állapotterük méretéből adódik?
válasza:> Viszont 624*(2^(32*624)) az durván 2^185410.91
Valamit rosszul számoltál. Eleve 2^(32*624) = 2^19968.
624 ≈ 2^9.285…
Így: 624*2^(32*624) ≈ 2^9.285 * 2^(32*624) = 2^(9.285+32*624) = 2^19977.285
> Ugyanakkor pedig tetszőlegesen bármit az mt-nek nem állíthatunk be. Vagyis nem valid állapota mind a 2^(32*624) darab állapot, ha nem így van akkor meg minek az init_by_array ?
Gondolom azért, hogy ha olyan jellegű a felhasználás, akkor nem biztos, hogy elég 2^32 induló állapot, így a limiten belül tetszőlegesen lehet a kiinduló állapotot is változatosabbá tenni.
"Valamit rosszul számoltál"
Igazad van, 2^(32*624) = 2^19968 ... így már világos.
"Gondolom azért, hogy ha olyan jellegű a felhasználás, akkor nem biztos, hogy elég 2^32 induló állapot"
624 elemű tömbbel (init_by_array-al) kihasználható az összes lehetséges kezdőállapot?
Most nézem, jól számoltam csak rosszul dekódoltam fejben, hihetetlen mind a ketten benéztük.
A kitevő 185410 < 185410.91 < 185411 . Azaz 185 ezer 410 egész akármennyi, szemben a 19937 azaz tizenkilecezer akármennyivel.
"624 elemű tömbbel (init_by_array-al) kihasználható az összes lehetséges kezdőállapot?"
Több mint valószínű, hogy igen. Kérdés hogy egyenletes eloszlással is, ha az input egyenletes eloszlású 32 bites true random ?
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!