RANMAR

RANMAR jest algorytmem opisanym przez Marsaglię i Zamana w 1987 roku.

Operację $x\bullet y$ definiujemy następująco: $x\bullet y$ = {if x>= y then x-y else x-y+1}.Operacja zdefiniowana jest na liczbach rzeczywistych z przedziału [0,1) każda z 24-bitową częścią ułamkową. Jest ona używana do produkcji opóźnionej sekwencji Fibonacciego oznaczonej przez F(r,s,$\bullet$). Jest to sekwencja x₁,x₂,x₃,...liczb rzeczywistych, zdefiniowanych przez x_n = x_n-r $\bullet$ x_n-s. W algorytmie wybrano r=97,s=33. Algorytm ten samodzielnie nie przechodzi testu Birthday-Spacings, generatory opóźnionego Fibonacciego nie przechodzą tego testu chyba że opóźnienie r jest większe niż 500, lub powiedzmy binarna operacja $\bullet$ jest operacją mnożenia nieparzystych liczb całkowitych modulo 2^k. Aby generator mógł przejść wszystkie testy, łączymy go z drugim generatorem:

c_n = c_n-1 $\circ$ (7654321 / 16777216)

gdzie $c\circ d$ = {if c>=d then c-d, else c-d+16777213 / 16777216 } a 16777213 = 2²⁴-3 - liczba pierwsza. Inicjujemy c₀ = 362436 / 16777216

RMARIN

Należy teraz zainicjować tablicę 97 początkowych liczb. Będą wygenerowane algorytmem o nazwie RMARIN. Ponieważ będą generowane raz na początku, nie musimy się zbytnio troszczyć o szybkość generatora. Mamy dwa ciągi:

pierwszy y₁,y₂,y₃,y₄,...gdzie y_n = y_n-3*y_n-2*y_n-1 mod 179

drugi z₁,z₂,z₃,z₄,...gdzie z_n = 53*z_n-1 + 1 mod 169

Następnie bierzemy iloczyn elementów y_n i z_n, a następnie szósty bit licząc od najmłodszego: b_i = {if y_nz_n mod 64 <32 then 0 else 1}. Ponieważ zostały wybrane małe liczby modulo jak 179 i 169, mamy pewność, że dokładność mnożenia będzie wystarczająca.

Przykład RMARIN

Pierwszy ciąg inicjujemy liczbami 12, 34 i 56 drugi liczbą 78.

y1= (y{-2}*y{-1}*y0) mod 179 =(12*34*56) mod 179 = 22848 mod 179 =115

z1 = (53*z0+1) mod 169 = (53*78+1) mod 169 = 4135 mod 169 = 79

y1*z1 = 9085

binarnie 9085 = 0010 0011 0111 1101‬

szósty bit licząc od najmłodszego to 1

y2 = (34*56*115) mod 179 = 218960 mod 179 = 43

z2 = (53*79+1) mod 169 = 4188 mod 169 = 132

y2*z2 = 5676 = ‭0001 0110 0010 1100‬

szósty bit licząc od najmłodszego to 1

y3 = (56*115*43) mod 179 = 7525 = 7

z3 = (53*132+1) mod 169 = 6997mod 169 = 68

y3*z3 = 476 = ‭0001 1101 1100‬

szósty bit licząc od najmłodszego to 0

Kolejne bity: 110.. aż w końcu powstanie liczba 13697435 = binarnie ‭1101 0001 0000 0001 1001 1011‬

Liczby kolejno :

u1= 13697435

u2= 3833429

u3= 12353926

u4= 2287754

Oczywiście przesunięte o 24 bity tworząc liczby zmiennoprzecinkowe z przedziału [0,1)

Przykład RANMAR

Z pierwszego ciągu:

u97(14606645) - u33(3168599) = 11438046

u96(16298670) - u32(15057436) = 1241234

u95(15616920) - u31(6626452) = 8990468

u94(3474722) - u30(9897761) = 10354177

u93(1183983) - u29(13996856) = 3964343

Z drugiego ciągu:

9485328

1831007

10953899

3299578

12422470

Łącząc je:

11438046-9485328 = 1952718

1241234-1831007+4096² = 16187443

8990468-10953899+4096² = 14813785

10354177-3299578 = 7054599

3964343-12422470+4096² = 8319089

• A Review of Pseudorandom Number Generators
• Program w C