Random numbers in PHP

[ShadowMage]

Rather than hijack this post any further, I decided to ask my own question.From the above mentioned post:

That just shows how truly non-random it is. One limitation though, is on Windows the max random number is 32768. And you've generated exactly half that number of unique strings. That's not a coincidence.

JSG, can you explain this a little more, please? I'm not fully understanding the correlation between the max random number and the number of unique strings I was able to generate with rand(). Once I switched my function to use mt_rand() instead, I ran my function 120,000 times at 7 character string length and generated ~119k unique strings.

[justsomeguy]

This is the algorithm in question:

function randHexDec($len) {	$hex = '';	for ($i=0; $i<$len; $i++) {		$d=rand(1,16)%8;		$hex .= ($d<5) ? chr(rand(48,57)) : chr(rand(65,70));	}	return $hex;}

So, first you generate d, which is between 0 and 7 inclusive. Then you check if d is less than 5, which is true the majority of the time (62.5%, if each number shows up with the same frequency). If it's less than 5, then you have a strange way of generating a random number between 0 and 9, or else you generate a random A-F.Run this page a few times and change len between 3 and 4. With a length of 3 it should always generate all 4096 strings. When the length is 4, for 250k iterations, it should generate around 64,000 of the 65536 possibilities. See if you're still seeing it stick at or near 16384.

<?phpfunction randHexDec($len) {	$hex = '';	for ($i=0; $i<$len; $i++) {		$d=rand(1,16)%8;		$hex .= ($d<5) ? chr(rand(48,57)) : chr(rand(65,70));	}	return $hex;}$num = array();$i = 250000;$len = 4;$top = 50;for ($n = 0; $n < $i; $n++){  $val = randHexDec($len);  if (isset($num[$val]))	$num[$val]++;  else	$num[$val] = 1;}asort($num);$num = array_reverse($num);echo 'ran ' . $i . ' times<br>';echo 'len=' . $len . '<br>';echo 'generated ' . count($num) . ' strings<br>';echo 'top ' . $top . ':<hr>';$n = 0;foreach ($num as $k => $v){  echo $k . ' (' . $v . ')<br>';  if ((++$n) >= $top) break;}?>

It's interesting to play with that. Change the length to 1 and then see how truly non-random it is. I'm nearly always seeing the numbers come out in order, with the letters scattered among them. If you change it so that letters and numbers have an equal chance of showing up, all letters show up much more frequently than all numbers, and the numbers are virtually always in order:

$d = rand() % 2;$hex .= ($d) ? chr(rand(48,57)) : chr(rand(65,70));

ran 250000 timeslen=1generated 16 stringstop 50:A (21146)E (20889)C (20803)B (20798)D (20772)F (20639)0 (12670)1 (12631)2 (12542)3 (12539)4 (12526)5 (12519)6 (12438)7 (12388)8 (12368)9 (12332)

I understand why each letter is more frequent, because there are only 6, but I don't know why the numbers show up in order. Putting the characters in an array and using array_rand has a more even distribution of letters and numbers, but the numbers still show up in order:

$c = array('0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F');$num = array();for ($n = 0; $n < $i; $n++){  $val = $c[array_rand($c)];  if (isset($num[$val]))	$num[$val]++;  else	$num[$val] = 1;}asort($num);$num = array_reverse($num);echo 'ran ' . $i . ' times<br>';echo 'len=' . $len . '<br>';echo 'generated ' . count($num) . ' strings<br>';echo 'top ' . $top . ':<hr>';$n = 0;foreach ($num as $k => $v){  echo $k . ' (' . $v . ')<br>';  if ((++$n) >= $top) break;}

ran 250000 timeslen=1generated 16 stringstop 50:D (15828)0 (15793)1 (15753)2 (15735)3 (15721)4 (15696)5 (15692)A (15669)E (15666)6 (15658)7 (15583)F (15553)8 (15546)9 (15405)B (15362)C (15340)

[ShadowMage]

...you have a strange way of generating a random number between 0 and 9...

Yeah, I fixed that. It now reads rand(0,9) instead of chr(rand(48,57))

Run this page a few times and change len between 3 and 4. With a length of 3 it should always generate all 4096 strings. When the length is 4, for 250k iterations, it should generate around 64,000 of the 65536 possibilities. See if you're still seeing it stick at or near 16384.

With a len of 3 it consistently generates almost all 4096 strings (anywhere from about 4090 to 4096), but at length of 4 this is what I get:

ran 250000 timeslen=4generated 3962 stringstop 50:B5D8 (123)736A (123)1DF3 (123)4C62 (123)1B7D (123)0804 (123)0 (123)0330 (123)1 (123)B232 (123)623E (123)6AD7 (123)...

I'm assuming that the lines 0 (123) and 1 (123) are actually the strings '0000' and '0001' respectively...Anyway, as you can see, it did not come anywhere near generating 64k strings. It didn't even hit 4k! :)I ran this roughly a dozen times and not once did it reach 4k strings.And at len=7 it still returns 16384 every single time.If I change the function to use mt_rand() then I get ~64k strings when len=4 and ~249k when len=7

...I don't know why the numbers show up in order.

That is interesting....

[justsomeguy]

I believe rand uses the libc function of the same name, so it's going to be platform-dependent. The server I'm running this on is 64-bit Windows Web Server 2008 R2, so the 64-bit implementation might have different characteristics than a 32-bit implementation.

[ShadowMage]

I believe rand uses the libc function of the same name, so it's going to be platform-dependent. The server I'm running this on is 64-bit Windows Web Server 2008 R2, so the 64-bit implementation might have different characteristics than a 32-bit implementation.

Ah yes, that old 32-bit/64-bit pitfall. That's gotten me on a number of occasions...I'm running this on (don't laugh ) a Windows 2000 server (obviously 32-bit, since I don't think 64 was available then)So I guess the moral of this story is use mt_rand instead of rand... (and nothing is truly random )

[Fmdpa]

How did early pioneer programmers create random number pickers? Any idea I can come up with comes back down to using a random number function. Math is very systematic, not random. How could they use math to pick a random number?

[boen_robot]

Clocks in computers have always been a variable that changes every milisecond... pretty much all algoritms start off with that as a base, and then use fancy math to make it so that output numbers appear chaotic within a certain small time range.

[jeffman]

EDIT: as boen wrote . . .Most computers for a long time have had some sort of internal clock. Some clocks maintain state and track the real time. Other clocks keep track of some number of "ticks" since the computer started, or since the current process started, etc. That gives you the basis for some sort of pseudo-randomness, since time always changes. Run the time through an algorithm that can spit out very different outputs from similar inputs and you have yourself a decent generator. You could build one in JavaScript just using the Date object, and an even better one in PHP using microtime. Run the time through something like MD5, reanalyze all the resulting characters into digits, and you'll have a pretty random number.As you've noted, though, there is a limit to this, since there is always an amount of regularity to the system. Some RN generators have biases that may need to be offset (like generating a disproportionate number of "1"s), but it's doable if you're willing to analyze your results for a while.Pseudo-random is good enough for most applications. Only a few things require true randomness, like a really good quantum decay simulator, for example, or if you need a really, really good simulator for Vegas-type games. A lot of so-called "systems" for beating the house turn out not to work because the RNGs used to test them were less than random.

[Fmdpa]

Ah, I had never thought of using timestamp values. Very interesting!