Warum scheint C++ rand() nur Zahlen derselben Größenordnung zu generieren?

Lesezeit: 6 Minuten

Benutzeravatar von Tallaron Mathias
Tallaron Mathias

In einer kleinen Anwendung, die in C/C++ geschrieben wurde, habe ich ein Problem mit der rand Funktion und vielleicht der Seed:

Ich möchte eine Folge von Zufallszahlen erzeugen, die unterschiedlicher Ordnung sind, dh mit unterschiedlichen Logarithmuswerten (Basis 2). Aber es scheint, dass alle produzierten Zahlen in der gleichen Größenordnung liegen und nur zwischen 2^25 und 2^30 schwanken.

Ist es weil rand() ist mit Unix-Zeit gesät, was mittlerweile eine relativ große Zahl ist? Was vergesse ich? Ich säe rand() nur einmal am Anfang des main().

  • FWIW also, ist es C oder C++? Wenn Sie mit C/C++ meinen, dass Sie tatsächlich C++ verwenden können, und die Erwähnung von C nur zufällig war, vielleicht das en.cppreference.com/w/cpp/numeric/random/binomial_distribution kann helfen.

    – R.Martinho Fernandes

    20. Juni 2013 um 13:26 Uhr


  • Leider haben Sie auf das falsche Pferd gesetzt. Samen sollten nicht Ihr Problem sein. Ihr Problem war eine falsch erwartete Verteilung. Da würden unvoreingenommene Programmierer erwarten rand() gleichmäßig verteilte Zahlen zurückzugeben (Dokumentation mit hohem Google-Ranking sagt dies ausdrücklich) Ich denke nicht, dass diese Frage für zukünftige Leser nützlich ist. Stimmen Sie deshalb ab, aber lassen Sie sich nicht davon abhalten, SO zu verwenden.

    – Kaiser Orionii

    20. Juni 2013 um 14:16 Uhr

  • @ doug65536 “… wo keine Zahl jemals wiederholt wird” – das ist kein Zufall! Ich könnte meinen Ruhestand am Craps-Tisch finanzieren, wenn meine rand()-Würfel nie zweimal die gleiche Zahl ergeben würden, bis jede mögliche Zahl zurückgegeben wurde.

    – Chris Gregg

    21. Juni 2013 um 8:46 Uhr

  • @GalacticCowboy Verwechseln Sie die Periodizität nicht mit einer Wiederholung einzelner Zahlen. Aus dem von Ihnen zitierten Wikipedia-Artikel: “Ein wiederholtes Ergebnis bedeutet nicht, dass das Ende des Zeitraums erreicht wurde, da sein interner Zustand größer sein kann als sein Ausgang.” Es wäre sehr, sehr schlecht, wenn ein PRNG einen Wert produzieren würde und diesen Wert dann garantiert nicht mehr produzieren würde, bis alle Werte zurückgegeben wurden.

    – Chris Gregg

    22. Juni 2013 um 0:23 Uhr


  • Doug65536, niemand fängt Streit an. Sie sagen nur richtig, dass Sie falsch liegen. Wenn ich einen RAND zwischen 1 und 10 haben wollte, könnte ein PRNG problemlos Folgendes ausgeben: 2 4 7 2 8 1 5 9 7 3 Das wäre trotz der mehrfachen 2er und 7er vollkommen gültig. Ich denke, Sie verwechseln das PRNG mit der Shuffle-Funktion auf Ihrem iPhone.

    – Entspannen in Zypern

    22. Juni 2013 um 12:46 Uhr


Benutzeravatar von C4stor
C4stor

Es gibt nur 3% der Zahlen zwischen 1 und 230 die NICHT zwischen 2 liegen25 und 230. Also das hört sich ganz normal an 🙂

Denn 225 / 230 = 2-5 = 1/32 = 0,03125 = 3,125 %

  • Ja, guter Punkt! Es gibt 31 mal mehr Zahlen zwischen 2^25 und 2^30 als zwischen 1 und 2^25 🙂 Danke für die schnelle Antwort. Dann muss ich das Programm überdenken. Frage beantwortet.

    – Tallaron Mathias

    20. Juni 2013 um 9:35 Uhr

  • @TallaronMathias Erwägen Sie, die Zahl zu kürzen >> Bitshifting – dies gibt Ihnen kleinere Zahlen. (Oder ein Modul mit nehmen %.)

    – Sean Allred

    20. Juni 2013 um 16:40 Uhr


  • Ich würde erwarten, dass dies für die meisten Programmierer offensichtlich ist: Bei jeder vorzeichenlosen Ganzzahl kleiner als 2^25 müssen die ersten 7 Bits gleich sein 0 – und wenn jedes Bit zufällig ist…

    – BlueRaja – Danny Pflughoeft

    20. Juni 2013 um 18:46 Uhr


  • @BlueRaja-DannyPflughoeft – wenn die Wahrscheinlichkeiten offensichtlich wären, wären Casinos aus dem Geschäft.

    – Brett Hale

    20. Juni 2013 um 18:56 Uhr

  • @BrettHale – Ich glaube jedoch nicht, dass Programmierer die Zielgruppe eines Casinos sind.

    – ÖkoostikMartin

    21. Juni 2013 um 15:30 Uhr

Benutzeravatar von Casey Chu
Casey Chu

Das hellere Grün ist der Bereich zwischen 0 und 225; das dunklere Grün ist der Bereich zwischen 225 und 230. Die Ticks sind Potenzen von 2.

Verteilung

Sie müssen genauer sein: Sie wollen unterschiedliche Logarithmuswerte zur Basis 2, aber was Verteilung willst du dafür Die Standardfunktionen von rand() erzeugen eine gleichmäßige Verteilung, Sie müssen diese Ausgabe mit transformieren Quantil Funktion, die der gewünschten Verteilung zugeordnet ist.

Wenn Sie uns die Verteilung mitteilen, können wir Ihnen die mitteilen quantile Funktion, die Sie brauchen.

  • +1, Verteilung ist der entscheidende Begriff. Es macht keinen Sinn, von Zufallszahlen zu sprechen, wenn nichts über die Verteilung bekannt ist. Uniform ist nur ein Sonderfall, wenn auch ein wichtiger. Könnte ein guter Ort sein, um auf verschiedene Distributionen aus der C++11-Standardbibliothek hinzuweisen.

    – linksherum

    20. Juni 2013 um 21:43 Uhr

Benutzeravatar von aspiring_sarge
aspiring_sarge

Wenn Sie andere Größenordnungen wünschen, probieren Sie es einfach aus pow(2, rand())? Oder wählen Sie die Reihenfolge vielleicht direkt als rand() aus, wie Harold vorgeschlagen hat?

Benutzeravatar von Francisco Presencia
Francisco Präsenz

@C4stor hat einen tollen Punkt gemacht. Aber für einen allgemeineren Fall und für Menschen leichter verständlich (Basis 10): Für den Bereich von 1 bis 10 ^ n sind ~ 90% der Zahlen von 10 ^ (n-1) bis 10 ^ n, daher ~99 % der Zahlen reichen von 10^(n-2) bis 10^n. Fügen Sie so viele Dezimalstellen hinzu, wie Sie möchten.

Komische Mathematik, wenn du das für n weiter machst, kannst du das von 1 bis 10^n sehen, 99,9999 … % = 100 % der Zahlen reichen bei dieser Methode von 10^0 bis 10^n.

Nun zum Code, wenn Sie eine Zufallszahl mit zufälligen Größenordnungen von 0 bis 10 ^ n wollen, könnten Sie Folgendes tun:

  1. Generieren Sie eine kleine Zufallszahl von 0 bis n

  2. Wenn Sie den Bereich kennen, den n hat, generieren Sie eine große Zufallszahl der Ordnung 10^k, wobei k > max{n}.

  3. Schneiden Sie die längere Zufallszahl ab, um die n Ziffern dieser großen Zufallszahl zu erhalten.

  • Sie haben völlig Recht, aber für eine WIRKLICH leicht verständliche Antwort sollte sich das OP fragen, warum 90% der Zufallszahlen zwischen 1 und 100 zweistellig sind.

    – Fragen Sie nach Monica

    20. Juni 2013 um 15:16 Uhr

Die grundlegende (und richtige) Antwort wurde oben bereits gegeben und akzeptiert: Es gibt 10 Zahlen zwischen 0 und 9, 90 Zahlen zwischen 10 und 99, 900 zwischen 100 und 999 usw.

Für eine recheneffiziente Möglichkeit, eine Verteilung mit zu erhalten etwa Logarithmische Verteilung, möchten Sie Ihre Zufallszahl um eine Zufallszahl nach rechts verschieben:

s = rand() & 31; // a random number between 0 and 31 inclusive, assuming RAND_MAX = 2^32-1
r = rand() >> s; // right shift

Es ist nicht perfekt, aber es ist viel schneller als Computer pow(2, rand()*scalefactor). Es ist “klumpig” in dem Sinne, dass die Verteilung für Zahlen innerhalb eines Faktors 2 gleichmäßig ist (gleichmäßig für 128 bis 255, halbe Dichte für 256 bis 1023 usw.).

Hier ist ein Histogramm der Häufigkeit der Zahlen 0 bis 31 (in 1 Million Stichproben):

Geben Sie hier die Bildbeschreibung ein

  • Sie haben völlig Recht, aber für eine WIRKLICH leicht verständliche Antwort sollte sich das OP fragen, warum 90% der Zufallszahlen zwischen 1 und 100 zweistellig sind.

    – Fragen Sie nach Monica

    20. Juni 2013 um 15:16 Uhr

Vadims Benutzeravatar
Wadim

Es gibt genau gleich viele Zahlen zwischen 0 und 2^29 und 2^29 und 2^30.

Eine andere Betrachtungsweise des Problems: Betrachten Sie die binäre Darstellung der von Ihnen generierten Zufallszahl, die Wahrscheinlichkeit, dass das höchste Bit 1 ist, ist gleich 1/2, und daher erhalten Sie in halben Fällen die Ordnung 29. Was Sie wollen, ist eine Zahl zu sehen, die unter 2 ^ 25 wäre, aber das bedeutet, dass die 5 höchsten Bits alle Null sind, was mit einer geringen Wahrscheinlichkeit von 1/32 passiert. Die Chancen stehen gut, dass Sie, selbst wenn Sie es lange laufen lassen, die Reihenfolge nie unter 15 sehen werden (die Wahrscheinlichkeit ist ungefähr so, als ob Sie 6 mal 6 Mal hintereinander würfeln würden).

Nun, der Teil Ihrer Frage über den Samen. Nein, der Seed kann unmöglich den Bereich bestimmen, aus dem die Zahlen generiert werden, er bestimmt nur das erste, anfängliche Element. Stellen Sie sich rand() als eine Folge aller möglichen Zahlen im Bereich vor (vorbestimmte Permutation). Der Seed bestimmt, wo Sie beginnen, Zahlen aus der Sequenz zu ziehen. Wenn Sie also (Pseudo-)Zufälligkeit wollen, verwenden Sie die aktuelle Zeit, um die Sequenz zu initialisieren: Es ist Ihnen egal, dass die Position, an der Sie beginnen, nicht gleichmäßig verteilt ist, alles, was zählt, ist, dass Sie nie von derselben Position aus starten.

1424000cookie-checkWarum scheint C++ rand() nur Zahlen derselben Größenordnung zu generieren?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy