Rozstawiany generator liczb losowych JavaScript

150

Funkcja JavaScript Math.random()zwraca losową wartość z przedziału od 0 do 1, automatycznie wypełnianą na podstawie aktualnego czasu (podobnie jak ja wierzę w Javie). Jednak nie sądzę, aby można było ustawić sobie własne ziarno.

Jak mogę utworzyć generator liczb losowych, dla którego mogę podać własną wartość początkową, aby mógł generować powtarzalną sekwencję (pseudo) liczb losowych?

scunliffe
źródło
1
Uwaga: aby to pytanie było krótkie i skoncentrowane, podzieliłem kod zawarty w powyższym pytaniu na poniższą odpowiedź Wiki społeczności .
Ilmari Karonen
1
Zobacz także stackoverflow.com/questions/521295
Palimondo

Odpowiedzi:

124

Jedną z opcji jest http://davidbau.com/seedrandom, który jest rozwijalnym zamiennikiem Math.random () opartym na RC4 z ładnymi właściwościami.

David Bau
źródło
18
Od tego czasu seedrandom Davida Bau stał się na tyle popularny, że utrzymuje go tutaj na githubie . Szkoda, że ​​ECMAScript był tak dawno za kulisami, że takie rzeczy nie są zawarte w języku. Poważnie, bez rozstawiania !!!
Jedz w Joes
2
@EatatJoes, Szkoda i chwała JS, że jest to potrzebne i możliwe. To całkiem fajne, że możesz dołączyć jeden plik i uzyskać kompatybilne wstecz zmiany wprowadzone w obiekcie Math. Nieźle jak na 10 dni pracy, Brendan Eich.
Bruno Bronosky
2
Dla każdego, kto szuka strony npm dla tego projektu: npmjs.com/package/seedrandom
Kip
27

Jeśli nie potrzebujesz możliwości seedowania, po prostu użyj Math.random()i zbuduj wokół niej funkcje pomocnicze (np. randRange(start, end)).

Nie jestem pewien, jakiego RNG używasz, ale najlepiej go poznać i udokumentować, abyś był świadomy jego cech i ograniczeń.

Jak powiedział Starkii, Mersenne Twister to dobry PRNG, ale nie jest łatwy do wdrożenia. Jeśli chcesz to zrobić sam, spróbuj zaimplementować LCG - jest to bardzo łatwe, ma przyzwoite cechy losowości (nie tak dobre jak Mersenne Twister) i możesz użyć niektórych popularnych stałych.

EDYCJA: rozważ świetne opcje w tej odpowiedzi dla krótkich implementacji RNG, w tym opcję LCG.

function RNG(seed) {
  // LCG using GCC's constants
  this.m = 0x80000000; // 2**31;
  this.a = 1103515245;
  this.c = 12345;

  this.state = seed ? seed : Math.floor(Math.random() * (this.m - 1));
}
RNG.prototype.nextInt = function() {
  this.state = (this.a * this.state + this.c) % this.m;
  return this.state;
}
RNG.prototype.nextFloat = function() {
  // returns in range [0,1]
  return this.nextInt() / (this.m - 1);
}
RNG.prototype.nextRange = function(start, end) {
  // returns in range [start, end): including start, excluding end
  // can't modulu nextInt because of weak randomness in lower bits
  var rangeSize = end - start;
  var randomUnder1 = this.nextInt() / this.m;
  return start + Math.floor(randomUnder1 * rangeSize);
}
RNG.prototype.choice = function(array) {
  return array[this.nextRange(0, array.length)];
}

var rng = new RNG(20);
for (var i = 0; i < 10; i++)
  console.log(rng.nextRange(10, 50));

var digits = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'];
for (var i = 0; i < 10; i++)
  console.log(rng.choice(digits));

orip
źródło
2
Czy moduł nie powinien wynosić 2 ^ 31? Czytałem ten algorytm z wiki .
Trantor Liu
3
Tak więc jesteś świadomy, że nie jest to „poprawne” w tym sensie, że nie wyświetla tego, co dyktuje matematyka. Innymi słowy, język, który poradzi sobie z tymi dużymi liczbami, będzie miał inny wynik. JS dusi się na precyzji dużych liczb i ciosów (w końcu są to liczby zmiennoprzecinkowe).
DDS,
4
-1 Ta implementacja LCG this.a * this.stateprzekracza limit dokładnych liczb całkowitych w JavaScript, ponieważ prawdopodobnie spowoduje to liczbę większą niż 2 ^ 53. Rezultatem jest ograniczony zakres wydajności, a dla niektórych nasion prawdopodobnie bardzo krótki okres. Dalej, ogólnie rzecz biorąc, użycie potęgi dwa w celu muzyskania dość oczywistych wzorców, kiedy i tak wydajesz operację modułu zamiast prostego obcięcia, nie ma powodu, aby nie używać liczby pierwszej.
aaaaaaaaaaaa
22

Jeśli chcesz mieć możliwość określenia ziarna, wystarczy zamienić wywołania getSeconds()i getMinutes(). Możesz podać int i użyć połowy z tego mod 60 dla wartości sekund, a drugą połowę modulo 60, aby uzyskać drugą część.

Biorąc to pod uwagę, ta metoda wygląda jak śmieci. Wykonanie prawidłowego generowania liczb losowych jest bardzo trudne. Oczywistym problemem jest to, że zarodek liczb losowych jest oparty na sekundach i minutach. Aby odgadnąć ziarno i odtworzyć strumień liczb losowych, wystarczy wypróbować 3600 różnych kombinacji sekund i minut. Oznacza to również, że istnieje tylko 3600 różnych możliwych nasion. Można to naprawić, ale od początku byłbym podejrzliwy wobec tego RNG.

Jeśli chcesz użyć lepszego RNG, wypróbuj Mersenne Twister . Jest to dobrze przetestowany i dość solidny RNG z ogromną orbitą i doskonałą wydajnością.

EDYCJA: Naprawdę powinienem mieć rację i odnosić się do tego jako do generatora liczb pseudolosowych lub PRNG.

„Każdy, kto używa metod arytmetycznych do tworzenia liczb losowych, jest w stanie grzechu”.
                                                                                                                                                          --- John von Neumann

Starkii
źródło
1
Link do implementacji JS Mersenne Twister: math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/JAVASCRIPT/…
orip
1
@orip Czy masz źródło 3600 stanów początkowych? Mersenne Twister jest rozstawiany przez liczbę 32-bitową, więc PRNG powinien mieć 4 miliardy stanów początkowych - tylko wtedy, gdy początkowe ziarno jest naprawdę losowe.
Tobias P.
2
@TobiasP. Miałem na myśli sugestię, aby seedować za pomocą kombinacji getSeconds () i getMinutes (), 60 * 60 == 3600 możliwych stanów początkowych. Nie miałem na myśli Mersenne Twister.
orip
3
@orip Ok, nie było jasne. Mówiłeś o Mersenne Twister, aw następnym zdaniu o stanach początkowych;)
Tobias P.
2
Osoba zadająca pytanie nie wspomina, że ​​potrzebuje „odpowiedniego” generowania liczb losowych dla jakiejkolwiek aplikacji wrażliwej na kryptografię. Chociaż cała odpowiedź jest prawdziwa, tylko pierwszy akapit ma znaczenie dla zadanego pytania. Być może dodaj fragment kodu sugerowanego rozwiązania.
V. Rubinetti
12

Używam portu JavaScript Mersenne Twister: https://gist.github.com/300494 Pozwala to ręcznie ustawić ziarno. Ponadto, jak wspomniano w innych odpowiedziach, Mersenne Twister to naprawdę dobry PRNG.

Christoph Henkelmann
źródło
8

Kod, który podałeś, wygląda trochę jak Lehmer RNG . W takim przypadku 2147483647jest to największa 32-bitowa liczba całkowita 2147483647ze 48271znakiem , jest największą 32-bitową liczbą pierwszą i jest mnożnikiem pełnego okresu używanym do generowania liczb.

Jeśli to prawda, można zmodyfikować RandomNumberGenerator, aby wziąć na dodatkowym parametrem seed, a następnie ustawić this.seedsię seed; ale musiałbyś uważać, aby upewnić się, że ziarno spowoduje dobry rozkład liczb losowych (Lehmer może być taki dziwny) - ale większość nasion będzie w porządku.

mipadi
źródło
7

Poniżej znajduje się PRNG, który może być karmiony niestandardowym nasionem. Wywołanie SeedRandomzwróci losową funkcję generatora. SeedRandommożna wywołać bez argumentów w celu zapełnienia zwróconej funkcji losowej bieżącym czasem lub można ją wywołać z 1 lub 2 nieujemnymi liczbami całkowitymi jako argumentami, aby zapełnić ją tymi liczbami całkowitymi. Ze względu na dokładność punktu zmiennoprzecinkowego zaszczepienie tylko 1 wartością pozwoli na zainicjowanie generatora tylko w jednym z 2 ^ 53 różnych stanów.

limitZwracana funkcja generatora losowego przyjmuje 1 argument będący liczbą całkowitą o nazwie , limit musi mieścić się w zakresie od 1 do 4294965886, funkcja zwróci liczbę z zakresu od 0 do limit-1.

function SeedRandom(state1,state2){
    var mod1=4294967087
    var mul1=65539
    var mod2=4294965887
    var mul2=65537
    if(typeof state1!="number"){
        state1=+new Date()
    }
    if(typeof state2!="number"){
        state2=state1
    }
    state1=state1%(mod1-1)+1
    state2=state2%(mod2-1)+1
    function random(limit){
        state1=(state1*mul1)%mod1
        state2=(state2*mul2)%mod2
        if(state1<limit && state2<limit && state1<mod1%limit && state2<mod2%limit){
            return random(limit)
        }
        return (state1+state2)%limit
    }
    return random
}

Przykładowe zastosowanie:

var generator1=SeedRandom() //Seed with current time
var randomVariable=generator1(7) //Generate one of the numbers [0,1,2,3,4,5,6]
var generator2=SeedRandom(42) //Seed with a specific seed
var fixedVariable=generator2(7) //First value of this generator will always be
                                //1 because of the specific seed.

Ten generator ma następujące właściwości:

  • Ma około 2 ^ 64 różnych możliwych stanów wewnętrznych.
  • Ma okres około 2 ^ 63, znacznie więcej niż ktokolwiek realnie kiedykolwiek potrzebowałby w programie JavaScript.
  • Ponieważ modwartości są liczbami pierwszymi, nie ma prostego wzoru na wyjściu, bez względu na wybraną granicę. W odróżnieniu od niektórych prostszych PRNG, które wykazują pewne dość systematyczne wzorce.
  • Odrzuca niektóre wyniki, aby uzyskać doskonałą dystrybucję bez względu na limit.
  • Jest stosunkowo wolny, na mojej maszynie działa około 10 000 000 razy na sekundę.
aaaaaaaaaaaa
źródło
2
Dlaczego to tworzy wzór? for (var i = 0; i < 400; i++) { console.log("input: (" + i * 245 + ", " + i * 553 + ") | output: " + SeedRandom(i * 245, i * 553)(20)); }
Timothy Kanski
@TimothyKanski Ponieważ używasz go źle. Nie jestem ekspertem, ale dzieje się tak, ponieważ inicjalizujesz generator w każdej iteracji, widzisz tylko jego pierwszą wartość na podstawie ziarna, a NIE iterujesz na kolejnych liczbach generatora. Uważam, że stanie się to w każdym PRNG, który nie haszuje nasion w określonym przedziale czasu.
bryc
5

Jeśli programujesz w Typescript, zaadaptowałem implementację Mersenne Twister, która została wprowadzona w odpowiedzi Christopha Henkelmanna do tego wątku, jako klasę maszynopisu:

/**
 * copied almost directly from Mersenne Twister implementation found in https://gist.github.com/banksean/300494
 * all rights reserved to him.
 */
export class Random {
    static N = 624;
    static M = 397;
    static MATRIX_A = 0x9908b0df;
    /* constant vector a */
    static UPPER_MASK = 0x80000000;
    /* most significant w-r bits */
    static LOWER_MASK = 0x7fffffff;
    /* least significant r bits */

    mt = new Array(Random.N);
    /* the array for the state vector */
    mti = Random.N + 1;
    /* mti==N+1 means mt[N] is not initialized */

    constructor(seed:number = null) {
        if (seed == null) {
            seed = new Date().getTime();
        }

        this.init_genrand(seed);
    }

    private init_genrand(s:number) {
        this.mt[0] = s >>> 0;
        for (this.mti = 1; this.mti < Random.N; this.mti++) {
            var s = this.mt[this.mti - 1] ^ (this.mt[this.mti - 1] >>> 30);
            this.mt[this.mti] = (((((s & 0xffff0000) >>> 16) * 1812433253) << 16) + (s & 0x0000ffff) * 1812433253)
                + this.mti;
            /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
            /* In the previous versions, MSBs of the seed affect   */
            /* only MSBs of the array mt[].                        */
            /* 2002/01/09 modified by Makoto Matsumoto             */
            this.mt[this.mti] >>>= 0;
            /* for >32 bit machines */
        }
    }

    /**
     * generates a random number on [0,0xffffffff]-interval
     * @private
     */
    private _nextInt32():number {
        var y:number;
        var mag01 = new Array(0x0, Random.MATRIX_A);
        /* mag01[x] = x * MATRIX_A  for x=0,1 */

        if (this.mti >= Random.N) { /* generate N words at one time */
            var kk:number;

            if (this.mti == Random.N + 1)   /* if init_genrand() has not been called, */
                this.init_genrand(5489);
            /* a default initial seed is used */

            for (kk = 0; kk < Random.N - Random.M; kk++) {
                y = (this.mt[kk] & Random.UPPER_MASK) | (this.mt[kk + 1] & Random.LOWER_MASK);
                this.mt[kk] = this.mt[kk + Random.M] ^ (y >>> 1) ^ mag01[y & 0x1];
            }
            for (; kk < Random.N - 1; kk++) {
                y = (this.mt[kk] & Random.UPPER_MASK) | (this.mt[kk + 1] & Random.LOWER_MASK);
                this.mt[kk] = this.mt[kk + (Random.M - Random.N)] ^ (y >>> 1) ^ mag01[y & 0x1];
            }
            y = (this.mt[Random.N - 1] & Random.UPPER_MASK) | (this.mt[0] & Random.LOWER_MASK);
            this.mt[Random.N - 1] = this.mt[Random.M - 1] ^ (y >>> 1) ^ mag01[y & 0x1];

            this.mti = 0;
        }

        y = this.mt[this.mti++];

        /* Tempering */
        y ^= (y >>> 11);
        y ^= (y << 7) & 0x9d2c5680;
        y ^= (y << 15) & 0xefc60000;
        y ^= (y >>> 18);

        return y >>> 0;
    }

    /**
     * generates an int32 pseudo random number
     * @param range: an optional [from, to] range, if not specified the result will be in range [0,0xffffffff]
     * @return {number}
     */
    nextInt32(range:[number, number] = null):number {
        var result = this._nextInt32();
        if (range == null) {
            return result;
        }

        return (result % (range[1] - range[0])) + range[0];
    }

    /**
     * generates a random number on [0,0x7fffffff]-interval
     */
    nextInt31():number {
        return (this._nextInt32() >>> 1);
    }

    /**
     * generates a random number on [0,1]-real-interval
     */
    nextNumber():number {
        return this._nextInt32() * (1.0 / 4294967295.0);
    }

    /**
     * generates a random number on [0,1) with 53-bit resolution
     */
    nextNumber53():number {
        var a = this._nextInt32() >>> 5, b = this._nextInt32() >>> 6;
        return (a * 67108864.0 + b) * (1.0 / 9007199254740992.0);
    }
}

możesz użyć go w następujący sposób:

var random = new Random(132);
random.nextInt32(); //return a pseudo random int32 number
random.nextInt32([10,20]); //return a pseudo random int in range [10,20]
random.nextNumber(); //return a a pseudo random number in range [0,1]

sprawdź źródło, aby znaleźć więcej metod.

bennyl
źródło
0

Uwaga: ten kod został pierwotnie zawarty w powyższym pytaniu. Aby pytanie było krótkie i skoncentrowane, przeniosłem je do odpowiedzi na Wiki społeczności.

Zauważyłem, że ten kod się kręci i wydaje się, że działa dobrze, aby uzyskać liczbę losową, a następnie użyć ziarna, ale nie jestem do końca pewien, jak działa logika (np. Skąd pochodzą liczby 2345678901, 48271 i 2147483647).

function nextRandomNumber(){
  var hi = this.seed / this.Q;
  var lo = this.seed % this.Q;
  var test = this.A * lo - this.R * hi;
  if(test > 0){
    this.seed = test;
  } else {
    this.seed = test + this.M;
  }
  return (this.seed * this.oneOverM);
}

function RandomNumberGenerator(){
  var d = new Date();
  this.seed = 2345678901 + (d.getSeconds() * 0xFFFFFF) + (d.getMinutes() * 0xFFFF);
  this.A = 48271;
  this.M = 2147483647;
  this.Q = this.M / this.A;
  this.R = this.M % this.A;
  this.oneOverM = 1.0 / this.M;
  this.next = nextRandomNumber;
  return this;
}

function createRandomNumber(Min, Max){
  var rand = new RandomNumberGenerator();
  return Math.round((Max-Min) * rand.next() + Min);
}

//Thus I can now do:
var letters = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'];
var numbers = ['1','2','3','4','5','6','7','8','9','10'];
var colors = ['red','orange','yellow','green','blue','indigo','violet'];
var first = letters[createRandomNumber(0, letters.length)];
var second = numbers[createRandomNumber(0, numbers.length)];
var third = colors[createRandomNumber(0, colors.length)];

alert("Today's show was brought to you by the letter: " + first + ", the number " + second + ", and the color " + third + "!");

/*
  If I could pass my own seed into the createRandomNumber(min, max, seed);
  function then I could reproduce a random output later if desired.
*/
Ilmari Karonen
źródło
3
Wow, funkcje RandomNumberGeneratori nextRandomNumberfaktycznie sięgają roku 1996. Przypuszczalnie jest to RNG Lehmer / LCG. Używa sprytnych działań matematycznych do wykonywania arytmetyki modulo na 32-bitowych liczbach całkowitych, które w przeciwnym razie byłyby zbyt małe, aby zawierały jakieś wartości pośrednie. Rzecz w tym, że JavaScript nie implementuje 32-bitowych liczb całkowitych, ale 64-bitowe liczby zmiennoprzecinkowe, a ponieważ dzielenie nie jest dzieleniem całkowitoliczbowym, tak jak ten kod zakłada, że ​​wynik nie jest generatorem Lehmera. Daje pewne wyniki, które wydają się przypadkowe, ale gwarancje generatora Lehmera nie mają zastosowania.
aaaaaaaaaaaa
1
Ta createRandomNumberfunkcja jest późniejszym dodatkiem, robi prawie wszystko źle, przede wszystkim tworzy instancję nowego RNG za każdym razem, gdy jest wywoływana, co oznacza, że ​​wywołania w krótkich odstępach czasu będą używać tego samego float. W podanym kodzie jest prawie niemożliwe 'a'sparowanie z czymkolwiek innym niż '1'i 'red'.
aaaaaaaaaaaa
-2

OK, oto rozwiązanie, na które się zdecydowałem.

Najpierw utwórz wartość początkową za pomocą funkcji „newseed ()”. Następnie przekazujesz wartość ziarna do funkcji „srandom ()”. Na koniec funkcja „srandom ()” zwraca pseudolosową wartość z przedziału od 0 do 1.

Najważniejsze jest to, że wartość ziarna jest przechowywana w tablicy. Gdyby była to po prostu liczba całkowita lub zmiennoprzecinkowa, wartość byłaby nadpisywana przy każdym wywołaniu funkcji, ponieważ wartości liczb całkowitych, zmiennoprzecinkowych, łańcuchów itd. Są przechowywane bezpośrednio na stosie, a nie tylko wskaźniki, jak w przypadku tablic i inne obiekty. W ten sposób wartość ziarna może pozostać trwała.

Wreszcie, możliwe jest zdefiniowanie funkcji „srandom ()” w taki sposób, że jest to metoda obiektu „Math”, ale pozostawię to Tobie do rozgryzienia. ;)

Powodzenia!

JavaScript:

// Global variables used for the seeded random functions, below.
var seedobja = 1103515245
var seedobjc = 12345
var seedobjm = 4294967295 //0x100000000

// Creates a new seed for seeded functions such as srandom().
function newseed(seednum)
{
    return [seednum]
}

// Works like Math.random(), except you provide your own seed as the first argument.
function srandom(seedobj)
{
    seedobj[0] = (seedobj[0] * seedobja + seedobjc) % seedobjm
    return seedobj[0] / (seedobjm - 1)
}

// Store some test values in variables.
var my_seed_value = newseed(230951)
var my_random_value_1 = srandom(my_seed_value)
var my_random_value_2 = srandom(my_seed_value)
var my_random_value_3 = srandom(my_seed_value)

// Print the values to console. Replace "WScript.Echo()" with "alert()" if inside a Web browser.
WScript.Echo(my_random_value_1)
WScript.Echo(my_random_value_2)
WScript.Echo(my_random_value_3)

Lua 4 (moje osobiste środowisko docelowe):

-- Global variables used for the seeded random functions, below.
seedobja = 1103515.245
seedobjc = 12345
seedobjm = 4294967.295 --0x100000000

-- Creates a new seed for seeded functions such as srandom().
function newseed(seednum)
    return {seednum}
end

-- Works like random(), except you provide your own seed as the first argument.
function srandom(seedobj)
    seedobj[1] = mod(seedobj[1] * seedobja + seedobjc, seedobjm)
    return seedobj[1] / (seedobjm - 1)
end

-- Store some test values in variables.
my_seed_value = newseed(230951)
my_random_value_1 = srandom(my_seed_value)
my_random_value_2 = srandom(my_seed_value)
my_random_value_3 = srandom(my_seed_value)

-- Print the values to console.
print(my_random_value_1)
print(my_random_value_2)
print(my_random_value_3)
posfan12
źródło
PS - Nie jestem jeszcze zaznajomiony z przepełnieniem stosu, ale dlaczego posty nie są uporządkowane chronologicznie?
posfan12
Cześć @ posfan12 - odpowiedzi na pytania są zwykle uporządkowane według „głosów pozytywnych”, tak że „krem wznosi się na szczyt”. Jednak aby zapewnić rzetelne postrzeganie odpowiedzi z tym samym wynikiem, są one wyświetlane w kolejności losowej. Ponieważ to było pierwotnie moje pytanie ;-) Na pewno wkrótce to sprawdzę. Jeśli ja (lub inni) uznam tę odpowiedź za pomocną, zagłosujemy za nią, a jeśli uznam ją za „prawidłową”, zobaczysz również zielony znacznik wyboru dodany do tej odpowiedzi. - Witamy w StackOverflow!
scunliffe
2
-1 Ta implementacja LCG seedobj[0] * seedobjaprzekracza limit dokładnych liczb całkowitych w JavaScript, ponieważ prawdopodobnie spowoduje to liczbę większą niż 2 ^ 53. Rezultatem jest ograniczony zakres wydajności, a dla niektórych nasion prawdopodobnie bardzo krótki okres.
aaaaaaaaaaaa