Bug #55519 [Asn]: mt_rand only generetes even 64 bits numbers

Edit report at https://bugs.php.net/bug.php?id=55519&edit=1 ID: 55519 Updated by: aharvey@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] aharvey@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