RANMAR jest algorytmem opisanym przez Marsaglię i Zamana w 1987 roku.
Operację definiujemy następująco: = {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,). Jest to sekwencja x1,x2,x3,...liczb rzeczywistych, zdefiniowanych przez xn = xn-r xn-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 jest operacją mnożenia nieparzystych liczb całkowitych modulo 2k. Aby generator mógł przejść wszystkie testy, łączymy go z drugim generatorem: cn = cn-1 (7654321 / 16777216) gdzie = {if c>=d then c-d, else c-d+16777213 / 16777216 } a 16777213 = 224-3 - liczba pierwsza. Inicjujemy c0 = 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 y1,y2,y3,y4,...gdzie yn = yn-3*yn-2*yn-1 mod 179 drugi z1,z2,z3,z4,...gdzie zn = 53*zn-1 + 1 mod 169 Następnie bierzemy iloczyn elementów yn i zn, a następnie szósty bit licząc od najmłodszego: bi = {if ynzn 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+40962 = 16187443 8990468-10953899+40962 = 14813785 10354177-3299578 = 7054599 3964343-12422470+40962 = 8319089
A Review of Pseudorandom Number Generators Program w C
Przypisy
Kategoria:Generowanie liczb losowych