Erweitern Sie einen Zufallsbereich von 1-5 auf 1-7

Question

Geben Sie eine Funktion an, die eine zufällige ganze Zahl im Bereich von 1 bis 5 erzeugt. Schreiben Sie eine Funktion, die eine zufällige ganze Zahl im Bereich von 1 bis 7 erzeugt.

1. Was ist eine einfache Lösung?
2. Was ist eine effektive Lösung, um die Speichernutzung zu reduzieren oder mit einer langsameren CPU zu arbeiten?

Answer 1

int randbit( void )
{
    while( 1 )
    {
        int r = rand5();
        if( r <= 4 ) return(r & 1);
    }
}

int randint( int nbits )
{
    int result = 0;
    while( nbits-- )
    {
        result = (result<<1) | randbit();
    }
    return( result );
}

int rand7( void )
{
    while( 1 )
    {
        int r = randint( 3 ) + 1;
        if( r <= 7 ) return( r );
    }
}

Answer 2

rand7() = (rand5()+rand5()+rand5()+rand5()+rand5()+rand5()+rand5())%7+1

Edit: Das funktioniert nicht ganz. Die Abweichung beträgt etwa 2 Teile von 1000 (unter der Annahme eines perfekten rand5). Die Eimer bekommen:

value   Count  Error%
1       11158  -0.0035
2       11144  -0.0214
3       11144  -0.0214
4       11158  -0.0035
5       11172  +0.0144
6       11177  +0.0208
7       11172  +0.0144

Durch den Wechsel zu einer Summe von

n   Error%
10  +/- 1e-3,
12  +/- 1e-4,
14  +/- 1e-5,
16  +/- 1e-6,
...
28  +/- 3e-11

scheint um eine Größenordnung zuzunehmen für jede 2 hinzugefügte

Übrigens: Die obige Fehlertabelle wurde nicht durch Stichproben generiert, sondern durch die folgende Rekursionsbeziehung:

p[x,n] ist die Anzahl der Wege output=x kann passieren, wenn n Anrufe an rand5 .

  p[1,1] ... p[5,1] = 1
  p[6,1] ... p[7,1] = 0

  p[1,n] = p[7,n-1] + p[6,n-1] + p[5,n-1] + p[4,n-1] + p[3,n-1]
  p[2,n] = p[1,n-1] + p[7,n-1] + p[6,n-1] + p[5,n-1] + p[4,n-1]
  p[3,n] = p[2,n-1] + p[1,n-1] + p[7,n-1] + p[6,n-1] + p[5,n-1]
  p[4,n] = p[3,n-1] + p[2,n-1] + p[1,n-1] + p[7,n-1] + p[6,n-1]
  p[5,n] = p[4,n-1] + p[3,n-1] + p[2,n-1] + p[1,n-1] + p[7,n-1]
  p[6,n] = p[5,n-1] + p[4,n-1] + p[3,n-1] + p[2,n-1] + p[1,n-1]
  p[7,n] = p[6,n-1] + p[5,n-1] + p[4,n-1] + p[3,n-1] + p[2,n-1]

Answer 3

int ans = 0;
while (ans == 0) 
{
     for (int i=0; i<3; i++) 
     {
          while ((r = rand5()) == 3){};
          ans += (r < 3) >> i
     }
}

Answer 4

int rand7() {
    int value = rand5()
              + rand5() * 2
              + rand5() * 3
              + rand5() * 4
              + rand5() * 5
              + rand5() * 6;
    return value%7;
}

Anders als die gewählte Lösung läuft der Algorithmus in konstanter Zeit. Er macht jedoch 2 Aufrufe mehr an rand5 als die durchschnittliche Laufzeit der gewählten Lösung.

Beachten Sie, dass dieser Generator nicht perfekt ist (die Zahl 0 hat eine um 0,0064 % höhere Wahrscheinlichkeit als jede andere Zahl), aber für die meisten praktischen Zwecke wiegt die Garantie einer konstanten Zeit wahrscheinlich mehr als diese Ungenauigkeit.

Erläuterung

Diese Lösung ergibt sich aus der Tatsache, dass die Zahl 15.624 durch 7 teilbar ist. Wenn wir also zufällig und gleichmäßig Zahlen von 0 bis 15.624 erzeugen können und dann mod 7 nehmen, erhalten wir einen nahezu gleichmäßigen rand7-Generator. Zahlen von 0 bis 15.624 können einheitlich generiert werden, indem man rand5 6-mal würfelt und damit die Ziffern einer Basis-5-Zahl wie folgt bildet:

rand5 * 5^5 + rand5 * 5^4 + rand5 * 5^3 + rand5 * 5^2 + rand5 * 5 + rand5

Die Eigenschaften von mod 7 erlauben es uns jedoch, die Gleichung ein wenig zu vereinfachen:

5^5 = 3 mod 7
5^4 = 2 mod 7
5^3 = 6 mod 7
5^2 = 4 mod 7
5^1 = 5 mod 7

Also

rand5 * 5^5 + rand5 * 5^4 + rand5 * 5^3 + rand5 * 5^2 + rand5 * 5 + rand5

wird

rand5 * 3 + rand5 * 2 + rand5 * 6 + rand5 * 4 + rand5 * 5 + rand5

Theorie

Die Zahl 15.624 wurde nicht zufällig gewählt, sondern kann mit Hilfe des kleinen Satzes von Fermat ermittelt werden, der besagt, dass, wenn p eine Primzahl ist, dann

a^(p-1) = 1 mod p

Daraus ergibt sich also,

(5^6)-1 = 0 mod 7

(5^6)-1 ist gleich

4 * 5^5 + 4 * 5^4 + 4 * 5^3 + 4 * 5^2 + 4 * 5 + 4

Dies ist eine Zahl zur Basis 5, und wir können sehen, dass diese Methode verwendet werden kann, um von jedem Zufallszahlengenerator zu jedem anderen Zufallszahlengenerator zu gelangen. Allerdings wird bei der Verwendung des Exponenten p-1 immer eine kleine Verzerrung in Richtung 0 eingeführt.

Um diesen Ansatz zu verallgemeinern und um genauer zu sein, können wir eine Funktion wie die folgende verwenden:

def getRandomconverted(frm, to):
    s = 0
    for i in range(to):
        s += getRandomUniform(frm)*frm**i
    mx = 0
    for i in range(to):
        mx = (to-1)*frm**i 
    mx = int(mx/to)*to # maximum value till which we can take mod
    if s < mx:
        return s%to
    else:
        return getRandomconverted(frm, to)

Answer 5

Im Folgenden wird eine Gleichverteilung auf {1, 2, 3, 4, 5, 6, 7} mit Hilfe eines Zufallszahlengenerators erzeugt, der eine Gleichverteilung auf {1, 2, 3, 4, 5} erzeugt. Der Code ist chaotisch, aber die Logik ist klar.

public static int random_7(Random rg) {
    int returnValue = 0;
    while (returnValue == 0) {
        for (int i = 1; i <= 3; i++) {
            returnValue = (returnValue << 1) + SimulateFairCoin(rg);
        }
    }
    return returnValue;
}

private static int SimulateFairCoin(Random rg) {
    while (true) {
        int flipOne = random_5_mod_2(rg);
        int flipTwo = random_5_mod_2(rg);

        if (flipOne == 0 && flipTwo == 1) {
            return 0;
        }
        else if (flipOne == 1 && flipTwo == 0) {
            return 1;
        }
    }
}

private static int random_5_mod_2(Random rg) {
    return random_5(rg) % 2;
}

private static int random_5(Random rg) {
    return rg.Next(5) + 1;
}