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
Ciało funkcji\(\displaystyle{ A = 4294883355 \\
M = \left( A * 2^{32}\right) - 1}\)
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
Ciało funkcji\(\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}}\)
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
\(\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)
.