Einsetzen des Zufallszahlengenerators in Javascript

Question

Ist es möglich, den Zufallszahlengenerator ( Math.random ) in JavaScript?

Answer 1

Nein, es ist nicht möglich, Saatgut Math.random() .

Ich habe eine Reihe von guten, kurzen und schnellen Pseudozufallszahlengenerator (PRNG) Funktionen in einfachem JavaScript. Sie können alle geseedet werden und liefern qualitativ hochwertige Zahlen.

Achten Sie zunächst darauf, Ihre PRNGs richtig zu initialisieren. Der Einfachheit halber haben die folgenden Generatoren kein eingebautes Verfahren zur Erzeugung von Seeds, sondern akzeptieren einen oder mehrere 32-Bit-Werte als Ausgangswert Saatzustand des PRNG. Ähnliche oder spärliche Seeds (z. B. ein einfacher Seed von 1 und 2) haben eine niedrige Entropie und können Korrelationen oder andere Zufallsqualitätsprobleme verursachen, was manchmal dazu führt, dass die Ausgabe ähnliche Eigenschaften hat (z. B. dass zufällig erzeugte Ebenen ähnlich sind). Um dies zu vermeiden, ist es am besten, PRNGs mit einem gut verteilten Seed mit hoher Entropie zu initialisieren.

Es gibt viele Möglichkeiten, dies zu tun, aber hier sind zwei Methoden. Erstens, Hash-Funktionen sind sehr gut im Erzeugen von Samen aus kurzen Saiten. Eine gute Hash-Funktion erzeugt selbst dann sehr unterschiedliche Ergebnisse, wenn zwei Zeichenketten ähnlich sind, so dass man sich keine großen Gedanken über die Zeichenkette machen muss. Hier ist ein Beispiel für einen Seed-Generator, der auf der Mischfunktion von MurmurHash3 basiert:

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;
    }
}

Jeder weitere Aufruf der Rücklauffunktion de xmur3 erzeugt einen neuen 32-Bit-Hash-Wert, der als Seed in einem PRNG verwendet werden kann. So könnten Sie es verwenden:

// 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();

Alternativ können Sie auch einfach einige Dummy-Daten zum Auffüllen des Seeds wählen und den Generator vorher einige Male (12-20 Iterationen) vorschalten, um den Ausgangszustand gründlich zu mischen. Dies hat den Vorteil, dass es einfacher ist, und wird oft in Referenzimplementierungen von PRNGs verwendet, aber es begrenzt die Anzahl der Ausgangszustände:

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();

Hinweis: Die Ausgabe dieser PRNG-Funktionen ergibt eine positive 32-Bit-Zahl (0 bis 2 32 -1), die dann in eine Fließkommazahl zwischen 0-1 (0 einschließlich, 1 ausschließlich) umgewandelt wird, die Math.random() Wenn Sie Zufallszahlen in einem bestimmten Bereich wünschen, lesen Sie dieser Artikel auf MDN . Wenn Sie nur die rohen Bits benötigen, entfernen Sie einfach die letzte Divisionsoperation.

JavaScript-Zahlen können nur ganze Zahlen mit einer Auflösung von bis zu 53 Bit darstellen. Bei der Verwendung bitweiser Operationen reduziert sich diese Zahl auf 32. Moderne PRNGs in anderen Sprachen verwenden oft 64-Bit-Operationen, die bei der Portierung auf JS Shims erfordern, die drastisch die Leistung verringern. Die Algorithmen hier verwenden nur 32-Bit-Operationen, da sie direkt mit JS kompatibel sind.

Und nun zu den Generatoren. (Ich führe die vollständige Liste mit Referenzen und Lizenzinformationen aquí )

---

sfc32 (Einfacher schneller Zähler)

sfc32 ist Teil der PractRand random number testing suite (die es natürlich besteht). sfc32 hat einen 128-Bit-Status und ist in JS sehr schnell.

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;
    }
}

Sie fragen sich vielleicht, was die | 0 y >>>= 0 sind für. Dies sind im Wesentlichen 32-Bit-Integer-Casts, die für Leistungsoptimierungen verwendet werden. Number in JS sind im Grunde Floats, aber bei bitweisen Operationen schalten sie in einen 32-Bit-Integer-Modus. Dieser Modus wird von JS-Interpretern schneller verarbeitet, aber jede Multiplikation oder Addition führt dazu, dass sie wieder zu einer Fließkommazahl werden, was zu einem Leistungseinbruch führt.

Maulbeere32

Mulberry32 ist ein einfacher Generator mit einem 32-Bit-Zustand, aber er ist extrem schnell und hat eine gute Zufallsqualität (der Autor gibt an, dass er alle Tests von gjrand Prüfsuite und hat eine vollständige 2 32 Zeitraum, aber ich habe es nicht überprüft).

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;
    }
}

Ich würde dies empfehlen, wenn Sie nur eine einfache, aber anständig PRNG und benötigen keine Milliarden von Zufallszahlen (siehe Geburtstagsproblem ).

xoshiro128**

Stand: Mai 2018, xoshiro128** ist das neue Mitglied der Xorshift-Familie von Vigna & Blackman (Professor Vigna war auch für den Xorshift128+-Algorithmus verantwortlich, der den meisten Math.random Implementierungen unter der Haube). Es ist der schnellste Generator, der einen 128-Bit-Status bietet.

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;
    }
}

Die Autoren behaupten, dass es Zufallstests gut besteht ( wenn auch mit Vorbehalten ). Andere Forscher haben darauf hingewiesen, dass er einige Tests in TestU01 nicht besteht (insbesondere LinearComp und BinaryRank). In der Praxis sollte es keine Probleme verursachen, wenn Fließkommazahlen verwendet werden (wie bei diesen Implementierungen), kann aber Probleme verursachen, wenn man sich auf das rohe Bit niedrigster Ordnung verlässt.

JSF (Jenkins' Small Fast)

Dies ist JSF oder "smallprng" von Bob Jenkins (2007), der auch die ISAAC y SpookyHash . Sie geht PractRand testet und sollte recht schnell sein, wenn auch nicht so schnell wie sfc32.

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;
    }
}

Answer 2

Nein, es ist nicht möglich, Saatgut Math.random() aber es ist ziemlich einfach, einen eigenen Generator zu schreiben oder besser noch, einen vorhandenen zu verwenden.

Sehen Sie sich das an: diese verwandte Frage .

Siehe auch David Bau's Blog für weitere Informationen zur Aussaat .

Answer 3

HINWEIS: Trotz (oder gerade wegen) seiner Kürze und scheinbaren Eleganz ist dieser Algorithmus in Bezug auf die Zufälligkeit keineswegs von hoher Qualität. Sehen Sie sich z. B. die in diese Antwort für bessere Ergebnisse.

(Ursprünglich eine clevere Idee, die in einem Kommentar zu einer anderen Antwort vorgestellt wurde).

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

Sie können einstellen seed kann eine beliebige Zahl sein, vermeiden Sie einfach Null (oder ein Vielfaches von Math.PI).

Die Eleganz dieser Lösung ergibt sich meiner Meinung nach aus dem Fehlen jeglicher "magischer" Zahlen (abgesehen von 10000, die ungefähr das Minimum an Ziffern darstellen, das man wegwerfen muss, um ungerade Muster zu vermeiden - siehe Ergebnisse mit Werten 10 , 100 , 1000 ). Auch die Kürze ist gut.

Es ist ein bisschen langsamer als Math.random() (um den Faktor 2 oder 3), aber ich glaube, es ist ungefähr so schnell wie jede andere in JavaScript geschriebene Lösung.

Answer 4

Nein, aber hier ist ein einfacher Pseudozufallsgenerator, eine Implementierung von Multiplizieren-mit-Tragen Angepasst von Wikipedia (wurde inzwischen entfernt):

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;
}

Answer 5

Der Algorithmus von Antti Sykäri ist nett und kurz. Ursprünglich habe ich eine Variante entwickelt, die die JavaScript-Funktion Math.random wenn Sie anrufen Math.seed(s) aber dann meinte Jason, dass es besser wäre, die Funktion zurückzugeben:

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());

Damit haben Sie eine weitere Funktion, die JavaScript nicht hat: mehrere unabhängige Zufallsgeneratoren. Das ist besonders wichtig, wenn Sie mehrere wiederholbare Simulationen gleichzeitig laufen lassen wollen.