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

ID: 12530 Updated by: andy Reported By: sulka@sulake.com Status: Open Old Bug Type: Arrays related Bug Type: Feature/Change Request Operating System: Solaris (most unices) PHP Version: 4.0.6 New Comment: reclassified Previous Comments: ------------------------------------------------------------------------ [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