webentwicklung-frage-antwort-db.com.de

Warum sagen die Leute, dass bei der Verwendung eines Zufallszahlengenerators ein Modulo-Bias vorliegt?

Ich habe gesehen, dass diese Frage viel gestellt wurde, aber ich habe nie eine wirklich konkrete Antwort darauf gesehen. Ich werde hier einen Beitrag posten, der hoffentlich den Leuten helfen wird zu verstehen, warum es genau "modulo bias" gibt, wenn ein Zufallszahlengenerator verwendet wird, wie Rand() in C++.

252
user1413793

Also ist Rand() ein Pseudo-Zufallszahlengenerator, der eine natürliche Zahl zwischen 0 und Rand_MAX auswählt, die eine Konstante ist, die in cstdlib definiert ist (siehe diesen Artikel für einen allgemeinen Überblick über Rand()).

Was passiert nun, wenn Sie eine Zufallszahl zwischen 0 und 2 generieren möchten? Nehmen wir zur Erklärung an, dass Rand_MAX 10 ist und ich beschließe, eine Zufallszahl zwischen 0 und 2 zu generieren, indem ich Rand()%3 aufrufe. Rand()%3 erzeugt jedoch nicht mit gleicher Wahrscheinlichkeit die Zahlen zwischen 0 und 2! 

Wenn Rand() 0, 3, 6 oder 9 zurückgibt,Rand()%3 == 0. Daher ist P(0) = 4/11

Wenn Rand() 1, 4, 7 oder 10 zurückgibt,Rand()%3 == 1. Daher ist P(1) = 4/11 

Wenn Rand() 2, 5 oder 8 zurückgibt,Rand()%3 == 2. Daher ist P(2) = 3/11

Dadurch werden die Zahlen zwischen 0 und 2 nicht mit gleicher Wahrscheinlichkeit generiert. Für kleine Bereiche ist dies natürlich nicht das größte Problem, aber für einen größeren Bereich könnte dies die Verteilung verzerren und die kleineren Zahlen beeinflussen. 

Wann gibt Rand()%n also mit gleicher Wahrscheinlichkeit einen Zahlenbereich von 0 bis n-1 zurück? Wenn Rand_MAX%n == n - 1. In diesem Fall geben wir zusammen mit unserer früheren Annahme Rand() mit gleicher Wahrscheinlichkeit eine Zahl zwischen 0 und Rand_MAX zurück, die Modulo-Klassen von n wären ebenfalls gleichmäßig verteilt.

Wie lösen wir dieses Problem? Eine grobe Methode besteht darin, so lange Zufallszahlen zu generieren, bis Sie eine Zahl im gewünschten Bereich erhalten:

int x; 
do {
    x = Rand();
} while (x >= n);

dies ist jedoch ineffizient für niedrige Werte von n, da Sie nur eine n/Rand_MAX-Chance haben, einen Wert in Ihrem Bereich zu erhalten. Daher müssen Sie im Durchschnitt Rand_MAX/n-Aufrufe von Rand() durchführen.

Eine effizientere Formelmethode wäre, einen großen Bereich mit einer durch n teilbaren Länge zu verwenden, wie Rand_MAX - Rand_MAX % n, so lange Zufallszahlen zu generieren, bis Sie einen Wert erhalten, der im Bereich liegt, und dann den Modulus verwenden:

int x;

do {
    x = Rand();
} while (x >= (Rand_MAX - Rand_MAX % n));

x %= n;

Bei kleinen Werten von n erfordert dies selten mehr als einen Aufruf von Rand().


Zitierte Werke und weiterführende Literatur:


357
user1413793

Wählen Sie eine Zufallsauswahl, um die Verzerrung zu entfernen.

Update

Wir könnten den Code schnell machen, wenn wir nach einem durch n teilbaren x im Bereich suchen.

// Assumptions
// Rand() in [0, Rand_MAX]
// n in (0, Rand_MAX]

int x; 

// Keep searching for an x in a range divisible by n 
do {
    x = Rand();
} while (x >= Rand_MAX - (Rand_MAX % n)) 

x %= n;

Die obige Schleife sollte sehr schnell sein, sagen wir durchschnittlich 1 Iteration.

35

@ user1413793 ist bezüglich des Problems korrekt. Ich werde das nicht weiter besprechen, außer um einen Punkt zu machen: Ja, für kleine Werte von n und große Werte von Rand_MAX kann der Modulo-Bias sehr klein sein. Wenn Sie jedoch ein voreingenommenes Muster verwenden, müssen Sie die Verzerrung jedes Mal berücksichtigen, wenn Sie eine Zufallszahl berechnen und für verschiedene Fälle andere Muster auswählen. Und wenn Sie die falsche Wahl treffen, sind die Fehler, die es einführt, subtil und für den Komponententest fast unmöglich. Verglichen mit der Verwendung des richtigen Tools (wie arc4random_uniform) ist dies zusätzliche Arbeit, nicht weniger Arbeit. Mehr Arbeit zu leisten und eine schlechtere Lösung zu finden, ist ein schreckliches Engineering, vor allem wenn es richtig ist, wenn es auf den meisten Plattformen einfach ist.

Leider sind die Implementierungen der Lösung alle falsch oder weniger effizient als sie sein sollten. (Für jede Lösung gibt es verschiedene Kommentare, die die Probleme erläutern. Es wurde jedoch keine der Lösungen korrigiert, um sie zu lösen.) Dies wird den gelegentlichen Antwortsuchenden wahrscheinlich verwirren. Daher führe ich hier eine bekanntermaßen gute Implementierung aus.

Auch hier ist die beste Lösung die Verwendung von arc4random_uniform auf Plattformen, die diese bereitstellen, oder einer ähnlichen Lösung für Ihre Plattform (z. B. Random.nextInt auf Java). Es wird das Richtige tun, ohne dass Sie dafür Code zahlen müssen. Dies ist fast immer der richtige Aufruf.

Wenn Sie arc4random_uniform nicht haben, können Sie die Leistung von opensource nutzen, um genau zu sehen, wie es über einem RNG mit weiterem Bereich implementiert wird (ar4random in diesem Fall, aber ein ähnlicher Ansatz könnte auch auf anderen RNGs funktionieren). . 

Hier ist die OpenBSD-Implementierung :

/*
 * Calculate a uniformly distributed random number less than upper_bound
 * avoiding "modulo bias".
 *
 * Uniformity is achieved by generating new random numbers until the one
 * returned is outside the range [0, 2**32 % upper_bound).  This
 * guarantees the selected random number will be inside
 * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
 * after reduction modulo upper_bound.
 */
u_int32_t
arc4random_uniform(u_int32_t upper_bound)
{
    u_int32_t r, min;

    if (upper_bound < 2)
        return 0;

    /* 2**32 % x == (2**32 - x) % x */
    min = -upper_bound % upper_bound;

    /*
     * This could theoretically loop forever but each retry has
     * p > 0.5 (worst case, usually far better) of selecting a
     * number inside the range we need, so it should rarely need
     * to re-roll.
     */
    for (;;) {
        r = arc4random();
        if (r >= min)
            break;
    }

    return r % upper_bound;
}

Beachten Sie den neuesten Commit-Kommentar zu diesem Code für diejenigen, die ähnliche Dinge implementieren müssen:

Ändern Sie arc4random_uniform (), um den 2**32 % upper_bound'' as - upper_bound% upper_bound '' zu berechnen. Vereinfacht den Code und macht ihn zum Dies gilt sowohl für ILP32- als auch für LP64-Architekturen und für .__ auch etwas schneller. LP64-Architekturen mit einem 32-Bit-Rest statt eines 64-Bit Rest.

Daraufhin von Jorden Verwer auf tech @ .__ hingewiesen. ok deraadt; keine einwendungen von djm oder otto

Die Java-Implementierung ist auch leicht auffindbar (siehe vorherigen Link):

public int nextInt(int n) {
   if (n <= 0)
     throw new IllegalArgumentException("n must be positive");

   if ((n & -n) == n)  // i.e., n is a power of 2
     return (int)((n * (long)next(31)) >> 31);

   int bits, val;
   do {
       bits = next(31);
       val = bits % n;
   } while (bits - val + (n-1) < 0);
   return val;
 }
17
Rob Napier

Definition

Modulo Bias ist die inhärente Vorspannung bei der Verwendung von Modulo-Arithmetik, um eine Ausgabemenge auf eine Teilmenge der Eingabemenge zu reduzieren. Im Allgemeinen liegt eine Verzerrung vor, wenn die Abbildung zwischen Eingabe- und Ausgabesatz nicht gleichmäßig verteilt ist, wie im Fall der Verwendung von Modulo-Arithmetik, wenn die Größe des Ausgabesatzes kein Teiler der Größe des Eingabesatzes ist.

Diese Verzerrung ist beim Rechnen besonders schwer zu vermeiden, wenn Zahlen als Folgen von Bits dargestellt werden: 0s und 1s. Es ist ebenfalls äußerst schwierig, wirklich zufällige Quellen für Zufälligkeiten zu finden, die jedoch nicht Gegenstand dieser Diskussion sind. Für den Rest dieser Antwort wird angenommen, dass es eine unbegrenzte Quelle von wirklich zufälligen Bits gibt.

Problem Beispiel

Wir wollen einen Würfelwurf (0 bis 5) mit diesen zufälligen Bits simulieren. Es gibt 6 Möglichkeiten, also brauchen wir genug Bits, um die Zahl 6 darzustellen, was 3 Bits entspricht. Leider ergeben 3 zufällige Bits 8 mögliche Ergebnisse:

000 = 0, 001 = 1, 010 = 2, 011 = 3
100 = 4, 101 = 5, 110 = 6, 111 = 7

Wir können die Größe der Ergebnismenge auf genau 6 reduzieren, indem wir den Wert modulo 6 annehmen. Dies ist jedoch das Modulo-Bias -Problem: 110 ergibt eine 0 und 111 ergibt eine 1. Dieser Würfel ist geladen.

Potentielle Lösungen

Ansatz 0:

Anstatt sich auf Zufallsbits zu verlassen, könnte man theoretisch eine kleine Armee engagieren, die den ganzen Tag Würfel würfelt und die Ergebnisse in einer Datenbank aufzeichnet und dann jedes Ergebnis nur einmal verwendet. Dies ist ungefähr so ​​praktisch, wie es sich anhört, und würde höchstwahrscheinlich sowieso keine wirklich zufälligen Ergebnisse liefern (Wortspiel beabsichtigt).

Ansatz 1:

Anstatt den Modul zu verwenden, besteht eine naive, aber mathematisch korrekte Lösung darin, Ergebnisse zu verwerfen, die 110 Und 111 Ergeben, und es einfach mit 3 neuen Bits erneut zu versuchen. Leider bedeutet dies, dass 25% Chance für jede Rolle, dass eine erneute Rolle erforderlich ist, einschließlich jeder der erneuten Rollen sich. Dies ist offensichtlich für alle, außer für die trivialsten Verwendungen, unpraktisch.

Ansatz 2:

Verwenden Sie mehr Bits: Verwenden Sie 4 anstelle von 3 Bits. Dies ergibt 16 mögliche Ergebnisse. Ein erneutes Rollen, wenn das Ergebnis größer als 5 ist, macht die Sache natürlich noch schlimmer (10/16 = 62,5%), so dass allein nichts hilft.

Beachten Sie, dass 2 * 6 = 12 <16, so dass wir sicher weniger als 12 Ergebnisse erhalten und dieses Modulo 6 reduzieren können, um die Ergebnisse gleichmäßig zu verteilen. Die anderen 4 Ergebnisse müssen verworfen und dann wie im vorherigen Ansatz neu gewürfelt werden.

Klingt zunächst gut, aber lassen Sie uns die Mathematik überprüfen:

4 discarded results / 16 possibilities = 25%

In diesem Fall hat 1 zusätzliches Bit hat nicht geholfen überhaupt nicht geholfen!

Dieses Ergebnis ist bedauerlich, aber versuchen wir es noch einmal mit 5 Bits:

32 % 6 = 2 discarded results; and
2 discarded results / 32 possibilities = 6.25%

Eine deutliche Verbesserung, aber in vielen praktischen Fällen nicht gut genug. Die gute Nachricht ist: Das Hinzufügen weiterer Bits erhöht niemals die Wahrscheinlichkeit, verworfen und neu gewürfelt werden zu müssen.. Dies gilt nicht nur für Würfel, sondern in allen Fällen.

Wie gezeigt jedoch ändert das Hinzufügen eines zusätzlichen Bits möglicherweise nichts. Wenn wir unseren Wurf auf 6 Bits erhöhen, bleibt die Wahrscheinlichkeit 6,25%.

Dies wirft 2 zusätzliche Fragen auf:

  1. Wenn wir genügend Bits hinzufügen, gibt es eine Garantie dafür, dass die Wahrscheinlichkeit eines Verwerfens abnimmt?
  2. Wie viele Bits sind im allgemeinen Fall ausreichend ?

Allgemeine Lösung

Zum Glück ist die Antwort auf die erste Frage ja. Das Problem bei 6 ist, dass 2 ^ x mod 6 zwischen 2 und 4 wechselt, die zufällig ein Vielfaches von 2 sind, so dass für ein gerades x> 1

[2^x mod 6] / 2^x == [2^(x+1) mod 6] / 2^(x+1)

Somit ist 6 eher eine Ausnahme als die Regel. Es ist möglich, auf die gleiche Weise größere Module zu finden, die aufeinanderfolgende Potenzen von 2 ergeben, aber dies muss sich schließlich ändern, und die Wahrscheinlichkeit eines Verwerfens wird verringert.

Ohne weiteren Beweis bietet die Verwendung von doppelte Anzahl der erforderlichen Bits im Allgemeinen eine geringere, in der Regel unbedeutende Wahrscheinlichkeit für ein Verwerfen.

Konzeptioneller Beweiß

Hier ist ein Beispielprogramm, das OpenSSLs libcrypo verwendet, um zufällige Bytes zu liefern. Stellen Sie beim Kompilieren sicher, dass Sie mit -lcrypto Auf die Bibliothek verlinken, die für die meisten Benutzer verfügbar sein sollte.

#include <iostream>
#include <assert.h>
#include <limits>
#include <openssl/Rand.h>

volatile uint32_t dummy;
uint64_t discardCount;

uint32_t uniformRandomUint32(uint32_t upperBound)
{
    assert(Rand_status() == 1);
    uint64_t discard = (std::numeric_limits<uint64_t>::max() - upperBound) % upperBound;
    uint64_t randomPool = Rand_bytes((uint8_t*)(&randomPool), sizeof(randomPool));

    while(randomPool > (std::numeric_limits<uint64_t>::max() - discard)) {
        Rand_bytes((uint8_t*)(&randomPool), sizeof(randomPool));
        ++discardCount;
    }

    return randomPool % upperBound;
}

int main() {
    discardCount = 0;

    const uint32_t MODULUS = (1ul << 31)-1;
    const uint32_t ROLLS = 10000000;

    for(uint32_t i = 0; i < ROLLS; ++i) {
        dummy = uniformRandomUint32(MODULUS);
    }
    std::cout << "Discard count = " << discardCount << std::endl;
}

Ich empfehle, mit den Werten MODULUS und ROLLS zu spielen, um zu sehen, wie viele Re-Rolls unter den meisten Bedingungen tatsächlich stattfinden. Eine skeptische Person möchte möglicherweise auch die berechneten Werte in einer Datei speichern und sicherstellen, dass die Verteilung normal erscheint.

12
Jim Wood

Es gibt zwei übliche Beanstandungen bei der Verwendung von Modulo.

  • eine gilt für alle Generatoren. Im Grenzfall ist das leichter zu erkennen. Wenn Ihr Generator über einen Rand_MAX verfügt, der 2 ist (der nicht dem C-Standard entspricht) und Sie nur 0 oder 1 als Wert verwenden möchten, wird die Verwendung von modulo 0 doppelt so oft (wenn der Generator 0 und 2 generiert), als dies der Fall ist generiere 1 (wenn der Generator 1 erzeugt). Beachten Sie, dass dies zutrifft, sobald Sie keine Werte löschen. Unabhängig von der Zuordnung, die Sie von den Generatorwerten zu den gewünschten Werten verwenden, wird eines doppelt so oft vorkommen wie das andere.

  • bei einigen Generatoren sind die weniger signifikanten Bits, zumindest für einige ihrer Parameter, weniger zufällig als die anderen, aber leider haben diese Parameter andere interessante Eigenschaften (so hat Rand_MAX eine weniger als eine Potenz von 2). Das Problem ist allgemein bekannt und die Bibliotheksimplementierung wird das Problem wahrscheinlich lange Zeit vermeiden (z. B. verwenden die Beispielimplementierungen Rand () im C-Standard diese Art von Generator, lassen aber die 16 niederwertigen Bits fallen), aber einige beschweren sich darüber das und du kannst Pech haben

Mit so etwas wie

int alea(int n){ 
 assert (0 < n && n <= Rand_MAX); 
 int partSize = 
      n == Rand_MAX ? 1 : 1 + (Rand_MAX-n)/(n+1); 
 int maxUsefull = partSize * n + (partSize-1); 
 int draw; 
 do { 
   draw = Rand(); 
 } while (draw > maxUsefull); 
 return draw/partSize; 
}

durch das Erzeugen einer Zufallszahl zwischen 0 und n werden beide Probleme vermieden (und ein Überlauf mit Rand_MAX == INT_MAX wird vermieden).

Übrigens, C++ 11 führte standardmäßige Wege zur Reduktion und andere Generatoren als Rand () ein.

9
AProgrammer

Marks Lösung (Die akzeptierte Lösung) ist nahezu perfekt.

int x;

do {
    x = Rand();
} while (x >= (Rand_MAX - Rand_MAX % n));

x %= n;

25. März 16 um 23:16 Uhr bearbeitet

Mark Amery 39k21170211

Es gibt jedoch einen Vorbehalt, der 1 gültige Ergebnissätze in jedem Szenario verwirft, in dem Rand_MAX (RM) um 1 kleiner ist als ein Vielfaches von N (wobei N = Anzahl der möglichen gültigen Ergebnisse).

wenn also die Anzahl der verworfenen Werte (D) gleich N ist, handelt es sich tatsächlich um eine gültige Menge (V), nicht um eine ungültige Menge (I).

Mit Marks Lösung werden Werte verworfen, wenn: X => RM - RM% N

EG: 

Ran Max Value (RM) = 255
Valid Outcome (N) = 4

When X => 252, Discarded values for X are: 252, 253, 254, 255

So, if Random Value Selected (X) = {252, 253, 254, 255}

Number of discarded Values (I) = RM % N + 1 == N

 IE:

 I = RM % N + 1
 I = 255 % 4 + 1
 I = 3 + 1
 I = 4

   X => ( RM - RM % N )
 255 => (255 - 255 % 4) 
 255 => (255 - 3)
 255 => (252)

 Discard Returns $True

Wie Sie im obigen Beispiel sehen können, würden wir, wenn der Wert von X (die Zufallszahl, die wir von der ursprünglichen Funktion erhalten) 252, 253, 254 oder 255 ist, den Wert verwerfen, obwohl diese vier Werte einen gültigen Satz von zurückgegebenen Werten enthalten .

IE: Wenn die Anzahl der verworfenen Werte (I) = N (Anzahl der gültigen Ergebnisse) ist, wird ein gültiger Satz von Rückgabewerten von der ursprünglichen Funktion verworfen.

Wenn wir die Differenz zwischen den Werten N und RM als D beschreiben, dh:

D = (RM - N)

Wenn dann der Wert von D kleiner wird, steigt der Prozentsatz nicht benötigter Wiederholungen aufgrund dieses Verfahrens bei jedem natürlichen Multiplikationsfaktor. (Wenn Rand_MAX NICHT mit einer Primzahl übereinstimmt, ist dies von gültiger Bedeutung.)

Z.B:

RM=255 , N=2 Then: D = 253, Lost percentage = 0.78125%

RM=255 , N=4 Then: D = 251, Lost percentage = 1.5625%
RM=255 , N=8 Then: D = 247, Lost percentage = 3.125%
RM=255 , N=16 Then: D = 239, Lost percentage = 6.25%
RM=255 , N=32 Then: D = 223, Lost percentage = 12.5%
RM=255 , N=64 Then: D = 191, Lost percentage = 25%
RM=255 , N= 128 Then D = 127, Lost percentage = 50%

Da der Prozentsatz der erforderlichen Rerolls steigt, je näher N an RM herankommt, kann dies bei vielen verschiedenen Werten von Belang sein, abhängig von den Einschränkungen des Systems, das den Code ausführt, und den gesuchten Werten.

Um dies zu negieren, können wir eine einfache Änderung vornehmen. Wie hier gezeigt:

 int x;

 do {
     x = Rand();
 } while (x > (Rand_MAX - ( ( ( Rand_MAX % n ) + 1 ) % n) );

 x %= n;

Dies stellt eine allgemeinere Version der Formel bereit, die die zusätzlichen Besonderheiten der Verwendung des Moduls zur Definition Ihrer Maximalwerte berücksichtigt.

Beispiele für die Verwendung eines kleinen Wertes für Rand_MAX, der ein Multiplikativ von N ist.

Mark'original Version:

Rand_MAX = 3, n = 2, Values in Rand_MAX = 0,1,2,3, Valid Sets = 0,1 and 2,3.
When X >= (Rand_MAX - ( Rand_MAX % n ) )
When X >= 2 the value will be discarded, even though the set is valid.

Generalisierte Version 1:

Rand_MAX = 3, n = 2, Values in Rand_MAX = 0,1,2,3, Valid Sets = 0,1 and 2,3.
When X > (Rand_MAX - ( ( Rand_MAX % n  ) + 1 ) % n )
When X > 3 the value would be discarded, but this is not a vlue in the set Rand_MAX so there will be no discard.

In dem Fall, in dem N die Anzahl der Werte in Rand_MAX sein soll; In diesem Fall können Sie N = Rand_MAX +1 setzen, sofern nicht Rand_MAX = INT_MAX ist.

Loop-weise können Sie einfach N = 1 verwenden, und jeder Wert von X wird jedoch akzeptiert und eine IF-Anweisung für Ihren endgültigen Multiplikator eingefügt. Aber vielleicht haben Sie Code, der einen gültigen Grund hat, eine 1 zurückzugeben, wenn die Funktion mit n = 1 aufgerufen wird.

Daher ist es möglicherweise besser, eine 0 zu verwenden, die normalerweise einen Div 0-Fehler liefert, wenn Sie n = Rand_MAX + 1 haben möchten 

verallgemeinerte Version 2:

int x;

if n != 0 {
    do {
        x = Rand();
    } while (x > (Rand_MAX - ( ( ( Rand_MAX % n ) + 1 ) % n) );

    x %= n;
} else {
    x = Rand();
}

Beide Lösungen lösen das Problem mit unnötig verworfenen gültigen Ergebnissen, die auftreten werden, wenn RM + 1 ein Produkt von n ist.

Die zweite Version deckt auch das Edge-Fall-Szenario ab, wenn n für die Gesamtmenge der möglichen Werte von Rand_MAX benötigt wird.

Der modifizierte Ansatz ist in beiden Fällen derselbe und ermöglicht eine allgemeinere Lösung für das Erfordernis, gültige Zufallszahlen bereitzustellen und verworfene Werte zu minimieren.

Wiederholen:

Die allgemeine Basislösung, die das Beispiel der Marke erweitert:

 int x;

 do {
     x = Rand();
 } while (x > (Rand_MAX - ( ( ( Rand_MAX % n ) + 1 ) % n) );

 x %= n;

Die erweiterte allgemeine Lösung, die ein zusätzliches Szenario von Rand_MAX + 1 = n ermöglicht:

int x;

if n != 0 {
    do {
        x = Rand();
    } while (x > (Rand_MAX - ( ( ( Rand_MAX % n ) + 1 ) % n) );

    x %= n;
} else {
    x = Rand();
}
6
Ben Personick

Mit einem Rand_MAX-Wert von 3 (in der Realität sollte es viel höher sein als der, aber die Verzerrung würde immer noch existieren), macht es aus diesen Berechnungen Sinn, dass eine Verzerrung vorliegt:

1 % 2 = 12 % 2 = 03 % 2 = 1random_between(1, 3) % 2 = more likely a 1

In diesem Fall sollten Sie den % 2 nicht verwenden, wenn Sie eine zufällige Zahl zwischen 0 und 1 wünschen. Sie könnten eine Zufallszahl zwischen 0 und 2 erhalten, indem Sie % 3 ausführen. In diesem Fall gilt: Rand_MAX ist ein Vielfaches von 3.

Eine andere Methode

Es ist viel einfacher, aber zu anderen Antworten hinzuzufügen, hier ist meine Lösung, um eine Zufallszahl zwischen 0 und n - 1 zu erhalten, also n verschiedene Möglichkeiten, ohne Vorurteile.

  • die Anzahl der Bits (nicht Bytes), die zum Kodieren der Anzahl der Möglichkeiten benötigt wird, ist die Anzahl der Bits der Zufallsdaten, die Sie benötigen
  • codiere die Zahl aus Zufallsbits
  • wenn diese Nummer >= n ist, starten Sie neu (kein Modulo).

Wirklich zufällige Daten sind nicht leicht zu bekommen, warum also mehr Bits als nötig verwenden.

Nachfolgend finden Sie ein Beispiel in Smalltalk, bei dem ein Bitcache aus einem Pseudozufallszahlengenerator verwendet wird. Ich bin kein Sicherheitsexperte, also auf eigenes Risiko.

next: n

    | bitSize r from to |
    n < 0 ifTrue: [^0 - (self next: 0 - n)].
    n = 0 ifTrue: [^nil].
    n = 1 ifTrue: [^0].
    cache isNil ifTrue: [cache := OrderedCollection new].
    cache size < (self randmax highBit) ifTrue: [
        Security.DSSRandom default next asByteArray do: [ :byte |
            (1 to: 8) do: [ :i |    cache add: (byte bitAt: i)]
        ]
    ].
    r := 0.
    bitSize := n highBit.
    to := cache size.
    from := to - bitSize + 1.
    (from to: to) do: [ :i |
        r := r bitAt: i - from + 1 put: (cache at: i)
    ].
    cache removeFrom: from to: to.
    r >= n ifTrue: [^self next: n].
    ^r
0
Rivenfall