Zaszczepianie generatora liczb losowych w JavaScript

Czy jest możliwe zaszczepienie generatora liczb losowych (Math.random) w JavaScript?

Nie, nie jest, ale dość łatwo jest napisać własny generator, a jeszcze lepiej użyć istniejącego. Sprawdź: to powiązane pytanie .

Zobacz także blog Davida Bau, aby uzyskać więcej informacji na temat seedowania .

UWAGA: Pomimo (a raczej z powodu) zwięzłości i pozornej elegancji, algorytm ten nie jest wysokiej jakości pod względem losowości. Poszukaj np. Tych wymienionych w tej odpowiedzi, aby uzyskać lepsze wyniki.

(Pierwotnie dostosowany do sprytnego pomysłu przedstawionego w komentarzu do innej odpowiedzi).

var seed = 1;
function random() {
    var x = Math.sin(seed++) * 10000;
    return x - Math.floor(x);
}

Możesz ustawić seeddowolną liczbę, po prostu unikaj zera (lub dowolnej wielokrotności Math.PI).

Moim zdaniem elegancja tego rozwiązania wynika z braku jakichkolwiek „magicznych” liczb (oprócz 10000, co odpowiada mniej więcej minimalnej liczbie cyfr, którą należy wyrzucić, aby uniknąć nieparzystych wzorów - patrz wyniki o wartościach 10 , 100 , 1000 ). Brevity jest również miłe.

Jest nieco wolniejszy niż Math.random () (2 lub 3 razy), ale uważam, że jest tak szybki jak każde inne rozwiązanie napisane w JavaScript.

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 ³² -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 ³² , 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.

Nie, ale oto prosty generator pseudolosowy, implementacja Multiply-with-carry, którą zaadaptowałem z Wikipedii (od tego czasu został usunięty):

var m_w = 123456789;
var m_z = 987654321;
var mask = 0xffffffff;

// Takes any integer
function seed(i) {
    m_w = (123456789 + i) & mask;
    m_z = (987654321 - i) & mask;
}

// Returns number between 0 (inclusive) and 1.0 (exclusive),
// just like Math.random().
function random()
{
    m_z = (36969 * (m_z & 65535) + (m_z >> 16)) & mask;
    m_w = (18000 * (m_w & 65535) + (m_w >> 16)) & mask;
    var result = ((m_z << 16) + (m_w & 65535)) >>> 0;
    result /= 4294967296;
    return result;
}

EDYCJA: naprawiono funkcję początkową poprzez jej zresetowanie m_z
EDIT2: Naprawiono poważne błędy implementacyjne

Algorytm Antti Sykäri jest ładny i krótki. Początkowo zrobiłem odmianę, która zastąpiła JavaScript Math.random JavaScript, gdy wywołujesz Math.seed (s), ale potem Jason skomentował, że zwrócenie funkcji byłoby lepsze:

Math.seed = function(s) {
    return function() {
        s = Math.sin(s) * 10000; return s - Math.floor(s);
    };
};

// usage:
var random1 = Math.seed(42);
var random2 = Math.seed(random1());
Math.random = Math.seed(random2());

Daje to kolejną funkcjonalność, której Javascript nie ma: wiele niezależnych generatorów losowych. Jest to szczególnie ważne, jeśli chcesz mieć jednocześnie wiele powtarzalnych symulacji.

Zobacz prace Pierre'a L'Ecuyera sięgające końca lat 80. i początku lat 90. Są też inni. Samo tworzenie (pseudo) generatora liczb losowych, jeśli nie jesteś ekspertem, jest dość niebezpieczne, ponieważ istnieje wysokie prawdopodobieństwo, że wyniki nie będą statystycznie losowe lub będą miały krótki okres. Pierre (i inni) stworzyli kilka dobrych (pseudo) generatorów liczb losowych, które są łatwe do wdrożenia. Używam jednego z jego generatorów LFSR.

https://www.iro.umontreal.ca/~lecuyer/myftp/papers/handstat.pdf

Phil Troy

Łącząc niektóre z poprzednich odpowiedzi, jest to funkcja losowa, której szukasz:

Math.seed = function(s) {
    var mask = 0xffffffff;
    var m_w  = (123456789 + s) & mask;
    var m_z  = (987654321 - s) & mask;

    return function() {
      m_z = (36969 * (m_z & 65535) + (m_z >>> 16)) & mask;
      m_w = (18000 * (m_w & 65535) + (m_w >>> 16)) & mask;

      var result = ((m_z << 16) + (m_w & 65535)) >>> 0;
      result /= 4294967296;
      return result;
    }
}

var myRandomFunction = Math.seed(1234);
var randomNumber = myRandomFunction();

Napisanie własnego pseudolosowego generatora jest dość proste.

Sugestia Dave'a Scotese'a jest użyteczna, ale jak zauważyli inni, nie jest ona dość jednolicie rozłożona.

Nie dzieje się tak jednak z powodu całkowitej liczby argumentów grzechu. Jest tak po prostu z powodu zasięgu grzechu, który okazuje się być jednowymiarową projekcją koła. Jeśli zamiast tego przyjmiesz kąt koła, będzie on jednolity.

Więc zamiast sin (x) użyj arg (exp (i * x)) / (2 * PI).

Jeśli nie podoba ci się porządek liniowy, zmieszaj go nieco z xor. Faktyczny czynnik też nie ma tak wielkiego znaczenia.

Aby wygenerować n pseudolosowych liczb, można użyć kodu:

function psora(k, n) {
  var r = Math.PI * (k ^ n)
  return r - Math.floor(r)
}
n = 42; for(k = 0; k < n; k++) console.log(psora(k, n))

Należy również pamiętać, że nie można używać pseudolosowych sekwencji, gdy potrzebna jest prawdziwa entropia.

Wiele osób, które potrzebują w dzisiejszych czasach Javascript do generowania liczb losowych w JavaScript, korzysta z modułu seedrandom Davida Bau .

Math.randomnie, ale uruchomiona biblioteka rozwiązuje ten problem. Ma prawie wszystkie rozkłady, jakie możesz sobie wyobrazić, i obsługuje generowanie liczb losowych. Przykład:

ran.core.seed(0)
myDist = new ran.Dist.Uniform(0, 1)
samples = myDist.sample(1000)

Napisałem funkcję, która zwraca rozstawioną liczbę losową, używa Math.sin, aby mieć długą liczbę losową i używa zarodka do wybierania liczb z tego.

Posługiwać się :

seedRandom("k9]:2@", 15)

zwróci liczbę początkową; pierwszym parametrem jest dowolna wartość ciągu; twoje nasienie. drugim parametrem jest liczba cyfr, które powrócą.

     function seedRandom(inputSeed, lengthOfNumber){

           var output = "";
           var seed = inputSeed.toString();
           var newSeed = 0;
           var characterArray = ['0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','y','x','z','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','U','R','S','T','U','V','W','X','Y','Z','!','@','#','$','%','^','&','*','(',')',' ','[','{',']','}','|',';',':',"'",',','<','.','>','/','?','`','~','-','_','=','+'];
           var longNum = "";
           var counter = 0;
           var accumulator = 0;

           for(var i = 0; i < seed.length; i++){
                var a = seed.length - (i+1);
                for(var x = 0; x < characterArray.length; x++){
                     var tempX = x.toString();
                     var lastDigit = tempX.charAt(tempX.length-1);
                     var xOutput = parseInt(lastDigit);
                     addToSeed(characterArray[x], xOutput, a, i); 
                }                  
           }

                function addToSeed(character, value, a, i){
                     if(seed.charAt(i) === character){newSeed = newSeed + value * Math.pow(10, a)}
                }
                newSeed = newSeed.toString();

                var copy = newSeed;
           for(var i=0; i<lengthOfNumber*9; i++){
                newSeed = newSeed + copy;
                var x = Math.sin(20982+(i)) * 10000;
                var y = Math.floor((x - Math.floor(x))*10);
                longNum = longNum + y.toString()
           }

           for(var i=0; i<lengthOfNumber; i++){
                output = output + longNum.charAt(accumulator);
                counter++;
                accumulator = accumulator + parseInt(newSeed.charAt(counter));
           }
           return(output)
      }

Proste podejście do ustalonego materiału siewnego:

function fixedrandom(p){
    const seed = 43758.5453123;
    return (Math.abs(Math.sin(p)) * seed)%1;
}

Dla liczby od 0 do 100.

Number.parseInt(Math.floor(Math.random() * 100))