Seedable JavaScript Zufallszahlengenerator

149

Die JavaScript- Math.random()Funktion gibt einen zufälligen Wert zwischen 0 und 1 zurück, der basierend auf der aktuellen Zeit automatisch gesetzt wird (ähnlich wie Java, glaube ich). Ich glaube jedoch nicht, dass es eine Möglichkeit gibt, einen eigenen Samen dafür zu setzen.

Wie kann ich einen Zufallszahlengenerator erstellen, für den ich meinen eigenen Startwert angeben kann, damit er eine wiederholbare Folge von (Pseudo-) Zufallszahlen erzeugt?

scunliffe
quelle
1
Hinweis: Um diese Frage kurz und konzentriert zu halten, habe ich den Code in der obigen Frage in eine Community-Wiki-Antwort unten aufgeteilt.
Ilmari Karonen
1
Siehe auch stackoverflow.com/questions/521295
Palimondo

Antworten:

123

Eine Option ist http://davidbau.com/seedrandom , ein setzbarer RC4-basierter Math.random () - Drop-In-Ersatz mit netten Eigenschaften.

David Bau
quelle
18
David Baus Seedrandom ist seitdem so populär geworden, dass er es hier auf Github pflegt . Es ist eine Schande, dass ECMAScript so lange im Hintergrund war, dass solche Dinge nicht in der Sprache enthalten sind. Im Ernst, keine Aussaat !!!
Essen Sie bei Joes
2
@EatatJoes, es ist sowohl die Schande als auch der Ruhm von JS, dass dies sowohl gebraucht als auch möglich ist. Es ist ziemlich cool, dass Sie eine Datei einfügen und abwärtskompatible Änderungen am Math-Objekt erhalten können. Nicht schlecht für 10 Arbeitstage, Brendan Eich.
Bruno Bronosky
2
Für alle, die nach der npm-Seite für dieses Projekt suchen
Kip
27

Wenn Sie die Seeding-Funktion nicht benötigen, verwenden Math.random()und bauen Sie einfach Hilfsfunktionen darum herum (z. B. randRange(start, end)).

Ich bin nicht sicher, welches RNG Sie verwenden, aber es ist am besten, es zu kennen und zu dokumentieren, damit Sie sich seiner Eigenschaften und Einschränkungen bewusst sind.

Wie Starkii sagte, ist Mersenne Twister ein gutes PRNG, aber es ist nicht einfach zu implementieren. Wenn Sie es selbst tun möchten, versuchen Sie, ein LCG zu implementieren - es ist sehr einfach, hat anständige Zufallsqualitäten (nicht so gut wie Mersenne Twister) und Sie können einige der gängigen Konstanten verwenden.

BEARBEITEN: Berücksichtigen Sie bei dieser Antwort die großartigen Optionen für kurze RNG-Implementierungen, einschließlich einer LCG-Option.

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
quelle
2
Sollte der Modul nicht 2 ^ 31 sein? Ich habe diesen Algorithmus aus dem Wiki gelesen .
Trantor Liu
3
Nur damit Sie sich bewusst sind, ist dies nicht "richtig" in dem Sinne, dass es nicht ausgibt, was die Mathematik vorschreibt. Mit anderen Worten, eine Sprache, die mit diesen großen Zahlen umgehen kann, hat ein anderes Ergebnis. JS drosselt an den großen Zahlen und hackt die Präzision (sie sind schließlich Floats).
DDS
4
-1 Diese LCG-Implementierung überschreitet die Grenze für exakte Ganzzahlen in JavaScript, da dies this.a * this.statewahrscheinlich zu einer Zahl größer als 2 ^ 53 führt. Das Ergebnis ist ein begrenzter Ausgabebereich und für einige Samen möglicherweise ein sehr kurzer Zeitraum. mWenn Sie im Allgemeinen eine Zweierpotenz verwenden, um einige ziemlich offensichtliche Muster zu erhalten, gibt es keinen Grund, keine Primzahl zu verwenden, wenn Sie eine Moduloperation anstelle einer einfachen Kürzung aufwenden.
aaaaaaaaaaaa
22

Wenn Sie den Startwert angeben möchten, müssen Sie nur die Aufrufe von getSeconds()und ersetzen getMinutes(). Sie könnten ein int übergeben und die Hälfte davon mod 60 für den Sekundenwert und die andere Hälfte modulo 60 verwenden, um Ihnen den anderen Teil zu geben.

Davon abgesehen sieht diese Methode wie Müll aus. Die richtige Erzeugung von Zufallszahlen ist sehr schwierig. Das offensichtliche Problem dabei ist, dass der Zufallszahlen-Seed auf Sekunden und Minuten basiert. Um den Startwert zu erraten und Ihren Zufallszahlenstrom neu zu erstellen, müssen Sie nur 3600 verschiedene Sekunden- und Minutenkombinationen ausprobieren. Dies bedeutet auch, dass es nur 3600 verschiedene mögliche Samen gibt. Dies ist korrigierbar, aber ich wäre von Anfang an misstrauisch gegenüber diesem RNG.

Wenn Sie ein besseres RNG verwenden möchten, probieren Sie den Mersenne Twister . Es ist ein gut getestetes und ziemlich robustes RNG mit einer riesigen Umlaufbahn und einer hervorragenden Leistung.

EDIT: Ich sollte wirklich korrekt sein und dies als Pseudo-Zufallszahlengenerator oder PRNG bezeichnen.

"Jeder, der arithmetische Methoden verwendet, um Zufallszahlen zu erzeugen, ist in einem Zustand der Sünde."
                                                                                                                                                          --- John von Neumann

Starkii
quelle
1
Ein Link zu JS-Implementierungen von Mersenne Twister: math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/JAVASCRIPT/…
orip
1
@orip Haben Sie eine Quelle für die 3600 Anfangszustände? Mersenne Twister wird mit einer 32-Bit-Zahl geimpft, daher sollte der PRNG 4 Milliarden Anfangszustände haben - nur wenn der Anfangssamen wirklich zufällig ist.
Tobias P.
2
@TobiasP. Ich bezog mich auf den Vorschlag, mit einer Kombination aus getSeconds () und getMinutes () zu säen, 60 * 60 == 3600 mögliche Anfangszustände. Ich bezog mich nicht auf Mersenne Twister.
Orip
3
@orip Ok, war nicht klar. Sie haben über Mersenne Twister und im nächsten Satz über Anfangszustände gesprochen;)
Tobias P.
2
Der Fragesteller erwähnt nicht, dass er für jede Art von kryptografisch sensibler Anwendung eine "richtige" Zufallszahlengenerierung benötigt. Während die gesamte Antwort wahr ist, ist nur der erste Absatz für die gestellte Frage tatsächlich relevant. Fügen Sie möglicherweise einen Codeausschnitt der vorgeschlagenen Lösung hinzu.
V. Rubinetti
12

Ich verwende einen JavaScript-Port des Mersenne Twister: https://gist.github.com/300494 Damit können Sie den Startwert manuell festlegen. Wie in anderen Antworten erwähnt, ist der Mersenne Twister auch ein wirklich guter PRNG.

Christoph Henkelmann
quelle
8

Der Code, den Sie aufgelistet haben, sieht aus wie ein Lehmer RNG . Wenn dies der Fall ist, 2147483647ist dies die größte 32-Bit-Ganzzahl mit Vorzeichen, 2147483647die größte 32-Bit-Primzahl und 48271ein Vollzeitmultiplikator, der zum Generieren der Zahlen verwendet wird.

Wenn dies der Fall ist, können Sie ändern RandomNumberGeneratorin einem zusätzlichen Parameter zu nehmen seed, und stellen Sie dann this.seedauf seed; Aber Sie müssten vorsichtig sein, um sicherzustellen, dass der Samen zu einer guten Verteilung der Zufallszahlen führt (Lehmer kann so seltsam sein) - aber die meisten Samen sind in Ordnung.

Mipadi
quelle
7

Das Folgende ist ein PRNG, dem ein benutzerdefiniertes Saatgut zugeführt werden kann. Beim Aufrufen SeedRandomwird eine Zufallsgeneratorfunktion zurückgegeben. SeedRandomkann ohne Argumente aufgerufen werden, um die zurückgegebene Zufallsfunktion mit der aktuellen Zeit zu setzen, oder es kann entweder mit 1 oder 2 nicht negativen inters als Argumente aufgerufen werden, um sie mit diesen ganzen Zahlen zu setzen. Aufgrund der Gleitkommagenauigkeit kann beim Seeding mit nur 1 Wert der Generator nur in einen von 2 ^ 53 verschiedenen Zuständen versetzt werden.

Die zurückgegebene Zufallsgeneratorfunktion verwendet 1 benanntes Ganzzahlargument limit. Der Grenzwert muss im Bereich von 1 bis 4294965886 liegen. Die Funktion gibt eine Zahl im Bereich von 0 bis Grenzwert 1 zurück.

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
}

Anwendungsbeispiel:

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.

Dieser Generator weist folgende Eigenschaften auf:

  • Es hat ungefähr 2 ^ 64 verschiedene mögliche innere Zustände.
  • Es hat eine Periode von ungefähr 2 ^ 63, viel mehr, als irgendjemand jemals realistisch in einem JavaScript-Programm brauchen wird.
  • Da die modWerte Primzahlen sind, gibt es kein einfaches Muster in der Ausgabe, unabhängig von der gewählten Grenze. Dies ist anders als bei einigen einfacheren PRNGs, die einige recht systematische Muster aufweisen.
  • Einige Ergebnisse werden verworfen, um unabhängig vom Grenzwert eine perfekte Verteilung zu erzielen.
  • Es ist relativ langsam und läuft auf meinem Computer ungefähr 10 000 000 Mal pro Sekunde.
aaaaaaaaaaaa
quelle
2
Warum erzeugt dies ein Muster? for (var i = 0; i < 400; i++) { console.log("input: (" + i * 245 + ", " + i * 553 + ") | output: " + SeedRandom(i * 245, i * 553)(20)); }
Timothy Kanski
@ TimothyKanski Weil du es falsch benutzt. Ich bin kein Experte, aber dies tritt auf, weil Sie den Generator bei jeder Iteration initialisieren, nur seinen ersten Wert basierend auf dem Startwert sehen und NICHT die nachfolgenden Zahlen des Generators iterieren. Ich glaube, dass dies in jedem PRNG passieren wird, das den Startwert nicht über das angegebene Intervall hinweg hasht.
Bryc
5

Wenn Sie in Typescript programmieren, habe ich die Mersenne Twister-Implementierung angepasst, die in Christoph Henkelmanns Antwort auf diesen Thread als Typoskript-Klasse enthalten war:

/**
 * 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);
    }
}

Sie können es dann wie folgt verwenden:

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]

Überprüfen Sie die Quelle auf weitere Methoden.

Bennyl
quelle
0

Hinweis: Dieser Code war ursprünglich in der obigen Frage enthalten. Um die Frage kurz und konzentriert zu halten, habe ich sie in diese Antwort des Community-Wikis verschoben.

Ich habe festgestellt, dass dieser Code herumwirbelt, und es scheint gut zu funktionieren, um eine Zufallszahl zu erhalten und anschließend den Startwert zu verwenden, aber ich bin mir nicht ganz sicher, wie die Logik funktioniert (z. B. woher die Zahlen 2345678901, 48271 und 2147483647 stammen).

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
quelle
3
Wow, die RandomNumberGeneratorund nextRandomNumberFunktionen stammen tatsächlich aus dem Jahr 1996. Es soll sich um ein Lehmer / LCG RNG handeln. Es verwendet einige clevere Mathematik, um Modulo-Arithmetik für 32-Bit-Ganzzahlen durchzuführen, die sonst zu klein wären, um einige Zwischenwerte zu enthalten. Die Sache ist, dass JavaScript keine 32-Bit-Ganzzahlen implementiert, sondern 64-Bit-Gleitkommazahlen, und da die Division keine Ganzzahldivision ist, wie dieser Code voraussetzt, ist das Ergebnis kein Lehmer-Generator. Es führt zwar zu zufälligen Ergebnissen, die Garantien eines Lehmer-Generators gelten jedoch nicht.
aaaaaaaaaaaa
1
Die createRandomNumberFunktion ist eine spätere Ergänzung, sie macht so ziemlich alles falsch, insbesondere instanziiert sie jedes Mal ein neues RNG, wenn sie aufgerufen wird, was bedeutet, dass Aufrufe in schneller Folge alle denselben Float verwenden. In dem gegebenen Code ist es fast unmöglich 'a', mit etwas anderem als '1'und gepaart zu werden 'red'.
aaaaaaaaaaaa
-2

OK, hier ist die Lösung, für die ich mich entschieden habe.

Zuerst erstellen Sie einen Startwert mit der Funktion "newseed ()". Anschließend übergeben Sie den Startwert an die Funktion "srandom ()". Schließlich gibt die Funktion "srandom ()" einen Pseudozufallswert zwischen 0 und 1 zurück.

Das entscheidende Bit ist, dass der Startwert in einem Array gespeichert wird. Wenn es einfach eine Ganzzahl oder ein Gleitkommawert wäre, würde der Wert bei jedem Aufruf der Funktion überschrieben, da die Werte von Ganzzahlen, Gleitkommazahlen, Zeichenfolgen usw. direkt im Stapel gespeichert werden und nicht nur die Zeiger, wie im Fall von Arrays und andere Objekte. Somit ist es möglich, dass der Wert des Samens persistent bleibt.

Schließlich ist es möglich, die Funktion "srandom ()" so zu definieren, dass es sich um eine Methode des "Math" -Objekts handelt, aber das überlasse ich Ihnen, um es herauszufinden. ;)

Viel Glück!

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 (meine persönliche Zielumgebung):

-- 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
quelle
PS: Ich bin noch nicht so vertraut mit Stack Overflow, aber warum sind die Beiträge nicht in chronologischer Reihenfolge?
Posfan12
Hi @ posfan12 - Antworten auf Fragen werden normalerweise in der Reihenfolge nach "Upvotes" aufgelistet, sodass die "Creme nach oben steigt". Um jedoch eine faire Anzeige der Antworten mit derselben Punktzahl zu gewährleisten, werden sie in zufälliger Reihenfolge angezeigt. Da dies ursprünglich meine Frage war ;-) Ich werde es auf jeden Fall in Kürze überprüfen. Wenn ich (oder andere) diese Antwort hilfreich finde, werden wir sie positiv bewerten. Wenn ich finde, dass sie die "richtige" Antwort ist, wird dieser Antwort ebenfalls ein grünes Häkchen hinzugefügt. - Willkommen bei StackOverflow!
Scunliffe
2
-1 Diese LCG-Implementierung überschreitet die Grenze für exakte Ganzzahlen in JavaScript, da dies seedobj[0] * seedobjawahrscheinlich zu einer Zahl größer als 2 ^ 53 führt. Das Ergebnis ist ein begrenzter Ausgabebereich und für einige Samen möglicherweise ein sehr kurzer Zeitraum.
aaaaaaaaaaaa