Ursprüngliche Quelle des Zufallsalgorithmus "(Startwert * 9301 + 49297)% 233280"?

9

Wenn Sie nach Beispielen für die Erstellung eines gesetzten (Pseudo-) Zufallszahlengenerators suchen, werden Sie auf solche Dinge stoßen (spezielles Beispiel http://indiegamr.com/generate-repeatable-random-numbers-in-js/ ):

// the initial seed
Math.seed = 6;

// in order to work 'Math.seed' must NOT be undefined,
// so in any case, you HAVE to provide a Math.seed
Math.seededRandom = function(max, min) {
    max = max || 1;
    min = min || 0;

    Math.seed = (Math.seed * 9301 + 49297) % 233280;
    var rnd = Math.seed / 233280;

    return min + rnd * (max - min);
}

Diese spezifischen Zahlen (9301, 49297, 233280) und der Algorithmus werden immer wieder verwendet, aber niemand scheint eine endgültige Referenz dafür zu haben. Wer hat diesen Algorithmus erfunden und die Verteilung getestet? Gibt es ein Papier oder etwas zu zitieren?

jlarson
quelle
5
Es ist ein linearer kongruenter Generator, aber mit einer ziemlich kleinen Periode (nur 233k, während ein 32-Bit-Int eine Periode von 4 Milliarden erlaubt
Ratschenfreak
1
Menschen kopieren Code häufig direkt aus Büchern, daher stammt er wahrscheinlich irgendwo aus einem alten Buch und wurde mehrmals kopiert. Es scheint auch ein Grenzfall zu sein. Möglicherweise hilfreich: heydari.persiangig.com/Ebooks/Applied_Crypto-Ch11-ch20.pdf/… ict.griffith.edu.au/anthony/info/C/RandomNumbers
barrycarter
2
Unabhängig von der Herkunft sind dies schreckliche Werte für die Berechnung eines Samens.
3
@jlarson Ein Kommentar ist bei weitem nicht lang genug, aber es gibt zwei Probleme. Erstens ist das Modulo, wie der Ratschenfreak angedeutet hat, die maximale Periode: Anzahl der eindeutigen Zahlen, bevor sich der Generator wiederholt. Der tatsächliche Zeitraum kann kleiner sein. Zweitens sollten die beiden anderen Zahlen (meistens der Multiplikand) relativ prim zu der Modulo-Zahl sein, um einen längeren Zeitraum zu gewährleisten. Idealerweise ist die Modulo-Zahl die größte Primzahl, die kleiner als die maximale positive Ganzzahl ist, die in den Datentyp passt, und die beiden anderen Zahlen sind ebenfalls große Primzahlen.
1
Das ist die kurze, kurze Version, warum diese Zahlen schrecklich sind, da dies eine Nebendiskussion ist und das Hinzufügen einer tatsächlichen Antwort für diese Frage nicht angemessen ist. Ich empfehle, in Wikipedia und vielleicht in Mathematik oder Informatik herumzuspringen, um weitere Informationen zu erhalten, obwohl technisch Pseudozufallszahlenalgorithmen auch bei Programmierern zum Thema gehören.

Antworten:

7

Eine schnelle Suche in Google Books zeigt, dass diese Nummern (9301, 49297, 233280) in einer Reihe von Referenzen verwendet wurden:

  • Numerische Rezepte in FORTRAN 77
  • Eine Einführung in numerische Methoden in C ++
  • CGI-Entwicklerressource: Webprogrammierung in TCL und PERL
  • Effektives Fortran 77 für Ingenieure und Wissenschaftler
  • JavaScript-Entwicklung
  • Alles auf C.
  • Java-Beispiele auf den Punkt gebracht
  • Seminumerische Algorithmen
  • Eine Einführung in die Mechanik

Die älteste ist die Computermethode von 1977 für mathematische Berechnungen von George Elmer Forsythe, Michael A. Malcolm und Cleve B. Moler (Prentice-Hall), obwohl Google nicht anzeigt, wo der Text im Buch verwendet wurde, sodass er nicht überprüft werden kann.

Die früheste Darstellung des Textes ist Numerical Recipes in Pascal (Erstausgabe): The Art of Scientific Computing , Band 1 von Press, Teukolsky, Vetterling und Flannery in einer ganzseitigen Tabelle mit "Konstanten für tragbare Zufallszahlengeneratoren". Diese bestimmten Zahlen werden mit einem Überlauf bei 2 ^ 31 angegeben.

Die Buchreihe Numerical Recipes ist sehr beliebt und seit 1986 im Druck.

Hugo
quelle
1
Wow, wenn die Antwort nicht hier ist, weiß ich nicht, wo es sein würde. Danke .. // Ich hatte gehofft, auf eine bestimmte Untersuchung hinweisen zu können, warum diese Zahlen etwas Besonderes sind, aber das reicht aus. 9301 ist ein Produkt aus zwei Primzahlen (71x131), 49297 ist eine Primzahl - instinktiv denke ich, dass dies relevant sein muss. 233280 ist keine Primzahl - es entspricht 2x2x2x2x2x2x3x3x3x3x3x3x5 (oder 2 ^ 6 * 3 ^ 5 * 5)
jlarson