|  support |  documentation |  report a bug |  advanced search |  search howto |  statistics |  random bug |  login
Bug #12530 Shuffle shouldn't use the least significant bit of rand()
Submitted: 2001-08-02 07:24 UTC Modified: 2002-07-03 19:07 UTC
From: sulka at sulake dot com Assigned:
Status: Closed Package: Arrays related
PHP Version: 4.0.6 OS: Solaris (most unices)
Private report: No CVE-ID: None
 [2001-08-02 07:24 UTC] sulka at sulake dot 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:

$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 
		// 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.


Add a Patch

Pull Requests

Add a Pull Request


AllCommentsChangesGit/SVN commitsRelated reports
 [2001-08-04 18:12 UTC]
 [2002-04-27 15:53 UTC]
this is a bug, not a feature request.
 [2002-07-03 19:07 UTC]
This bug has been fixed in CVS. You can grab a snapshot of the
CVS version at In case this was a documentation 
problem, the fix will show up soon at
In case this was a website problem, the change will show
up on the site and on the mirror sites.
Thank you for the report, and for helping us make PHP better.

PHP Copyright © 2001-2023 The PHP Group
All rights reserved.
Last updated: Sat Sep 30 10:01:24 2023 UTC