Bug #12530 Updated: Shuffle shouldn't use the least significant bit of rand()

ID: 12530 Updated by: eru@php.net Reported By: sulka@sulake.com -Status: Open +Status: Closed Bug Type: Arrays related Operating System: Solaris (most unices) PHP Version: 4.0.6 New Comment: This bug has been fixed in CVS. You can grab a snapshot of the CVS version at http://snaps.php.net/. In case this was a documentation problem, the fix will show up soon at http://www.php.net/manual/. In case this was a PHP.net website problem, the change will show up on the PHP.net site and on the mirror sites. Thank you for the report, and for helping us make PHP better. Previous Comments: ------------------------------------------------------------------------ [2002-04-27 15:53:53] jimw@php.net this is a bug, not a feature request. ------------------------------------------------------------------------ [2001-08-04 18:12:31] andy@php.net reclassified ------------------------------------------------------------------------ [2001-08-02 07:24:41] sulka@sulake.com In ext/standard/array.c, the sorting algorithm of shuffle is defined as (php_rand() % 2) ? 1 : -1 This is fine for rand algorithms in which all bits are random but with Solaris and other unices this is not so. Quoting man random(): "The difference is that rand(3C) produces a much less random sequence-in fact, the low dozen bits generated by rand go through a cyclic pattern. All the bits generated by random() are usable." This is not true however - the LSB of random() calls are predictable on some systems. You can verify if your system is affected by running this: <?PHP $a = array(); $b = array(); for($i=0; $i<1000; $i++) // iterate 1000 times { $foo = ""; // initialize random seq with new seed srand ($i); // create a string with the LSB of first 24 random numbers for($j=0; $j<24; $j++) { $c = rand(); // $c = rand(0,32000); works on all systems // store the random number so we can check how many different // numbers were really generated $b[$c]= 1; // append the least signicant bit to the string $foo .= ($c % 2); } // store the parity string $a[$foo]= 1; } echo "Parity string count: " . count($a), "<BR>"; echo "Random number count: " . count($b), "<BR>"; ?> If the counts are 1000/24000 you're fine. Affected systems I've tried this on return 4/24000. Proposed fix: change shuffle to call PHP's own rand function with limits, ie, rand(0,32000). This introduces randomness into the LSB and fixes shuffle. ------------------------------------------------------------------------ -- Edit this bug report at http://bugs.php.net/?id=12530&edit=1