Równoważność dwóch metod generowania liczb pseudolosowych

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Wibowit
Użytkownik
Użytkownik
Posty: 5
Rejestracja: 24 sie 2011, o 20:09
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 1 raz

Równoważność dwóch metod generowania liczb pseudolosowych

Post autor: Wibowit »

Piszę sobie pewien wieloplatformowy program i jako, że potrzebny mi był generator liczb pseudolosowych, który byłby przenośny i efektywnie zrównoleglony to poszukałem i znalazłem coś takiego: ... wc64x.html

Algorytm oferuje dwie główne metody:
- metoda do obliczania kolejnego stanu (next),
- metoda do obliczania stanu po n iteracjach poprzedniej metody (skip),
Pierwsza metoda działa w czasie O(1), druga w czasie O(lg n).

Problem polega na tym, że nie widzę bezpośredniej zależności między tymi metodami, tzn dlaczego skip(n) rzeczywiście działa jak n wywołań next.

Moja implementacja w Scali jest tutaj: ... c64x.scala

Warte uwagi kawałki kodu to:
Stałe:

Kod: Zaznacz cały

  val aLong = 4294883355L
  val aBig = BigInt(aLong)
  val mBig = (aBig << 32) - 1
Matematycznie:
\(\displaystyle{ A = 4294883355 \\
M = \left( A * 2^{32}\right) - 1}\)
Ciało funkcji next obliczające stan generatora dla następnego kroku (state to Long i jest on stanem generatora):

Kod: Zaznacz cały

    val c = state >>> 32
    val x = state & 0xFFFFFFFFL
    state = Mwc64x.aLong * x + c
Matematycznie byłoby to:
\(\displaystyle{ c_{n} = \left\lfloor state_{n} / 2^{32} \right\rfloor \\
x_{n} = state_{n} \% 2^{32} \\
state_{n+1} = A * x_{n} + c_{n}}\)
Ciało funkcji skip przyjmującej parametr distance i wykonującej efektywnie distance kroków:

Kod: Zaznacz cały

    val (c, x) = (state >>> 32, state & 0xFFFFFFFFL)
    val m = aBig.modPow(distance, mBig)
    val (x1, c1) = ((aBig * x + c) * m % mBig) /% aBig
    state = (c1.toLong << 32) + x1.toLong
Matematycznie byłoby to:
\(\displaystyle{ c_{n} = \left\lfloor state_{n} / 2^{32} \right\rfloor \\
x_{n} = state_{n} \% 2^{32} \\
m_{distance} = A ^{distance} \% M \\
v_{n + distance} = \left( A * x_{n} + c_{n}\right) * m_{distance} \% M \\
x_{n + distance} = \left\lfloor v_{n + distance} / A \right\rfloor \\
c_{n + distance} = v_{n + distance} \% A \\
state_{n + distance} = c_{n + distance} * 2^{32} + x_{n + distance}}\)
skip(0) efektywnie nie zmienia stanu generatora.
skip(1) zmienia stan tak jak pojedyncze wywołanie next.
skip(n) zachowuje się tak jak opisane poprzednio, czyli tak jak n nextów.


Proszę o dowód na to, że n iteracji funkcji next da wynik taki sam jak wywołanie skip(n).
ODPOWIEDZ