Wird rand() manchmal nacheinander dasselbe zurückgeben?

Lesezeit: 5 Minuten

Benutzer-Avatar
Gohan

Ich bin nur neugierig, kann ein Singlethread-Programm jemals den gleichen Rückgabewert für zwei aufeinanderfolgende Aufrufe erhalten rand()?

Wird diese Behauptung also jemals ausgelöst?

assert(rand() != rand());

  • Na sicher. Warum nicht?

    – Juanchopanza

    3. Juni 2014 um 9:16 Uhr

  • Schauen Sie sich stackoverflow.com/q/21634465/3235496 an (es ist eine Java-Frage, bringt aber gültige Punkte).

    – manlio

    3. Juni 2014 um 9:22 Uhr


  • Du kannst einen Würfel zweimal werfen und jedes Mal sechs bekommen, oder?

    – Juanchopanza

    3. Juni 2014 um 9:34 Uhr

  • Nur eindeutige Zahlen zurückzugeben ist a Muster und ist nicht zufällig als solche.

    – Schepurin

    3. Juni 2014 um 10:26 Uhr

  • dilbert.com/strips/comic/2001-10-25

    – Dämmerwächter

    3. Juni 2014 um 12:19 Uhr

Benutzer-Avatar
Nr

Wenn wir ein Beispiel finden können, wo dies der Fall ist, lautet die Antwort auf Ihre Frage “Ja”.

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char* argv[])
{
  unsigned int i;
  for(i = 0; ; i++) {
    int r = rand();
    if (r == rand()) {
        printf("Oops. rand() = %d; i = %d\n", r, i);
        break;
    }
  }
  return 0;
}

Drucke Oops. rand() = 3482; i = 32187 unter Windows mit Visual Studio 2010.

BEARBEITEN: Verwenden Sie die folgende Version, um alle Sequenzen zu erkennen, bei denen 2 aufeinanderfolgende rand()-Aufrufe denselben Wert zurückgeben. C gibt nur an, dass rand() „pseudozufällige Ganzzahlen im Bereich von 0 bis RAND_MAX“ zurückgeben soll und RAND_MAX mindestens 32767 sein sollte. Es gibt keine Einschränkungen hinsichtlich der Qualität des PRNG oder seiner Implementierung oder anderer Details wie z 2 aufeinanderfolgende rand()-Aufrufe können denselben Wert zurückgeben.

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char* argv[])
{
  unsigned int i;
  int r1 = rand();
  int r2 = rand();
  for(i = 0; ; i++) {
    if (r1 == r2) {
        printf("Oops. rand() = %d; i = %d\n", r1, i);
    }
    r1 = r2;
    r2 = rand();
  }
  return 0;
}

  • @bits_international, weil es später kam und die Antwort von Unwind der erste Impuls aller war.

    – nwp

    3. Juni 2014 um 11:10 Uhr

  • @bits_international: Die Definition im Handbuch oder Standard ist maßgeblicher als das Ergebnis einer Programmausführung. Nach allem, was wir wissen (ohne Bezugnahme auf eine tatsächliche Definition von rand()), könnte dieses Verhalten ein Fehler in der Visual Studio-Implementierung sein, oder das Programm könnte ein undefiniertes Verhalten aufweisen.

    – Mankarse

    3. Juni 2014 um 11:10 Uhr


  • Nur ein Nitpick, aber es sieht so aus, als könnten viele zufällige fortlaufende Zahlen fehlen. Es prüft nur, ob ein ungerader Anruf mit dem nächsten geraden übereinstimmt, nicht, ob ein gerader Anruf mit dem nächsten übereinstimmt. Irgendwann hast du einen gefunden, aber es besteht eine gute Chance, dass es einen früheren Fall gibt.

    – Schwebecouch

    3. Juni 2014 um 19:36 Uhr

  • Unter Ubuntu 64 Bit (amd64) mit gcc 4.6.3 wiederholt rand() 1804289383 nach 2888000745 Iterationen.

    – Ken A

    3. Juni 2014 um 20:41 Uhr

  • @Mankarse: Dieses Programm zeigt, dass die Antwort auf die Frage des OP “Ja” lautet: Das OP hat gefragt, ob es jemals passieren kann, und diese Antwort zeigt, dass dies möglich ist. Das OP hat nicht gefragt, ob dieses Verhalten vom Standard erlaubt ist. Selbst wenn dies ein Fehler in MSVC wäre, würde es die Frage trotzdem beantworten. (Natürlich wäre es auch nützlich für die Antwort zu sagen, dass dies ein Fehler war, falls dies der Fall wäre.)

    – ruach

    4. Juni 2014 um 8:13 Uhr

Benutzer-Avatar
Gohan

Ich habe meine Nachforschungen angestellt

entdeckt, dass mein Compiler (msvc10)’s rand-Implementierung verwendete den linearen kongruenten Generator genau wie andere c/c++-Compiler

Linearer Kongruenzgenerator

Lineare Kongruenzgeneratoren verwenden die Rekursionsmethode.

benutze die

ptd->_holdrand(n) wird nie gleich ptd->_holdrand(n+1), aber das Mod-Ergebnis wird gleich sein.

msvc-Implementierung

@nos zeigt das Ergebnis

return( ((ptd->_holdrand = ptd->_holdrand * 214013L + 2531011L) >> 16) & 0x7fff );

ptd->_holdrand = 2375716238;
return 3482; (2375716238 >> 16) % 32768
ptd->_holdrand = 228240921;
return 3482; (228240921 >> 16) % 32768

Die letzte Antwort ist, dass rand() manchmal zweimal denselben Wert zurückgibt wie mein Instinkt.

  • Es ist schön, dass Sie recherchiert haben, aber das ist oft der Schritt Vor eine Frage stellen (eine Regel, an die sich bei Stackoverflow fast niemand hält).

    – Shahbaz

    3. Juni 2014 um 12:03 Uhr


  • +1 für die Ergänzung Ihrer eigenen Frage mit etwas Mathematik als Antwort. Wie @Shahbaz sagte, ist es am besten, diese Art von Recherche vor der Frage durchzuführen, um sie zu vermeiden fragen müssen wenn Sie finden, wonach Sie gesucht haben, aber es ist sowieso gut, Referenzfragen wie diese auf SO zu haben (meiner Meinung nach).

    – Chris Cirefice

    3. Juni 2014 um 15:10 Uhr

  • @ChrisCirefice, das stimmt. Am besten wäre das: recherchieren (dabei evtl. feststellen, dass dir keine Frage in SO beantwortet). Wenn Sie Ihre Antwort nicht finden, stellen Sie eine Frage. Wenn Sie Ihre Antwort finden, stellen Sie die Frage trotzdem und posten Sie Ihre Antwort, um anderen zu helfen (Sie können eine Frage und ihre Antwort gleichzeitig posten!). Ernten Sie Belohnungen für eine gut recherchierte Frage (und möglicherweise eine gut geschriebene Antwort).

    – Shahbaz

    3. Juni 2014 um 16:47 Uhr


  • Aber dann geben die Antworten oft einen Hinweis, was zu recherchieren ist, so dass ohne das Lesen der Antworten auf die Frage ein Rechercheversuch gescheitert wäre. Manchmal geben Antworten eine unvollständige Antwort, und der Fragesteller, der mehr an der vollständigen Antwort interessiert ist als alle anderen, kann dies als Ausgangspunkt verwenden. Das Posten einer verbesserten Antwort kommt allen zugute. Und Recherche nach dem Posten ist meilenweit besser als keine Recherche nach dem Posten.

    – gnasher729

    3. Juni 2014 um 16:50 Uhr

  • @Shahbaz Ich bin anderer Meinung. Ich denke, wenn eine Frage wahrscheinlich Informationen generiert, die für andere Benutzer hilfreich sind, ist es in Ordnung, sie zu posten, solange es sich nicht um ein Duplikat handelt. Das ist definitiv so eine Frage.

    – Kevin

    3. Juni 2014 um 20:39 Uhr

Ein idealer Zufall rand() Bei zweimaligem Aufruf würde die Funktion jedes Mal dasselbe Ergebnis mit einer Wahrscheinlichkeit von zurückgeben 1.0 / RAND_MAX.

Aber rand() ist kein echter Zufallszahlengenerator. Es ist ein Pseudozufallszahlengenerator (PRNG), typischerweise der linear kongruent Typ.

Das internen Zustand des PRNG darf bei aufeinanderfolgenden Aufrufen nicht wiederholt werden; wenn ja, rand() würde für immer bei der gleichen Nummer stecken bleiben. Dies kann bei schlecht konzipierten Algorithmen wie dem passieren Mittelquadrat-Methode.

Einige (aber nicht alle) PRNG-Implementierungen haben jedoch mehr Bits in ihrem internen Zustand als in ihrer Ausgabe. Zum Beispiel, java.util.Random verwendet einen internen 48-Bit-Zustand, enthält jedoch nur die höchstwertigen 32 Bits in seiner Ausgabe. In diesem Fall ist es (zumindest theoretisch) möglich, zweimal hintereinander dieselbe Ausgabe zu erhalten, ohne denselben internen Zustand zu haben.

Ein guter Zufallsgenerator sollte geben manchmal denselben Wert zweimal hintereinander zurück. Nehmen wir an, es gibt positive ganze Zahlen 0 <= r < 2^31 zurück. Die Wahrscheinlichkeit, dass zwei aufeinanderfolgende Zahlen gleich sind, würde bei einem perfekten Zufallszahlengenerator etwa eins zu zwei Milliarden betragen. Die Chance auf nicht Bei 100 Milliarden Anrufen zwei aufeinanderfolgende Nummern zu erhalten, die gleich sind, ist etwa einer von 10^15.

1381660cookie-checkWird rand() manchmal nacheinander dasselbe zurückgeben?

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

Privacy policy