Warum gibt mt_rand (1, PHP_INT_MAX) immer eine ungerade Zahl zurück?

Question

Ich bin gerade auf einen interesting question von ComputerGuru auf Hacker News gestoßen und kein Kommentar scheint eine überzeugende Antwort zu geben.

Warum gibt mt_rand(1, PHP_INT_MAX) immer eine ungerade Zahl zurück?

Ich bin nicht der Autor der ursprünglichen Frage.

http://3v4l.org/dMbat

for ($i=0;$i<10000;$i++) 
{ 
    echo mt_rand(1, PHP_INT_MAX)."\n"; 
} 

Ausgang:

8571620074060775425 
7401021871338029057 
4351677773593444353 
1801559362708176897 
7848614552286527489 
... 

Answer 1

PHP_INT_MAX hier ist 2 -1 (64-bit signed int max).

mt_rand() verarbeitet jedoch keine so großen Werte. Der Mersenne-Twister generiert intern 32-Bit-Wörter, und PHP mt_getrandmax() ist nur 2 -1 (es wirft das höchste Bit weg).

Um einen Wert in Ihrem Wunsch min-max Bereich, mt_rand zuerst bekommen die 0 bis 2 -1 Zufallszahl zu erzeugen, skaliert es dann mit dieser Formel:

x = ((x/(mt_getrandmax() + 1)) * (max - min + 1)) + min; 

(Siehe Quelle rand.c und php_rand.h.)

Grundsätzlich skaliert es blind die intern generierte Nummer, um den übergroßen Bereich zu passen, ohne sogar eine Warnung zu erhöhen. Die Multiplikation mit dem übergroßen Bereich erzeugt eine Menge von Nullen in den niedrigen Bits, und das Hinzufügen von min (was 1 ist) macht das Ergebnis ungerade.

Das Problem ist noch dramatischer in hexadezimal, wo Sie, dass die unteren 32 Bits jeder Zahl sind vollständig nicht zufällig sehen:

for ($i = 0; $i < 10000; $i++) { 
    printf("%016x\n", mt_rand(1, PHP_INT_MAX)); 
} 

Ausgang:

41e0449b00000001 
53d33d7c00000001 
6ec8855700000001 
234140e000000001 
13a4581900000001 
77547beb00000001 
35a0660a00000001 
0d0cd44200000001 
... 

Es gibt eine Notiz in the manual, die versucht, davor zu warnen, obwohl es das Problem untertreibt:

Die Verteilung der Rückgabewerte mt_rand() ist auf gerade Zahlen bei 64-Bit-Builds von PHP ausgerichtet, wenn max über 2 hinausgeht. Dies liegt daran, dass, wenn max größer als der von mt_getrandmax() zurückgegebene Wert ist, der Ausgang des Zufallszahlengenerators hochskaliert werden muss.

(Sie sagt, sie zu geraden Zahlen vorbelastet sind, aber das ist nur wahr, wenn min selbst ist.)