RANMAR
RANMAR jest algorytmem opisanym przez Marsaglię i Zamana[1] 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
[edytuj | edytuj kod]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
[edytuj | edytuj kod]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
[edytuj | edytuj kod]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
Przypisy
[edytuj | edytuj kod]- ↑ Toward a universal random number generator. [dostęp 2010-06-10]. [zarchiwizowane z tego adresu (2010-06-10)].