5 Antworten

Beste Antwort

Es gibt zwei Probleme mit rand() % 6 (das 1+ betrifft keines der beiden Probleme).

Erstens ist, wie mehrere Antworten gezeigt haben, das Ergebnis des Restoperators auch nicht einheitlich, wenn die niedrigen Bits von rand() nicht angemessen einheitlich sind.

Zweitens, wenn die Anzahl der von rand() erzeugten unterschiedlichen Werte kein Vielfaches von 6 ist, erzeugt der Rest mehr niedrige Werte als hohe Werte. Dies gilt auch dann, wenn rand() perfekt verteilte Werte zurückgibt.

Stellen Sie sich als extremes Beispiel vor, dass rand() gleichmäßig verteilte Werte im Bereich [0..6] erzeugt. Wenn Sie sich die Reste für diese Werte ansehen und rand() einen Wert im Bereich [0..5] zurückgibt, führt der Rest zu gleichmäßig verteilten Ergebnissen im Bereich [0..5]. Wenn rand() 6 zurückgibt, gibt rand() % 6 0 zurück, als hätte rand() 0 zurückgegeben. Sie erhalten also eine Verteilung mit doppelt so vielen Nullen wie jeder andere Wert.

Das zweite ist das echte Problem mit rand() % 6.

Um dieses Problem zu vermeiden, müssen Sie Werte verwerfen, die zu ungleichmäßigen Duplikaten führen würden. Sie berechnen das größte Vielfache von 6, das kleiner oder gleich RAND_MAX ist, und wenn rand() einen Wert zurückgibt, der größer oder gleich diesem Vielfachen ist, lehnen Sie es ab und rufen erneut `rand () auf, ebenso viele mal ein benötigt.

So:

int max = 6 * ((RAND_MAX + 1u) / 6)
int value = rand();
while (value >= max)
    value = rand();

Dies ist eine andere Implementierung des fraglichen Codes, um klarer zu zeigen, was los ist.

136
T.C. 17 Apr. 2018 im 20:16

Hier gibt es verborgene Tiefen:

  1. Die Verwendung des kleinen u in RAND_MAX + 1u. RAND_MAX ist als int Typ definiert und häufig der größtmögliche int. Das Verhalten von RAND_MAX + 1 wäre in solchen Fällen undefiniert , in denen Sie einen signed -Typ überlaufen würden. Durch das Schreiben von 1u wird die Typkonvertierung von RAND_MAX in unsigned erzwungen, wodurch der Überlauf vermieden wird.

  2. Die Verwendung von % 6 kann (aber bei jeder Implementierung von std::rand, die nicht gesehen hat) führt darüber hinaus zu zusätzlichen statistischen Verzerrungen die vorgestellte Alternative. Solche Fälle, in denen % 6 gefährlich ist, sind Fälle, in denen der Zahlengenerator Korrelationsebenen in den niederwertigen Bits aufweist, wie beispielsweise eine ziemlich berühmte IBM-Implementierung (in C) von rand in den 1970er Jahren, die drehte die hohen und niedrigen Bits als "letzte Blüte" um. Eine weitere Überlegung ist, dass 6 sehr klein ist, vgl. RAND_MAX, daher gibt es einen minimalen Effekt, wenn RAND_MAX kein Vielfaches von 6 ist, was wahrscheinlich nicht der Fall ist.

Zusammenfassend würde ich heutzutage aufgrund seiner Traktierbarkeit % 6 verwenden. Es ist unwahrscheinlich, dass statistische Anomalien auftreten, die über die vom Generator selbst eingeführten hinausgehen. Wenn Sie immer noch Zweifel haben, testen Sie Ihren Generator, um festzustellen, ob er die entsprechenden statistischen Eigenschaften für Ihren Anwendungsfall aufweist.

19
Jonathan Leffler 20 Apr. 2018 im 00:01

Dieser Beispielcode zeigt, dass std::rand ein Fall von altem Frachtkult-Balderdash ist, bei dem Ihre Augenbrauen jedes Mal hochgezogen werden sollten, wenn Sie ihn sehen.

Hier gibt es mehrere Probleme:

Die Vertragsleute gehen normalerweise davon aus, dass rand Stichproben aus der gleichmäßigen Verteilung sind - selbst die armen, unglücklichen Seelen, die es nicht besser wissen und nicht genau so denken Die Ganzzahlen in 0, 1, 2,…, RAND_MAX und jeder Aufruf ergeben eine unabhängige Stichprobe.

Das erste Problem besteht darin, dass der angenommene Vertrag, unabhängige einheitliche Zufallsstichproben bei jedem Aufruf, nicht den Angaben in der Dokumentation entspricht - und in der Praxis haben Implementierungen in der Vergangenheit nicht einmal das geringste Simulakrum der Unabhängigkeit geliefert. Zum Beispiel , C99 §7.20.2.1 'Die rand Funktion' sagt ohne Ausarbeitung:

Die Funktion rand berechnet eine Folge von pseudozufälligen Ganzzahlen im Bereich von 0 bis RAND_MAX.

Dies ist ein bedeutungsloser Satz, da Pseudozufälligkeit eine Eigenschaft einer Funktion (oder einer Familie von Funktionen ) ist, nicht einer ganzen Zahl, aber das hält nicht einmal ISO-Bürokraten davon ab Missbrauch der Sprache. Schließlich wissen die einzigen Leser, die sich darüber aufregen würden, besser, als die Dokumentation zu rand zu lesen, aus Angst, dass ihre Gehirnzellen verfallen.

Eine typische historische Implementierung in C funktioniert folgendermaßen:

static unsigned int seed = 1;

static void
srand(unsigned int s)
{
    seed = s;
}

static unsigned int
rand(void)
{
    seed = (seed*1103515245 + 12345) % ((unsigned long)RAND_MAX + 1);
    return (int)seed;
}

Dies hat die unglückliche Eigenschaft, dass , obwohl eine einzelne Stichprobe unter einem einheitlichen zufälligen Startwert (der vom spezifischen Wert von RAND_MAX abhängt) gleichmäßig verteilt sein kann, zwischen geraden und ungeraden ganzen Zahlen in wechselt aufeinanderfolgende Anrufe - nach

int a = rand();
int b = rand();

Der Ausdruck (a & 1) ^ (b & 1) ergibt 1 mit einer Wahrscheinlichkeit von 100%, was bei unabhängigen Zufallsstichproben für jede Verteilung, die auf geraden und ungeraden ganzen Zahlen unterstützt wird, nicht der Fall ist. So entstand ein Frachtkult, dass man die niederwertigen Teile wegwerfen sollte, um das schwer fassbare Tier der „besseren Zufälligkeit“ zu jagen. (Spoiler-Alarm: Dies ist kein Fachbegriff. Dies ist ein Zeichen dafür, dass die Prosa, über die Sie lesen, entweder nicht weiß, wovon sie sprechen, oder Sie für ahnungslos hält und sich herablassen muss .)

Das zweite Problem ist, dass selbst wenn jeder Anruf unabhängig von einer gleichmäßigen Zufallsverteilung auf 0, 1, 2,…, RAND_MAX abgetastet wurde, das Ergebnis von rand() % 6 würde nicht gleichmäßig in 0, 1, 2, 3, 4, 5 wie ein Würfelwurf verteilt sein, es sei denn, RAND_MAX stimmt mit -1 Modulo 6 überein. Einfaches Gegenbeispiel: Wenn RAND_MAX = 6, dann haben ab rand() alle Ergebnisse die gleiche Wahrscheinlichkeit 1/7, aber ab rand() % 6 hat das Ergebnis 0 die Wahrscheinlichkeit 2/7, während alle anderen Ergebnisse die Wahrscheinlichkeit 1/7 haben.

Der richtige Weg, dies zu tun, ist die Ablehnungsstichprobe: wiederholt eine unabhängige einheitliche Zufallsstichprobe s aus 0, 1, 2,…, {{X1} ziehen. } und lehnen (zum Beispiel) die Ergebnisse 0, 1, 2,…, ((RAND_MAX + 1) % 6) - 1 ab - wenn Sie eines davon erhalten, beginnen Sie von vorne; Andernfalls ergeben Sie s % 6.

unsigned int s;
while ((s = rand()) < ((unsigned long)RAND_MAX + 1) % 6)
    continue;
return s % 6;

Auf diese Weise ist die Menge der Ergebnisse von rand(), die wir akzeptieren, gleichmäßig durch 6 teilbar, und jedes mögliche Ergebnis von s % 6 wird durch die gleiche Anzahl von akzeptierten Ergebnissen von {erhalten {X2}} Wenn also rand() gleichmäßig verteilt ist, ist dies auch s. Es gibt keine Bindung an die Anzahl der Versuche, aber die erwartete Anzahl beträgt weniger als 2, und die Erfolgswahrscheinlichkeit wächst exponentiell mit der Anzahl der Versuche.

Die Wahl, welche Ergebnisse von rand() Sie ablehnen, ist unerheblich, vorausgesetzt, Sie ordnen jeder Ganzzahl unter 6 eine gleiche Anzahl zu. Der Code auf cppreference.com unterscheidet Wahl aufgrund des ersten oben genannten Problems: Es wird nichts über die Verteilung oder Unabhängigkeit der Ausgaben von rand() garantiert, und in der Praxis zeigten die niederwertigen Bits Muster, die nicht zufällig genug aussehen. (egal, dass die nächste Ausgabe eine deterministische Funktion der vorherigen ist).

Übung für den Leser: Beweisen Sie, dass der Code auf cppreference.com eine gleichmäßige Verteilung auf Würfelwürfeln ergibt, wenn rand() eine gleichmäßige Verteilung auf 0, 1, 2,…, RAND_MAX ergibt.

Übung für den Leser: Warum möchten Sie vielleicht die eine oder andere Teilmenge ablehnen? Welche Berechnung ist in beiden Fällen für jeden Versuch erforderlich?

Ein drittes Problem ist, dass der Samenraum so klein ist, dass selbst wenn der Samen gleichmäßig verteilt ist, ein Gegner, der mit Kenntnis Ihres Programms und einem Ergebnis, aber nicht dem Samen, bewaffnet ist, den Samen und die nachfolgenden Ergebnisse leicht vorhersagen kann, was ihn ausmacht scheinen doch nicht so zufällig zu sein. Denken Sie also nicht einmal daran, dies für die Kryptographie zu verwenden.

Mit einem geeigneten Zufallsgerät und Ihrer bevorzugten Zufalls-Engine wie dem allseits beliebten Mersenne-Twister std::mt19937 können Sie die ausgefallene überarbeitete Route und die std::uniform_int_distribution -Klasse von C ++ 11 mit Ihrem vierjährigen Würfelspiel spielen. alter Cousin, aber selbst das wird nicht für die Erzeugung von kryptografischem Schlüsselmaterial geeignet sein - und der Mersenne-Twister ist auch ein schreckliches Weltraumfresser, da ein Multi-Kilobyte-Zustand mit einer obszönen Einrichtungszeit Chaos im Cache Ihrer CPU anrichtet, also ist es schlecht sogar für zB parallele Monte-Carlo-Simulationen mit reproduzierbaren Bäumen von Unterberechnungen; seine Popularität ergibt sich wahrscheinlich hauptsächlich aus seinem eingängigen Namen. Aber Sie können es für Spielzeugwürfel verwenden, die wie in diesem Beispiel rollen!

Ein anderer Ansatz besteht darin, einen einfachen kryptografischen Pseudozufallszahlengenerator mit einem kleinen Status zu verwenden, z. B. einen einfachen PRNG zum schnellen Löschen von Schlüsseln oder nur eine Stream-Verschlüsselung wie AES-CTR oder ChaCha20, wenn Sie sicher sind ( z. B. in einer Monte-Carlo-Simulation für naturwissenschaftliche Forschung), dass die Vorhersage früherer Ergebnisse keine nachteiligen Folgen hat, wenn der Staat jemals kompromittiert wird.

13
Squeamish Ossifrage 18 Apr. 2018 im 18:29

Ich bin keineswegs ein erfahrener C ++ - Benutzer, war aber interessiert zu sehen, ob die anderen Antworten dazu std::rand()/((RAND_MAX + 1u)/6) ist weniger voreingenommen als 1+std::rand()%6 und gilt tatsächlich. Also habe ich ein Testprogramm geschrieben, um die Ergebnisse für beide Methoden zu tabellieren (ich habe seit Jahren kein C ++ mehr geschrieben, bitte überprüfen Sie es). Ein Link zum Ausführen des Codes befindet sich hier. Es wird auch wie folgt reproduziert:

// Example program
#include <cstdlib>
#include <iostream>
#include <ctime>
#include <string>

int main()
{
    std::srand(std::time(nullptr)); // use current time as seed for random generator

    // Roll the die 6000000 times using the supposedly unbiased method and keep track of the results

    int results[6] = {0,0,0,0,0,0};

    // roll a 6-sided die 20 times
    for (int n=0; n != 6000000; ++n) {
        int x = 7;
        while(x > 6) 
            x = 1 + std::rand()/((RAND_MAX + 1u)/6);  // Note: 1+rand()%6 is biased

        results[x-1]++;
    }

    for (int n=0; n !=6; n++) {
        std::cout << results[n] << ' ';
    }

    std::cout << "\n";


    // Roll the die 6000000 times using the supposedly biased method and keep track of the results

    int results_bias[6] = {0,0,0,0,0,0};

    // roll a 6-sided die 20 times
    for (int n=0; n != 6000000; ++n) {
        int x = 7;
        while(x > 6) 
            x = 1 + std::rand()%6;

        results_bias[x-1]++;
    }

    for (int n=0; n !=6; n++) {
        std::cout << results_bias[n] << ' ';
    }
}

Ich habe dann die Ausgabe davon genommen und die Funktion chisq.test in R verwendet, um einen Chi-Quadrat-Test durchzuführen, um festzustellen, ob die Ergebnisse signifikant von den erwarteten abweichen. Diese Frage zum Stapelaustausch geht detaillierter auf die Verwendung des Chi-Quadrat-Tests zum Testen der Fairness ein: Wie kann ich testen, ob ein Würfel fair ist?. Hier sind die Ergebnisse für einige Läufe:

> ?chisq.test
> unbias <- c(100150, 99658, 100319, 99342, 100418, 100113)
> bias <- c(100049, 100040, 100091, 99966, 100188, 99666 )

> chisq.test(unbias)

Chi-squared test for given probabilities

data:  unbias
X-squared = 8.6168, df = 5, p-value = 0.1254

> chisq.test(bias)

Chi-squared test for given probabilities

data:  bias
X-squared = 1.6034, df = 5, p-value = 0.9008

> unbias <- c(998630, 1001188, 998932, 1001048, 1000968, 999234 )
> bias <- c(1000071, 1000910, 999078, 1000080, 998786, 1001075   )
> chisq.test(unbias)

Chi-squared test for given probabilities

data:  unbias
X-squared = 7.051, df = 5, p-value = 0.2169

> chisq.test(bias)

Chi-squared test for given probabilities

data:  bias
X-squared = 4.319, df = 5, p-value = 0.5045

> unbias <- c(998630, 999010, 1000736, 999142, 1000631, 1001851)
> bias <- c(999803, 998651, 1000639, 1000735, 1000064,1000108)
> chisq.test(unbias)

Chi-squared test for given probabilities

data:  unbias
X-squared = 7.9592, df = 5, p-value = 0.1585

> chisq.test(bias)

Chi-squared test for given probabilities

data:  bias
X-squared = 2.8229, df = 5, p-value = 0.7273

In den drei Läufen, die ich durchgeführt habe, war der p-Wert für beide Methoden immer größer als die typischen Alpha-Werte, die zum Testen der Signifikanz verwendet wurden (0,05). Dies bedeutet, dass wir keinen von beiden als voreingenommen betrachten würden. Interessanterweise weist die vermeintlich unvoreingenommene Methode durchweg niedrigere p-Werte auf, was darauf hinweist, dass sie möglicherweise tatsächlich voreingenommener ist. Die Einschränkung ist, dass ich nur 3 Läufe gemacht habe.

UPDATE: Während ich meine Antwort schrieb, hat Konrad Rudolph eine Antwort gepostet, die den gleichen Ansatz verfolgt, aber ein ganz anderes Ergebnis erzielt. Ich habe nicht den Ruf, seine Antwort zu kommentieren, deshalb werde ich sie hier ansprechen. Erstens ist die Hauptsache, dass der Code, den er verwendet, bei jeder Ausführung denselben Startwert für den Zufallszahlengenerator verwendet. Wenn Sie den Samen ändern, erhalten Sie tatsächlich eine Vielzahl von Ergebnissen. Zweitens erhalten Sie eine Vielzahl von Ergebnissen, wenn Sie den Startwert nicht ändern, aber die Anzahl der Versuche ändern. Versuchen Sie, um eine Größenordnung zu erhöhen oder zu verringern, um zu sehen, was ich meine. Drittens gibt es einige ganzzahlige Kürzungen oder Rundungen, bei denen die erwarteten Werte nicht ganz genau sind. Es ist wahrscheinlich nicht genug, um einen Unterschied zu machen, aber es ist da.

Zusammenfassend lässt sich sagen, dass er zufällig den richtigen Samen und die richtige Anzahl von Versuchen erhalten hat, um ein falsches Ergebnis zu erzielen.

2
anjama 17 Apr. 2018 im 16:54

Man kann sich einen Zufallszahlengenerator als Arbeit an einem Strom von Binärziffern vorstellen. Der Generator wandelt den Stream in Zahlen um, indem er ihn in Stücke schneidet. Wenn die Funktion std:rand mit einem RAND_MAX von 32767 arbeitet, werden in jedem Slice 15 Bits verwendet.

Wenn man die Module einer Zahl zwischen 0 und einschließlich 32767 nimmt, findet man, dass 5462 '0' und '1', aber nur 5461 '2', '3', '4' und '5'. Daher ist das Ergebnis voreingenommen. Je größer der RAND_MAX-Wert ist, desto geringer ist die Vorspannung, die jedoch unvermeidlich ist.

Was nicht voreingenommen ist, ist eine Zahl im Bereich [0 .. (2 ^ n) -1]. Sie können eine (theoretisch) bessere Zahl im Bereich 0..5 erzeugen, indem Sie 3 Bits extrahieren, diese in eine Ganzzahl im Bereich 0..7 konvertieren und 6 und 7 ablehnen.

Man hofft, dass jedes Bit im Bitstrom die gleiche Chance hat, eine '0' oder eine '1' zu sein, unabhängig davon, wo es sich im Strom befindet oder welche Werte andere Bits haben. Dies ist in der Praxis außerordentlich schwierig. Die vielen verschiedenen Implementierungen von Software-PRNGs bieten unterschiedliche Kompromisse zwischen Geschwindigkeit und Qualität. Ein linearer Kongruenzgenerator wie std::rand bietet die schnellste Geschwindigkeit bei niedrigster Qualität. Ein kryptografischer Generator bietet höchste Qualität bei niedrigster Geschwindigkeit.

2
Simon G. 18 Apr. 2018 im 13:41