wake-up-neo.com

Wie zufällig ist JavaScript Math.random?

Seit 6 Jahren habe ich eine Zufallszahlengenerator Seite auf meiner Website. Lange Zeit war es das erste oder zweite Ergebnis bei Google für "Zufallszahlengenerator" und wurde verwendet, um Dutzende, wenn nicht Hunderte von Wettbewerben und Zeichnungen in Diskussionsforen und Blogs zu entscheiden (ich weiß, weil ich die Verweise in meinem Blog sehe) Web-Logs und in der Regel gehen einen Blick darauf).

Heute hat mir jemand eine E-Mail geschickt, um mir mitzuteilen , dass es möglicherweise nicht so zufällig ist, wie ich dachte. Sie hat versucht, sehr große Zufallszahlen zu generieren (z. B. zwischen 1 und 10000000000000000000 ) und stellten fest, dass sie fast immer die gleiche Anzahl von Ziffern waren. Tatsächlich habe ich die Funktion in eine Schleife gehüllt, damit ich Tausende von Zahlen generieren kann, und bei sehr großen Zahlen betrug die Abweichung nur etwa 2 Größenordnungen.

Warum?

Hier ist die Loop-Version, damit Sie es selbst ausprobieren können:

http://andrew.hedges.name/experiments/random/randomness.html

Es enthält sowohl eine einfache Implementierung aus Mozilla Developer Network als auch Code aus dem Jahr 1997, den ich von einer nicht mehr vorhandenen Webseite entfernt habe (Paul Houles "Central Randomizer 1.3"). Zeigen Sie den Quellcode an, um zu sehen, wie die einzelnen Methoden funktionieren.

Ich habe gelesen hier und anderswo über Mersenne Twister. Was mich interessiert, ist warum die Ergebnisse der integrierten Math.random - Funktion von JavaScript nicht stärker variieren würden. Vielen Dank!

110
Andrew Hedges

Angegebene Zahlen zwischen 1 und 100. 

  • 9 haben 1 Ziffer (1-9)
  • 90 haben 2 Ziffern (10-99)
  • 1 hat 3 Ziffern (100)

Angegebene Zahlen zwischen 1 und 1000.

  • 9 haben 1 Ziffer
  • 90 haben 2 Ziffern
  • 900 haben 3 Ziffern
  • 1 hat 4 Ziffern

und so weiter.

Wenn Sie einige nach dem Zufallsprinzip auswählen, hat die überwiegende Mehrheit der ausgewählten Zahlen die gleiche Anzahl von Ziffern, da die überwiegende Mehrheit der möglichen Werte dieselbe Anzahl von Ziffern hat.

165
Quentin

Ihre Ergebnisse werden tatsächlich erwartet. Wenn die Zufallszahlen gleichmäßig in einem Bereich von 1 bis 10 ^ n verteilt sind, würden Sie erwarten, dass 9/10 der Zahlen n Ziffern haben und weitere 9/100 n-1 Ziffern.

54
jwoolard

Es gibt verschiedene Arten von Zufälligkeit. Math.random gibt Ihnen eine einheitliche Verteilung von Zahlen.

Wenn Sie unterschiedliche Größenordnungen wünschen, würde ich vorschlagen, eine Exponentialfunktion zu verwenden, um eine sogenannte Potenzgesetzverteilung zu erstellen:

function random_powerlaw(mini, maxi) {
    return Math.ceil(Math.exp(Math.random()*(Math.log(maxi)-Math.log(mini)))*mini)
}

Diese Funktion sollte ungefähr die gleiche Anzahl von 1-stelligen Nummern haben wie 2-stellige und 3-stellige Nummern.

Es gibt auch andere Verteilungen für Zufallszahlen wie die Normalverteilung (auch Gaußsche Verteilung genannt).

41
Christian

Das folgende Dokument erläutert, wie math.random () in gängigen Webbrowsern (un) sicher ist: "Temporäre Benutzerverfolgung in großen Browsern und domänenübergreifende Informationen Durchsickern und Angriffe" von Amid Klein (2008) . Es ist nicht stärker als typische in Java oder Windows integrierte Funktionen PRNG.

Andererseits erfordert die Implementierung von SFMT der Periode 2 ^ 19937-1 2496 Bytes des internen Zustands, der für jede PRNG - Sequenz aufrechterhalten wird. Einige Leute betrachten dies möglicherweise als unverzeihliche Kosten.

18
jj1bdx

Sieht für mich vollkommen zufällig aus! (Hinweis: Browserabhängig.)

Ich persönlich denke, meine Implementierung wäre besser, obwohl ich es von XKCD gestohlen habe, wer IMMER anerkannt werden sollte:

function random() {
  return 4; // Chosen by a fair dice throw. Guaranteed to be random.
}
17
Arafangion

Wenn Sie eine Zahl wie 10000000000000000000 verwenden, gehen Sie über die Genauigkeit des Datentyps hinaus, den Javascript verwendet. Beachten Sie, dass alle generierten Zahlen mit "00" enden.

5
Greg

Ich habe den JS-Pseudozufallszahlengenerator auf Chaos Game ausprobiert.

Mein Sierpiński-Dreieck sagt, es ist ziemlich zufällig: Fractal

5
zie1ony

Wenn Sie Zahlen bis etwa 1e6 generieren, werden Sie hoffentlich alle Zahlen mit ungefähr gleicher Wahrscheinlichkeit erhalten. Das bedeutet auch, dass Sie nur eine Chance von eins zu zehn haben, eine Zahl mit einer Ziffer weniger zu erhalten. Eine hundertprozentige Chance, zwei Stellen weniger zu erhalten, usw. Ich bezweifle, dass Sie bei der Verwendung eines anderen RNG einen großen Unterschied feststellen werden, weil Sie eine einheitliche Verteilung über die Zahlen haben und nicht über deren Logarithmus.

3
Joey

Nicht zufällige Zahlen, die gleichmäßig von 1 bis N verteilt sind, haben die gleiche Eigenschaft. Beachten Sie, dass es (in gewissem Sinne) eine Frage der Präzision ist. Eine einheitliche Verteilung auf 0-99 (als ganze Zahlen) hat 90% ihrer Zahlen mit zwei Ziffern. Eine einheitliche Verteilung auf 0-999999 hat 905 Ziffern mit fünf Ziffern. 

Jeder Zahlensatz (unter einigen nicht zu einschränkenden Bedingungen) hat eine Dichte. Wenn jemand "zufällige" Zahlen besprechen möchte, sollte die Dichte dieser Zahlen angegeben werden (wie oben angegeben). Eine gemeinsame Dichte ist die gleichförmige Dichte. Es gibt andere: die exponentielle Dichte, die normale Dichte usw. Bevor man einen Zufallszahlengenerator vorschlägt, muss man auswählen, welche Dichte relevant ist. Außerdem können Zahlen, die aus einer Dichte stammen, oft mit kariösen Mitteln leicht in eine andere Dichte umgewandelt werden.

0
ttw