Zaimplementowałem wiele dobrych, krótkich i szybkich funkcji generatora liczb pseudolosowych (PRNG) w zwykłym JavaScript. Wszystkie z nich można wysiać i zapewnić dobrą jakość liczb.
Przede wszystkim zadbaj o prawidłową inicjalizację swoich PRNG. Większość poniższych generatorów nie ma wbudowanej procedury generowania nasion (dla uproszczenia), ale akceptuje jedną lub więcej 32-bitowych wartości jako stan początkowy PRNG. Podobne nasiona (np. Proste ziarno 1 i 2) mogą powodować korelacje w słabszych PRNG, w wyniku czego dane wyjściowe mają podobne właściwości (takie jak losowo generowane poziomy są podobne). Aby tego uniknąć, najlepszą praktyką jest inicjowanie PRNG z dobrze rozłożonym nasieniem.
Na szczęście funkcje skrótu są bardzo dobre w generowaniu zarodków PRNG z krótkich ciągów. Dobra funkcja skrótu generuje bardzo różne wyniki, nawet gdy dwa ciągi znaków są podobne. Oto przykład oparty na funkcji mieszania MurmurHash3:
function xmur3(str) {
for(var i = 0, h = 1779033703 ^ str.length; i < str.length; i++)
h = Math.imul(h ^ str.charCodeAt(i), 3432918353),
h = h << 13 | h >>> 19;
return function() {
h = Math.imul(h ^ h >>> 16, 2246822507);
h = Math.imul(h ^ h >>> 13, 3266489909);
return (h ^= h >>> 16) >>> 0;
}
}
Każde kolejne wywołanie funkcji powrotnej z xmur3produkcją nowego „Random” 32-bitową wartość skrótu, który będzie używany jako materiał siewny w PRNG. Oto jak możesz go użyć:
// Create xmur3 state:
var seed = xmur3("apples");
// Output four 32-bit hashes to provide the seed for sfc32.
var rand = sfc32(seed(), seed(), seed(), seed());
// Output one 32-bit hash to provide the seed for mulberry32.
var rand = mulberry32(seed());
// Obtain sequential random numbers like so:
rand();
rand();
Alternatywnie, po prostu wybierz dane zastępcze, którymi chcesz wypełnić ziarno, i przesuń generator kilka razy (12-20 iteracji), aby dokładnie wymieszać stan początkowy. Jest to często widoczne w referencyjnych implementacjach PRNG, ale ogranicza liczbę stanów początkowych.
var seed = 1337 ^ 0xDEADBEEF; // 32-bit seed with optional XOR value
// Pad seed with Phi, Pi and E.
// https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number
var rand = sfc32(0x9E3779B9, 0x243F6A88, 0xB7E15162, seed);
for (var i = 0; i < 15; i++) rand();
Dane wyjściowe tych funkcji PRNG generują dodatnią liczbę 32-bitową (od 0 do 2 32 -1), która jest następnie przekształcana na liczbę zmiennoprzecinkową między 0-1 (0 włącznie, 1 wyłącznie) równoważną Math.random(), jeśli chcesz liczb losowych określonego zakresu, przeczytaj ten artykuł na MDN . Jeśli chcesz tylko surowych bitów, po prostu usuń ostatnią operację dzielenia.
Należy również zwrócić uwagę na ograniczenia JS. Liczby mogą reprezentować tylko liczby całkowite do 53-bitowej rozdzielczości. W przypadku operacji bitowych liczba ta jest zmniejszana do 32. Utrudnia to implementację algorytmów napisanych w C lub C ++, które używają liczb 64-bitowych. Przeniesienie 64-bitowego kodu wymaga podkładek, które mogą drastycznie zmniejszyć wydajność. Ze względu na prostotę i wydajność rozważałem tylko algorytmy wykorzystujące matematykę 32-bitową, ponieważ jest ona bezpośrednio kompatybilna z JS.
Teraz przejdźmy do generatorów. (Utrzymuję pełną listę z odnośnikami tutaj )
sfc32 (prosty szybki licznik)
sfc32 jest częścią pakietu do testowania liczb losowych PractRand (który oczywiście przechodzi). sfc32 ma stan 128-bitowy i jest bardzo szybki w JS.
function sfc32(a, b, c, d) {
return function() {
a >>>= 0; b >>>= 0; c >>>= 0; d >>>= 0;
var t = (a + b) | 0;
a = b ^ b >>> 9;
b = c + (c << 3) | 0;
c = (c << 21 | c >>> 11);
d = d + 1 | 0;
t = t + d | 0;
c = c + t | 0;
return (t >>> 0) / 4294967296;
}
}
Morwa32
Mulberry32 jest prostym generatorem ze stanem 32-bitowym, ale jest niezwykle szybki i ma dobrą jakość (autor twierdzi, że przeszedł wszystkie testy pakietu testowego gjrand i ma pełny okres 32 , ale nie zweryfikowałem).
function mulberry32(a) {
return function() {
var t = a += 0x6D2B79F5;
t = Math.imul(t ^ t >>> 15, t | 1);
t ^= t + Math.imul(t ^ t >>> 7, t | 61);
return ((t ^ t >>> 14) >>> 0) / 4294967296;
}
}
Poleciłbym to, jeśli potrzebujesz tylko prostego, ale przyzwoitego PRNG i nie potrzebujesz miliardów liczb losowych (patrz problem z urodzinami ).
xoshiro128 **
Od maja 2018 r. Xoshiro128 ** jest nowym członkiem rodziny Xorshift autorstwa Vigna / Blackman (który napisał również xoroshiro, który jest używany w Chrome). Jest to najszybszy generator oferujący stan 128-bitowy.
function xoshiro128ss(a, b, c, d) {
return function() {
var t = b << 9, r = a * 5; r = (r << 7 | r >>> 25) * 9;
c ^= a; d ^= b;
b ^= c; a ^= d; c ^= t;
d = d << 11 | d >>> 21;
return (r >>> 0) / 4294967296;
}
}
Autorzy twierdzą, że dobrze przechodzi testy losowości ( choć z zastrzeżeniami ). Inni badacze zauważyli, że niektóre testy w TestU01 nie udają się (szczególnie LinearComp i BinaryRank). W praktyce nie powinno to powodować problemów, gdy używane są zmiennoprzecinkowe (takie jak te implementacje), ale może powodować problemy, jeśli polegasz na surowych niskich bitach.
JSF (mały post Jenkinsa)
To jest JSF lub „smallprng” Boba Jenkinsa (2007), facet, który stworzył ISAAC i SpookyHash . To przechodzi testy PractRand i powinny być dość szybko, choć nie tak szybko jak SFC.
function jsf32(a, b, c, d) {
return function() {
a |= 0; b |= 0; c |= 0; d |= 0;
var t = a - (b << 27 | b >>> 5) | 0;
a = b ^ (c << 17 | c >>> 15);
b = c + d | 0;
c = d + t | 0;
d = a + t | 0;
return (d >>> 0) / 4294967296;
}
}
LCG (alias Lehmer / Park-Miller RNG lub MCG)
LCG jest niezwykle szybki i prosty, ale jakość jego losowości jest tak niska, że niewłaściwe użycie może faktycznie powodować błędy w twoim programie! Niemniej jednak jest znacznie lepszy niż niektóre odpowiedzi sugerujące użycie Math.sinlub Math.PI! Jest to jednak jedna linijka, co jest miłe :).
var LCG=s=>()=>(2**31-1&(s=Math.imul(48271,s)))/2**31;
Ta implementacja nazywa się minimalnym standardowym RNG, jak zaproponował Park – Miller w 1988 i 1993 r. I zaimplementowano w C ++ 11 as minstd_rand. Należy pamiętać, że stan jest 31-bitowy (31 bitów daje 2 miliardy możliwych stanów, 32 bity daje dwa razy więcej). Jest to rodzaj PRNG, który inni próbują zastąpić!
Będzie działał, ale nie użyłbym go, chyba że naprawdę potrzebujesz szybkości i nie zależy ci na jakości losowości (co w ogóle jest losowe?). Idealne do gry jam, demo lub coś takiego. LCG cierpią na korelacje nasion, więc najlepiej odrzucić pierwszy wynik LCG. A jeśli nalegasz na użycie LCG, dodanie wartości przyrostowej może poprawić wyniki, ale prawdopodobnie jest to ćwiczenie bezcelowe, gdy istnieją znacznie lepsze opcje.
Wydaje się, że istnieją inne mnożniki oferujące stan 32-bitowy (zwiększona przestrzeń stanu):
var LCG=s=>()=>(s=Math.imul(741103597,s)>>>0)/2**32;
var LCG=s=>()=>(s=Math.imul(1597334677,s)>>>0)/2**32;
Te wartości LCG pochodzą z: P. L'Ecuyer: Tabela liniowych kongruencjalnych generatorów o różnych rozmiarach i dobrej strukturze sieci, 30 kwietnia 1997 r.