Einheitlichkeit von Zufallszahlen, die Modulo N genommen werden

Lesezeit: 5 Minuten

Eine gängige Methode zum Auswählen einer Zufallszahl in [0, n) is to take the result of rand() modulo n: rand() % n. However, even if the results returned by the available rand() implementation are fully uniform, shouldn’t there be a problem with the uniformity of the resulting [0, n) numbers when RAND_MAX + 1 does not divide evenly by n? E.g. suppose RAND_MAX is 2, and n is 2. Then out of 3 possible rand() outputs: 0, 1 and 2, we get 0, 1 and 0 respectively when we use them modulo n. Therefore the output will not be uniform at all.

Is this a real problem in practice? What is a better way of choosing random numbers in [0, n) uniformly deriving from rand() output, preferably without any floating point arithmetic?

  • possible duplicate of What is the optimal algorithm for generating an unbiased random integer within a range?

    – hammar

    Oct 27, 2012 at 21:54

  • Not quite a duplicate, since the bias issue is taken for granted and the question is “is this really a problem in practice?” I’ve tried to quantify the bias in my answer.

    – slashingweapon

    Oct 27, 2012 at 21:58

  • See: eternallyconfuzzled.com/arts/jsw_art_rand.aspx

    – Alex Reynolds

    Oct 27, 2012 at 22:09

  • @MuriloVasconcelos: yes, I’ve just accepted one.

    – dragonroot

    Oct 29, 2012 at 7:07

  • Possible duplicate of Why do people say there is modulo bias when using a random number generator?

    – emlai

    Oct 1, 2016 at 9:34

You are correct, rand() % N is not precisely uniformly distributed. Precisely how much that matters depends on the range of numbers you want and the degree of randomness you want, but if you want enough randomness that you’d even care about it you don’t want to use rand() anyway. Get a real random number generator.

That said, to get a real random distribution, mod to the next power of 2 and sample until you get one in the range you want (e.g. for 0-9, use while(n = rand()%0x10 > 10);).

  • +1 for the workaround, but usually the low bits of rand() have very bad entropy. It would be smarter to use the high bits.

    – R.. GitHub STOP HELPING ICE

    Oct 27, 2012 at 22:21

  • @Kevin: Are you judging any particular implementation of rand(), i.e. the one found in modern glibc?

    – dragonroot

    Oct 27, 2012 at 23:44

  • @ToddLehman On my system (OSX 10.10), the low bits are certainly not uniform. Run this on the command line for a live-updating count: pastebin.com/D5r7we3H

    – Kevin

    Jul 30, 2015 at 4:44

  • @ToddLehman: I meant my suspicion is that most implementations use raw LCG output, not just LCG “at [the] Ader”.

    – R.. GitHub HÖR AUF, EIS ZU HELFEN

    30. Juli 2015 um 4:51 Uhr

  • @ToddLehman: Ich denke, deine Hoffnungen sind fehl am Platz. rand ist hoffnungslos schlecht (es kann höchstens erzeugen UINT_MAX mögliche Sequenzen aufgrund srand‘s-Signatur) und der Versuch, es “besser” zu machen, ermutigt die Leute nur, es zu benutzen. Das Rollen Ihres eigenen anständigen (nicht kryptografischen) PRNG sind nur ein paar Zeilen, und das sollten Sie wirklich tun – über die Sequenzqualität hinaus bietet es Ihnen nützliche Eigenschaften wie das Fehlen eines globalen Status, die Wiederaufsetzbarkeit und die plattformübergreifende Gleiche-Sequenz-für-Gleiche -Samen.

    – R.. GitHub HÖR AUF, EIS ZU HELFEN

    30. Juli 2015 um 13:50 Uhr

Benutzer-Avatar
Hiebwaffe

Das hängt ab von:

  • Der Wert von RAND_MAX
  • Ihr Wert von N

Nehmen wir an, Ihr RAND_MAX ist 2^32. Wenn N ziemlich klein ist (sagen wir 2), dann ist die Abweichung 1/2^31 – oder zu klein, um es zu bemerken.

Aber wenn N etwas größer ist, sagen wir 2^20, dann ist die Abweichung 1/2^12 oder etwa 1 in 4096. Viel größer, aber immer noch ziemlich klein.

  • Im Gegenteil, ich denke, die Antwort ist genau richtig. Wir gehen von einem PRNG aus, der Zahlen mit perfekter Verteilung generiert. Die Frage ist, kümmern wir uns um die Voreingenommenheit? Ich habe versucht, eine Möglichkeit zu bieten, die Voreingenommenheit zu quantifizieren, damit der Fragesteller selbst feststellen kann, ob es für ihn tolerierbar ist. Das ist alles sehr sprachunspezifisch.

    – Hiebwaffe

    27. Oktober 2012 um 22:00 Uhr


  • Einige Systeme haben eine RAND_MAX von 0xffffführt zu a viel größere Vorspannung.

    – Kevin

    27. Oktober 2012 um 22:04 Uhr

  • Schlechter. Visual C++-Implementierungen haben RAND_MAX==0x7FFF, übriggeblieben von 16-Bit MSC 3.0 unter MS-DOS.

    – Mike Housky

    27. Oktober 2012 um 22:15 Uhr

  • @slashingweapon können Sie mich auf einen Link / eine Ressource verweisen, um die Verzerrung formal zu berechnen?

    – der Mann, der die Welt verkaufte

    17. Februar 2015 um 7:35 Uhr

Ein Ansatz, den Sie tun können, ist der folgende:

Den Wert kennen Ndu machst R_MAX = ((RAND_MAX + 1) / N) * N; für Einheitlichkeit.

So können Sie Ihre Gewohnheit machen rand() Funktion:

int custom_rand(int mod) {
    int x = rand();
    const int R_MAX = ((RAND_MAX + 1) / mod) * mod;    

    while (x > R_MAX) { // discard the result if it is bigger
        x = rand();
    }

    return (x % mod);
}

  • was ist, wenn rand_max 2^32-1 ist?

    – Eamon Nerbonne

    22. November 2014 um 10:06 Uhr

  • Wann RAND_MAX == INT_MAX (ein häufiger Vorfall). RAND_MAX + 1 –> undefiniertes Verhalten – (evtl INT_MIN).

    – chux – Wiedereinsetzung von Monica

    30. Dezember 2014 um 20:12 Uhr

  • Ich denke, du willst es wirklich R_MAX = (RAND_MAX / N) * N; und while (x >= R_MAX)sonst haben Sie eine Tendenz, mehr Nullen zu produzieren, weil R_MAX % mod == 0. Auch eine do { x = rand(); } while (x >= R_MAX) wäre hier besser, denn dann würdest du nicht schreiben x = rand(); zweimal.

    – Todd Lehmann

    30. Juli 2015 um 3:59 Uhr


Es gibt zwei Probleme bei der Verwendung von Rest (% ist kein “Modulo”-Operator in C) für eine einheitliche Zufallszahl über einen begrenzten Bereich. Erstens gibt es eine leichte Neigung zu kleineren Zahlen (oben erwähnt) und zweitens neigen typische PRNGs dazu, in den Bits niedriger Ordnung weniger zufällig zu sein. Ich erinnere mich an Knuth (The Art of Computer Programming, Band II, Seminumerical Algorithms) zusammen mit der Behauptung, dass rand()%2 (nach der Übersetzung von MIX nach C) eine schlechte Quelle für zufällige Einzelbits ist. Es ist besser, (rand() > RAND_MAX/2) auszuwählen (oder ein höherwertiges Bit zu testen, wenn RAND_MAX fast eine Potenz von 2 ist.)

Der Rest sollte gut genug sein, um gelegentlich in kleinen Intervallen verwendet zu werden. Vermeiden Sie es für Simulationen. Vermeiden Sie eigentlich rand() ganz für große Simulationen oder “Monte-Carlo”-Berechnungen. Implementierungen haben in der Regel einen Zeitraum in der Größenordnung von 2^32 oder weniger. Es ist nicht schwer, 4 Milliarden Versuche auf einem Prozessor mit 2+ GHz zu übertreffen.

1157710cookie-checkEinheitlichkeit von Zufallszahlen, die Modulo N genommen werden

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

Privacy policy