Edit report at https://bugs.php.net/bug.php?id=55519&edit=1
ID: 55519
Updated by: ahar...@php.net
Reported by: sergio dot bobillier at gmail dot com
Summary: mt_rand only generetes even 64 bits numbers
Status: Assigned
Type: Bug
Package: Math related
Operating System: Linux (Ubuntu 11.04 x64)
PHP Version: Irrelevant
Assigned To: aharvey
Block user comment: N
Private report: N
New Comment:
OK, so this behaves normally for bounds up to 2^32, then does weird things
after that. Given this script:
<?php
$iterations = 1000;
function mt_check($lower, $upper) {
global $iterations;
$stats = array_reduce(array_map(function ($v) use ($lower, $upper) {
return mt_rand($lower, $upper);
}, range(1, $iterations)), function ($acc, $v) {
$v % 2 ? $acc['odd']++ : $acc['even']++;
return $acc;
}, array('odd' => 0, 'even' => 0));
echo "Stats for $iterations iterations of $lower..$upper: $stats[odd] odd;
$stats[even] even\n";
}
foreach (range(2, 62) as $pow) {
mt_check(pow(2, $pow - 1), pow(2, $pow));
}
?>
The results are this:
Stats for 1000 iterations of 2..4: 319 odd; 681 even
Stats for 1000 iterations of 4..8: 414 odd; 586 even
Stats for 1000 iterations of 8..16: 452 odd; 548 even
Stats for 1000 iterations of 16..32: 443 odd; 557 even
Stats for 1000 iterations of 32..64: 475 odd; 525 even
Stats for 1000 iterations of 64..128: 492 odd; 508 even
Stats for 1000 iterations of 128..256: 486 odd; 514 even
Stats for 1000 iterations of 256..512: 482 odd; 518 even
Stats for 1000 iterations of 512..1024: 505 odd; 495 even
Stats for 1000 iterations of 1024..2048: 502 odd; 498 even
Stats for 1000 iterations of 2048..4096: 480 odd; 520 even
Stats for 1000 iterations of 4096..8192: 485 odd; 515 even
Stats for 1000 iterations of 8192..16384: 501 odd; 499 even
Stats for 1000 iterations of 16384..32768: 513 odd; 487 even
Stats for 1000 iterations of 32768..65536: 508 odd; 492 even
Stats for 1000 iterations of 65536..131072: 498 odd; 502 even
Stats for 1000 iterations of 131072..262144: 510 odd; 490 even
Stats for 1000 iterations of 262144..524288: 514 odd; 486 even
Stats for 1000 iterations of 524288..1048576: 498 odd; 502 even
Stats for 1000 iterations of 1048576..2097152: 496 odd; 504 even
Stats for 1000 iterations of 2097152..4194304: 488 odd; 512 even
Stats for 1000 iterations of 4194304..8388608: 497 odd; 503 even
Stats for 1000 iterations of 8388608..16777216: 493 odd; 507 even
Stats for 1000 iterations of 16777216..33554432: 498 odd; 502 even
Stats for 1000 iterations of 33554432..67108864: 458 odd; 542 even
Stats for 1000 iterations of 67108864..134217728: 500 odd; 500 even
Stats for 1000 iterations of 134217728..268435456: 499 odd; 501 even
Stats for 1000 iterations of 268435456..536870912: 480 odd; 520 even
Stats for 1000 iterations of 536870912..1073741824: 512 odd; 488 even
Stats for 1000 iterations of 1073741824..2147483648: 487 odd; 513 even
Stats for 1000 iterations of 2147483648..4294967296: 492 odd; 508 even
Stats for 1000 iterations of 4294967296..8589934592: 0 odd; 1000 even
Stats for 1000 iterations of 8589934592..17179869184: 0 odd; 1000 even
Stats for 1000 iterations of 17179869184..34359738368: 0 odd; 1000 even
Stats for 1000 iterations of 34359738368..68719476736: 0 odd; 1000 even
Stats for 1000 iterations of 68719476736..137438953472: 0 odd; 1000 even
Stats for 1000 iterations of 137438953472..274877906944: 0 odd; 1000 even
Stats for 1000 iterations of 274877906944..549755813888: 0 odd; 1000 even
Stats for 1000 iterations of 549755813888..1099511627776: 0 odd; 1000 even
Stats for 1000 iterations of 1099511627776..2199023255552: 0 odd; 1000 even
Stats for 1000 iterations of 2199023255552..4398046511104: 0 odd; 1000 even
Stats for 1000 iterations of 4398046511104..8796093022208: 0 odd; 1000 even
Stats for 1000 iterations of 8796093022208..17592186044416: 0 odd; 1000 even
Stats for 1000 iterations of 17592186044416..35184372088832: 0 odd; 1000 even
Stats for 1000 iterations of 35184372088832..70368744177664: 4 odd; 996 even
Stats for 1000 iterations of 70368744177664..140737488355328: 4 odd; 996 even
Stats for 1000 iterations of 140737488355328..281474976710656: 5 odd; 995 even
Stats for 1000 iterations of 281474976710656..562949953421312: 20 odd; 980 even
Stats for 1000 iterations of 562949953421312..1125899906842624: 34 odd; 966 even
Stats for 1000 iterations of 1125899906842624..2251799813685248: 66 odd; 934
even
Stats for 1000 iterations of 2251799813685248..4503599627370496: 141 odd; 859
even
Stats for 1000 iterations of 4503599627370496..9007199254740992: 272 odd; 728
even
Stats for 1000 iterations of 9007199254740992..18014398509481984: 0 odd; 1000
even
Stats for 1000 iterations of 18014398509481984..36028797018963968: 0 odd; 1000
even
Stats for 1000 iterations of 36028797018963968..72057594037927936: 0 odd; 1000
even
Stats for 1000 iterations of 72057594037927936..144115188075855872: 0 odd; 1000
even
Stats for 1000 iterations of 144115188075855872..288230376151711744: 0 odd;
1000 even
Stats for 1000 iterations of 288230376151711744..576460752303423488: 0 odd;
1000 even
Stats for 1000 iterations of 576460752303423488..1152921504606846976: 0 odd;
1000 even
Stats for 1000 iterations of 1152921504606846976..2305843009213693952: 0 odd;
1000 even
Stats for 1000 iterations of 2305843009213693952..4611686018427387904: 0 odd;
1000 even
As any good engineer who's baffled would say: hmmm, that's interesting.
Previous Comments:
------------------------------------------------------------------------
[2011-08-28 03:40:06] ahar...@php.net
Verified on 64-bit OS X, at least beyond a certain set of mt_rand() bounds. Not
entirely sure what those actual bounds are yet.
------------------------------------------------------------------------
[2011-08-27 09:09:30] sergio dot bobillier at gmail dot com
Description:
------------
I was doing a lame RSA implementation when I discovered that mt_rand only
generates even numbers when the number is a 64 bits integer.
The Test script shows the script I used to generate two 64 bits integers p and
q with mt_rand. I was doing primality test only with odd numbers since even
numbers are not prime but the script never do the primality test because all
the generated numbers are even.
I thought this might be an integer overflow problem but I'm doing this on a 64
bits system and the var_dump function shows that the variables are actually
integers like so:
int(2117698586505379840)
int(1690740540401778688)
int(3279295862706012160)
int(4526730875131396096)
int(3188107862534520832)
int(1914802535743356928)
int(4172596828035874816)
int(4559249790717657088)
int(1938449129751445504)
int(1859647742213619712)
Test script:
---------------
function is_prime($num)
{
// See if the number is prime
echo "Primality test";
return true;
}
function gen_keys()
{
// 1. find two 64 bits primes p and q
$p = 0;
$q = 0;
while(!$p)
{
$p = mt_rand(72057594037927936, 4611686018427387904);
// debugging:
var_dump($p);
if($p % 2 == 0)
{
$p = 0;
}
else
{
// Primality test in another function
// (not important here)
echo "odd";
if(!is_prime($p))
$p = 0;
}
}
echo $p;
}
Expected result:
----------------
I expect the mt_rand to generate some odd numbers and make the script go
through the primality test or at least print "odd"
Actual result:
--------------
The script doesn't reach the primality or print "odd" test because all
generated numbers are even.
------------------------------------------------------------------------
--
Edit this bug report at https://bugs.php.net/bug.php?id=55519&edit=1
