Warum wird 1103515245 in Rand verwendet?

Ich rede von Dies überraschend einfache Implementierung von rand() aus der C-Norm:

static unsigned long int next = 1;

int rand(void)  /* RAND_MAX assumed to be 32767. */
{
    next = next * 1103515245 + 12345;
    return (unsigned)(next/65536) % 32768;
}

Aus diesen Wikipedia-Artikel Wir wissen, dass der Multiplikator a (im obigen Code a = 1103515245) sollte nur 2 Bedingungen erfüllen:

1. a - 1 durch alle Primfaktoren von teilbar ist m.
   (In unserem Fall m = 2^32Größe des int, so m hat nur einen Primfaktor = 2)
2. a - 1 ein Vielfaches von 4 ist, wenn m ist ein Vielfaches von 4.
   (32768 ist ein Vielfaches von 4 und 1103515244 auch)

Warum haben sie eine so seltsame, schwer zu merkende „Mann, ich habe diese Zufallszahlen satt, schreiben Sie was auch immer“-Nummer gewählt, wie 1103515245?

Vielleicht gibt es ein paar kluge Gründe, warum diese Nummer irgendwie besser ist als die andere?

Warum zum Beispiel nicht festlegen a = 20000000001? Es ist größer, sieht cool aus und ist leichter zu merken.

Wenn Sie ein LCG verwenden, um Punkte im d-dimensionalen Raum zu zeichnen, liegen sie höchstens auf (d!m)^1/_d Hyperebenen. Dies ist ein bekannter Defekt von LCGs.

Wenn Sie a und m nicht sorgfältig auswählen (über die Bedingung für volle Periodizität hinaus), können sie auf viel weniger Ebenen liegen. Diese Nummern wurden von der sogenannten ausgewählt Spektraler Test.

Der “Spektraltest” (der Name stammt aus der Zahlentheorie) ist der maximale Abstand zwischen aufeinanderfolgenden Hyperebenen, auf denen d-dimensionale gemeinsame Verteilungen liegen. Sie möchten, dass es für so viele d, wie Sie testen können, so klein wie möglich ist.

Sehen dieses Papier für einen historischen Rückblick auf das Thema. Beachten Sie, dass der von Ihnen zitierte Generator in der Veröffentlichung (als ANSIC) erwähnt und als nicht sehr gut eingestuft wird. Die 16 Bit hoher Ordnung sind jedoch akzeptabel, aber viele Anwendungen benötigen mehr als 32768 unterschiedliche Werte (wie Sie in den Kommentaren darauf hinweisen, beträgt die Periode tatsächlich 2 ^ 31 – die Bedingungen für die vollständige Periodizität im Wikipedia-Link sind wahrscheinlich nur erforderlich ).

Der ursprüngliche Quellcode im ANSI-Dokument hat die höherwertigen 16 Bits nicht verwendet, was zu einem sehr schlechten Generator führt, der leicht missbraucht werden kann (rand() % n ist das, woran die Leute zuerst denken, um eine Zahl dazwischen zu ziehen 0 und nund dies ergibt in diesem Fall etwas sehr Nicht-Zufälliges).

Siehe auch die Diskussion über LCGs in numerischen Rezepten. Zitat:

Schlimmer noch, viele frühe Generatoren trafen zufällig eine besonders schlechte Wahl für m und a. Eine berüchtigte Routine dieser Art, RANDU, mit a = 65539 und m = 231, war viele Jahre lang auf IBM-Mainframe-Computern weit verbreitet und wurde häufig auf andere Systeme kopiert. Einer von uns erinnert sich, wie er als Doktorand einen „zufälligen“ Plot mit nur 11 Flugzeugen erstellte und vom Programmierberater seines Rechenzentrums darauf hingewiesen wurde, dass er den Zufallszahlengenerator missbraucht habe: „Wir garantieren, dass jede Zahl einzeln zufällig ist, aber wir tun es nicht. Ich kann nicht garantieren, dass mehr als einer von ihnen zufällig ist.“ Das hat unsere Graduiertenausbildung um mindestens ein Jahr zurückgeworfen!

Erinnere dich daran rand() ist eine Annäherung an a gleichmäßige Verteilung. Diese Zahlen werden verwendet, weil sie getestet wurden, um zu zeigen, dass sie eine einheitlichere Verteilung erzeugen.

Angesichts der Vielzahl von Paaren vorzeichenloser Ganzzahlen im darstellbaren Bereich bezweifle ich, dass irgendjemand sie alle mit allen gültigen Startwerten ausprobiert hat. Wenn Sie der Meinung sind, dass Sie eine bessere Auswahl an Parametern haben, probieren Sie es einfach aus! Sie haben den Code, klammern Sie einfach die Parameter aus LCG und Tests durchführen. Generieren Sie eine Reihe von Zahlen (z. B. 10 Millionen), berechnen Sie ein Histogramm der generierten Zahlen und zeichnen Sie dies auf, um die Verteilung zu betrachten.

bearbeiten
Wenn Sie daran interessiert sind, einen Pseudozufallszahlengenerator für den Einsatz in realen Anwendungen zu entwickeln, empfehle ich Ihnen, sich mit der umfangreichen Literatur zu diesem Thema vertraut zu machen. Der oben gegebene “Ratschlag” soll nur zeigen, dass die Wahl willkürlicher “größerer, cooler aussehender und leichter zu merkender” LCG-Parameter eine sehr schlechte Verteilung ergibt.
/bearbeiten

Außerdem ist es eine Bibliotheksfunktion und ich habe noch nie ein Programm gesehen, das die Standardbibliotheksversion von verwendet rand() um sich an die Parameter seines LCG zu erinnern.

Frühe Berechnungen beschäftigten sich eher mit den Bits und Bytes und spielten Tricks mit den Registern, um Codebytes zu minimieren (vor Zeilen gab es Bytes).

Ich habe nur einen vernünftigen Hinweis unten gefunden:

Die Ausgabe dieses Generators ist nicht sehr zufällig. Wenn wir den oben aufgeführten Beispielgenerator verwenden, ist die Folge von 16 Schlüsselbytes höchst nicht zufällig. Beispielsweise stellt sich heraus, dass das niedrige Bit jeder aufeinanderfolgenden Ausgabe von rand() alterniert (z. B. 0,1,0,1,0,1, . . . ). Siehst du warum? Das Low-Bit von x * 1103515245 ist das gleiche wie das Low-Bit von x, und das Hinzufügen von 12345 dreht nur das Low-Bit um. Somit wechselt das Low-Bit. Dadurch wird die Menge der möglichen Schlüssel auf nur 2113 Möglichkeiten eingegrenzt, viel weniger als der gewünschte Wert von 2128.

http://inst.eecs.berkeley.edu/~cs161/fa08/Notes/random.pdf

Und zwei vernünftige Antworten:

Improving a poor random number generator (1976) von Bays, Durham Bays, Carter, SD Durham

http://en.wikipedia.org/wiki/TRNG

Diese Zahl scheint etwas Besonderes zu sein, sie liegt nur zwischen zwei Primzahlen: P.

Jetzt im Ernst, um zu sehen, ob es eine gute Wahl ist, schauen Sie sich einfach die Ausgabe an. Sie sollten sehr unterschiedliche Ergebnisse sehen, selbst wenn Sie nur ein einziges Bit umdrehen.

Überlegen Sie auch, wie viel Vorhersagbarkeit Sie erwarten … dass die Implementierung schrecklich ist, Sie können eine robustere und dennoch einfache Alternative in Betracht ziehen, z FNV-1a.