eine zufällige int gegeben eine zufällige Bit-Funktion erzeugen

Question

Sie eine int randBit() Funktion gegeben sind Angenommen, die zurückkommt, gleichmäßig verteilt, 0 oder 1.

schreiben randNumber (int max) Funktion.

Dies ist meine Implementierung, aber ich kann nicht beweisen/widerlegen, dass es richtig ist.

// max number of bits 
    int i = (int)Math.floor(Math.log(max)/Math.log(2)) + 1; 

    int ret = randBit(); 
    while (i-- > 0) { 
     ret = ret << 1 | randBit(); 
    } 

    return ret; 

Die grundlegende Idee, die ich hatte, ist, dass

• vorhanden, um die Anzahl der Bits finden in der Anzahl
• dann erzeugen die Anzahl von kontinuierlich die verketten LSB bis der Bitlänge ist
erfüllt

Answer 1

Der Ansatz, einen int mit zufälligen Bits zu füllen, ist meines Erachtens der richtige Weg. Da jedoch nur Ihr Algorithmus funktioniert, wenn maximale Leistung von 2 ist und ausgeschaltet ist durch eine in der Schleife, würde ich diese Änderung vorschlagen:

// max number of bits 
int i = (int)Math.floor(Math.log(max)/Math.log(2)) + 1; 

int rnd = 0; 
int mask = 1; 

while (i-- > 0) { 
    rnd = rnd << 1 | randBit(); 
    mask <<= 1; // or: mask *= 2 
} 
double q = (double)rnd/mask; // range is [0, 1) 
return (int)((max + 1) * q); 

Werfen wir einen Blick auf diese:

i wird immer gleich der Anzahl der Bits sein, die max belegt. Wenn die Schleife beendet ist, enthält rnd diese Anzahl von Bits, die zufällig mit 0 oder 1 gefüllt sind, und mask-1 enthält diese Anzahl von Bits, die mit 1s gefüllt sind. Man kann also davon ausgehen, dass der Quotient von rnd und mask-1 gleichmäßig zwischen 0 und 1 verteilt ist. Dies multipliziert mit max würde Ergebnisse im Bereich zwischen 0 und max, ebenfalls gleichverteilt, in Bezug auf Floating/Real-Werte ergeben.

Jetzt muss dieses Ergebnis auf ganze Zahlen abgebildet werden, und natürlich möchten Sie auch, dass sie gleichmäßig verteilt sind. Der einzige Haken hier ist die 1. Wenn der Quotient von rnd und mask-1 genau 1 ist, würde es einen Kantenfall geben, der Probleme bei der Skalierung auf den gewünschten Ergebnisbereich verursachen würde: Es wären 0 .. max-1 Werte gleichmäßig verteilt, aber max wäre eine seltene Ausnahme.

Um auf diese Bedingung zu achten, muss der Quotient so aufgebaut sein, dass er von 0 bis 1 reicht, aber mit 1 exclusiv. Dies wird erreicht durch rnd/mask. Dieser Bereich kann leicht auf gleichmäßig gespreizte Ganzzahlen 0 .. max abgebildet werden, indem mit max+1 multipliziert und an int.