Inverzivni generatori

Inverzivni generatori pseudoslučajnih brojeva (Inversive Congruential Generators) (ICG) su djelo Eichenauera i Lehna (1986). Trebamo izabrati modul p, množitelj a, dodatni uvjet b i početnu vrijednost y₀.

Za zadani prirodni broj p, i za c Î Z_p,

c':= 0 ako je c=0, te

c':=c^-1 ako je c¹0.

To znači da je c' jednako broju c^p-2 (mod p).

Sada možemo zadati jednakost:

y_n+1 = ay'_n + b (mod p), n³0

da dobijemo pripadni niz pseudoslučajnih brojeva u {0, 1, … , p-1}.

Zapis ovog generatora je:

ICG(p, a, b, y₀)

Razlika u odnosu na LCG generatore je da u ICG generatorima nemamo strukture, brojevi se mogu nalaziti na bilo kojim mogućim mjestima, kao što je prikazano na donjoj slici, u regiji oko točke (0.5, 0.5).

ICG (2³¹ – 1, 1288490188, 1, 0)

Eksplicitni inverzivni generatori

Eksplicitni inverzivni generatori pseudoslučajnih brojeva (Explicit Inversive Congruential Generators) (EICG) je poboljšana verzija ICG-a, zapravo lakša za implementiranje u praksi. Cijena toga je manja maksimalna veličina uzorka. Zasluge su pobrali Eichenauer-Herrmann (1993).

Izaberemo prirodni broj p, množitelj od a Î Z_p, a ¹0, bÎ Z_p, I početna vrijednost n₀ u Z_p.

Tada imamo:

y_n=[a(n+n₀)+b]' (mod p), n³0

I pripadni niz pseudoslučajnih brojeva u {0, 1, … , p-1}.

Zapis:

EICG(p, a, b, n₀)

Zanimljivo je da se isti pseudoslučajni niz može dobiti u dva zapisa:

EICG(p, a, b, n₀)

EICG(p, a, 0,m₀)

ako je m₀ = n₀ + a'b (mod p). U večini slučajeva se stavlja b=0.

Kombinirani generatori

Eichenhauer-Herrmann (1993, 1994) su uveli jednostavnu tehniku kombiniranja inverzivnih generatora, kombinirajući ICG i EICG.