So generieren Sie eine zufällige Ganzzahl aus einem Bereich

Dies ist eine Fortsetzung einer zuvor gestellten Frage:

Wie generiere ich eine Zufallszahl in C?

Ich möchte in der Lage sein, eine Zufallszahl aus einem bestimmten Bereich wie 1 bis 6 zu generieren, um die Seiten eines Würfels nachzuahmen.

Wie würde ich das machen?

Alle bisherigen Antworten sind mathematisch falsch. Die Rückgabe rand() % Ngibt nicht einheitlich eine Zahl im Bereich an, es [0, N)sei denn, Ndie Länge des Intervalls, in das die rand()Rückgabe erfolgt (dh eine Potenz von 2). Außerdem hat man keine Ahnung, ob die Module von rand()unabhängig sind: Es ist möglich, dass sie gehen 0, 1, 2, ..., was einheitlich, aber nicht sehr zufällig ist. Die einzige Annahme, die vernünftig erscheint, ist die, dass rand()eine Poisson-Verteilung ausgegeben wird: Zwei beliebige nicht überlappende Teilintervalle derselben Größe sind gleich wahrscheinlich und unabhängig. Für eine endliche Menge von Werten impliziert dies eine gleichmäßige Verteilung und stellt auch sicher, dass die Werte von rand()gut verteilt sind.

Dies bedeutet, dass der einzig richtige Weg, den Bereich von rand()zu ändern, darin besteht, ihn in Kästchen zu unterteilen. Wenn RAND_MAX == 11Sie beispielsweise einen Bereich von möchten 1..6, sollten Sie {0,1}1, {2,3}2 usw. zuweisen . Dies sind disjunkte, gleich große Intervalle und somit gleichmäßig und unabhängig verteilt.

Der Vorschlag, eine Gleitkommadivision zu verwenden, ist mathematisch plausibel, weist jedoch im Prinzip Rundungsprobleme auf. Vielleicht doubleist die Präzision hoch genug, damit es funktioniert. vielleicht nicht. Ich weiß es nicht und ich möchte es nicht herausfinden müssen; In jedem Fall ist die Antwort systemabhängig.

Der richtige Weg ist die Verwendung von Ganzzahlarithmetik. Das heißt, Sie möchten so etwas wie das Folgende:

#include <stdlib.h> // For random(), RAND_MAX

// Assumes 0 <= max <= RAND_MAX
// Returns in the closed interval [0, max]
long random_at_most(long max) {
  unsigned long
    // max <= RAND_MAX < ULONG_MAX, so this is okay.
    num_bins = (unsigned long) max + 1,
    num_rand = (unsigned long) RAND_MAX + 1,
    bin_size = num_rand / num_bins,
    defect   = num_rand % num_bins;

  long x;
  do {
   x = random();
  }
  // This is carefully written not to overflow
  while (num_rand - defect <= (unsigned long)x);

  // Truncated division is intentional
  return x/bin_size;
}

Die Schleife ist notwendig, um eine perfekt gleichmäßige Verteilung zu erhalten. Wenn Sie beispielsweise Zufallszahlen von 0 bis 2 erhalten und nur solche von 0 bis 1 möchten, ziehen Sie einfach weiter, bis Sie keine 2 mehr erhalten. Es ist nicht schwer zu überprüfen, ob dies mit gleicher Wahrscheinlichkeit 0 oder 1 ergibt. Diese Methode wird auch in dem Link beschrieben, den nos in ihrer Antwort angegeben haben, obwohl sie unterschiedlich codiert sind. Ich verwende random()eher als rand()weil es eine bessere Verteilung hat (wie auf der Manpage für angegeben rand()).

Wenn Sie zufällige Werte außerhalb des Standardbereichs erhalten möchten, [0, RAND_MAX]müssen Sie etwas Schwieriges tun. Vielleicht ist die zweckmäßigste ist eine Funktion zu definieren , random_extended()die zieht nBits (mit random_at_most()) und kehrt in [0, 2**n), und wenden Sie dann random_at_most()mit random_extended()anstelle von random()(und 2**n - 1anstelle von RAND_MAXals) zu ziehen , um einen zufälligen Wert weniger 2**n, vorausgesetzt , Sie einen numerischen Typen haben, so halten kann , ein Wert. Schließlich, natürlich können Sie Werte erhalten in [min, max]Verwendung min + random_at_most(max - min), einschließlich negativer Werte.

Nach der Antwort von @Ryan Reich dachte ich, ich würde meine bereinigte Version anbieten. Die Prüfung der ersten Grenzen ist angesichts der Prüfung der zweiten Grenzen nicht erforderlich, und ich habe sie eher iterativ als rekursiv gemacht. Es gibt Werte im Bereich [min, max] zurück, wobei max >= minund 1+max-min < RAND_MAX.

unsigned int rand_interval(unsigned int min, unsigned int max)
{
    int r;
    const unsigned int range = 1 + max - min;
    const unsigned int buckets = RAND_MAX / range;
    const unsigned int limit = buckets * range;

    /* Create equal size buckets all in a row, then fire randomly towards
     * the buckets until you land in one of them. All buckets are equally
     * likely. If you land off the end of the line of buckets, try again. */
    do
    {
        r = rand();
    } while (r >= limit);

    return min + (r / buckets);
}

Hier ist eine Formel, wenn Sie die Max- und Min-Werte eines Bereichs kennen und Zahlen einschließlich zwischen den Bereichen generieren möchten:

r = (rand() % (max + 1 - min)) + min

unsigned int
randr(unsigned int min, unsigned int max)
{
       double scaled = (double)rand()/RAND_MAX;

       return (max - min +1)*scaled + min;
}

Sehen Sie hier für weitere Optionen.

Würden Sie nicht einfach tun:

srand(time(NULL));
int r = ( rand() % 6 ) + 1;

%ist der Moduloperator. Im Wesentlichen wird es nur durch 6 geteilt und der Rest ... von 0 - 5 zurückgegeben

Für diejenigen, die das Bias-Problem verstehen, aber die unvorhersehbare Laufzeit von auf Zurückweisung basierenden Methoden nicht ertragen können, erzeugt diese Reihe eine zunehmend weniger voreingenommene zufällige Ganzzahl im [0, n-1]Intervall:

r = n / 2;
r = (rand() * n + r) / (RAND_MAX + 1);
r = (rand() * n + r) / (RAND_MAX + 1);
r = (rand() * n + r) / (RAND_MAX + 1);
...

Dies geschieht durch Synthetisieren einer hochpräzisen Festpunkt-Zufallszahl von i * log_2(RAND_MAX + 1)Bits (wobei idie Anzahl der Iterationen ist) und Durchführen einer langen Multiplikation mit n.

Wenn die Anzahl der Bits im Vergleich zu ausreichend groß ist, nwird die Vorspannung unermesslich klein.

Es spielt keine Rolle, ob RAND_MAX + 1es kleiner als n(wie in dieser Frage ) ist oder ob es keine Zweierpotenz ist, aber es muss darauf geachtet werden, einen ganzzahligen Überlauf zu vermeiden, wenn er RAND_MAX * ngroß ist.

Um die in anderen Antworten vorgeschlagene Modulo-Verzerrung zu vermeiden, können Sie immer Folgendes verwenden:

arc4random_uniform(MAX-MIN)+MIN

Wobei "MAX" die Obergrenze und "MIN" die Untergrenze ist. Zum Beispiel für Zahlen zwischen 10 und 20:

arc4random_uniform(20-10)+10

arc4random_uniform(10)+10

Einfache Lösung und besser als "rand ()% N".

Hier ist ein etwas einfacherer Algorithmus als die Lösung von Ryan Reich:

/// Begin and end are *inclusive*; => [begin, end]
uint32_t getRandInterval(uint32_t begin, uint32_t end) {
    uint32_t range = (end - begin) + 1;
    uint32_t limit = ((uint64_t)RAND_MAX + 1) - (((uint64_t)RAND_MAX + 1) % range);

    /* Imagine range-sized buckets all in a row, then fire randomly towards
     * the buckets until you land in one of them. All buckets are equally
     * likely. If you land off the end of the line of buckets, try again. */
    uint32_t randVal = rand();
    while (randVal >= limit) randVal = rand();

    /// Return the position you hit in the bucket + begin as random number
    return (randVal % range) + begin;
}

Example (RAND_MAX := 16, begin := 2, end := 7)
    => range := 6  (1 + end - begin)
    => limit := 12 (RAND_MAX + 1) - ((RAND_MAX + 1) % range)

The limit is always a multiple of the range,
so we can split it into range-sized buckets:
    Possible-rand-output: 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
    Buckets:             [0, 1, 2, 3, 4, 5][0, 1, 2, 3, 4, 5][X, X, X, X, X]
    Buckets + begin:     [2, 3, 4, 5, 6, 7][2, 3, 4, 5, 6, 7][X, X, X, X, X]

1st call to rand() => 13
    → 13 is not in the bucket-range anymore (>= limit), while-condition is true
        → retry...
2nd call to rand() => 7
    → 7 is in the bucket-range (< limit), while-condition is false
        → Get the corresponding bucket-value 1 (randVal % range) and add begin
    => 3

Während Ryan richtig ist, kann die Lösung viel einfacher sein, basierend auf dem, was über die Quelle der Zufälligkeit bekannt ist. So geben Sie das Problem erneut an:

• Es gibt eine Zufallsquelle, die ganzzahlige Zahlen im Bereich [0, MAX)mit gleichmäßiger Verteilung ausgibt .
• Das Ziel ist es, gleichmäßig verteilte zufällige Ganzzahlen in einem Bereich zu erzeugen, in [rmin, rmax]dem 0 <= rmin < rmax < MAX.

Wenn nach meiner Erfahrung die Anzahl der Behälter (oder "Kisten") erheblich kleiner als der Bereich der ursprünglichen Zahlen ist und die ursprüngliche Quelle kryptografisch stark ist, besteht keine Notwendigkeit, all diese Rigamarole durchzugehen, und eine einfache Modulo-Teilung würde dies tun genügen (wie output = rnd.next() % (rmax+1)wenn rmin == 0) und erzeugen Zufallszahlen, die gleichmäßig "genug" und ohne Geschwindigkeitsverlust verteilt sind. Der Schlüsselfaktor ist die Zufallsquelle (dh Kinder, versuchen Sie dies nicht zu Hause mit rand()).

Hier ist ein Beispiel / ein Beweis dafür, wie es in der Praxis funktioniert. Ich wollte Zufallszahlen von 1 bis 22 generieren, mit einer kryptografisch starken Quelle, die zufällige Bytes erzeugt (basierend auf Intel RDRAND). Die Ergebnisse sind:

Rnd distribution test (22 boxes, numbers of entries in each box):     
 1: 409443    4.55%
 2: 408736    4.54%
 3: 408557    4.54%
 4: 409125    4.55%
 5: 408812    4.54%
 6: 409418    4.55%
 7: 408365    4.54%
 8: 407992    4.53%
 9: 409262    4.55%
10: 408112    4.53%
11: 409995    4.56%
12: 409810    4.55%
13: 409638    4.55%
14: 408905    4.54%
15: 408484    4.54%
16: 408211    4.54%
17: 409773    4.55%
18: 409597    4.55%
19: 409727    4.55%
20: 409062    4.55%
21: 409634    4.55%
22: 409342    4.55%   
total: 100.00%

Dies ist so nahe an der Uniform, wie ich es für meinen Zweck benötige (fairer Würfelwurf, Generierung kryptografisch starker Codebücher für Verschlüsselungsmaschinen des Zweiten Weltkriegs wie http://users.telenet.be/d.rijmenants/en/kl-7sim.htm usw. ). Der Ausgang zeigt keine nennenswerte Vorspannung.

Hier ist die Quelle des kryptografisch starken (wahren) Zufallszahlengenerators: Intel Digital Random Number Generator und ein Beispielcode, der 64-Bit-Zufallszahlen (ohne Vorzeichen) erzeugt.

int rdrand64_step(unsigned long long int *therand)
{
  unsigned long long int foo;
  int cf_error_status;

  asm("rdrand %%rax; \
        mov $1,%%edx; \
        cmovae %%rax,%%rdx; \
        mov %%edx,%1; \
        mov %%rax, %0;":"=r"(foo),"=r"(cf_error_status)::"%rax","%rdx");
        *therand = foo;
  return cf_error_status;
}

Ich habe es unter Mac OS X mit clang-6.0.1 (gerade) und mit gcc-4.8.3 mit dem Flag "-Wa, q" kompiliert (da GAS diese neuen Anweisungen nicht unterstützt).

Wie bereits erwähnt, reicht Modulo nicht aus, da es die Verteilung verzerrt. Hier ist mein Code, der Bits maskiert und verwendet, um sicherzustellen, dass die Verteilung nicht verzerrt ist.

static uint32_t randomInRange(uint32_t a,uint32_t b) {
    uint32_t v;
    uint32_t range;
    uint32_t upper;
    uint32_t lower;
    uint32_t mask;

    if(a == b) {
        return a;
    }

    if(a > b) {
        upper = a;
        lower = b;
    } else {
        upper = b;
        lower = a; 
    }

    range = upper - lower;

    mask = 0;
    //XXX calculate range with log and mask? nah, too lazy :).
    while(1) {
        if(mask >= range) {
            break;
        }
        mask = (mask << 1) | 1;
    }


    while(1) {
        v = rand() & mask;
        if(v <= range) {
            return lower + v;
        }
    }

}

Mit dem folgenden einfachen Code können Sie sich die Verteilung ansehen:

int main() {

    unsigned long long int i;


    unsigned int n = 10;
    unsigned int numbers[n];


    for (i = 0; i < n; i++) {
        numbers[i] = 0;
    }

    for (i = 0 ; i < 10000000 ; i++){
        uint32_t rand = random_in_range(0,n - 1);
        if(rand >= n){
            printf("bug: rand out of range %u\n",(unsigned int)rand);
            return 1;
        }
        numbers[rand] += 1;
    }

    for(i = 0; i < n; i++) {
        printf("%u: %u\n",i,numbers[i]);
    }

}

Gibt eine Gleitkommazahl im Bereich [0,1] zurück:

#define rand01() (((double)random())/((double)(RAND_MAX)))