GOOD random number generator??

pointsplat

This is driving me nuts!! I have been searching all over for a random number algorithm written for PHP but haven't found anything sufficient. The best I found is
Code:
(double)microtime()*1000000

which seems to be common ground but thats not good enough . In a database of only 30 entries right now it returns the same results within only a couple clicks and even back to back sometimes.

I am writing a HotorNot style script so this is one of the most essential parts, people will get bored if they see the same stuff over and over again. Does anyone know of a more complex algorithm then the one listed above?

Thanks in advance, Grant.[/code]😕

laserlight

I dont think there are any random number generators in PHP.

You could use a pseudo-random number generator though, one would be srand() for the seed then rand().
I would use mt_srand() for the seed and mt_rand()

For example:

<?php
mt_srand((double)microtime() * 1000000);
$num = mt_rand(0, 30);
?>

though you may not need to seed the pseudo-random number generator on newer versions of PHP.

pointsplat

Yea thats what ive been using I was wondering if there are any more comples seeds then the double microtime... I am not completely clear on how seeds work even though the php documentation is pretty good on it its not geting through 🙂 I don't know if its just me but it seemed even when we used just a time() seed in C++ I would get more random values then PHP is returning. Maybe its just me.

Anyway thank you for the extremely quick response and I suppose I shall just hope the database grows a bit so the script become naturally more random 😃

If anyone has time and can follow up and explain the seeding process (what exactly its doing) to me that I could at least understand that it would be cool.

Thanks again,
Grant

bad76

Hi,
a random number generator is usually a linear function like this:

function Rrand()
{ $m = 65521; // this number are all prime and co-prime
   $b = 15937;  // it's a good math property for a good rnd
   $c = 33503;

   $seed = ($seed * $b + $c) mod $m;
   return $seed / $m  // a number between 0 and 1
}

As you see the $seed is a global and its initialization influence the result.

Weedpacket

You don't need a complex seed, just a sufficiently unpredictable one; microtime is generally unpredictable enough (especially the microsecond part); but it's best to use the rest of the microtime as well, as using only the microsecond part limits you to a space of only a million possible sequences out of the full four billion. It's worse still if the platform you're running on doesn't have a microsecond-resolution clock.

Basically all the seed is is the number that the generator starts from (if you give it the same seed on two different occasions, the sequences generated are identical; if the seeds are different, different sequences is generated). When you ask for a number from the generator, it takes te seed, cranks it through the algorithm, and gives you the number that drops out the other end. It also holds on to that number as the seed for the next time it needs a number.

Actually, the Mersenne Twister is a bit more complex than that; the number you initially give it as the seed is first mangled a few hundred times and the results stored in an array. Successive calls to the generator sees it grinding through updating the elements of the array (which acts as a kind of memory of the last few hundred numbers generated) while it works out which number to return. But before it does return it, it "tempers" it a bit more; shifting, xoring, and doing a few other bitwise operations with a few extra magic numbers.

That said of course, it's certainly possible (and it has been done) to write a script that will connect to a genuinely random source of bits that may be available and use that.

pointsplat

That brings up a good question, I know im C++ class we had talked about generating the seed only once. I didn't pay much attention at this point I just wanted to get through the class and I had the see generator in the function so it was getting called each time.

Could this be the reason I am not getting a random value? Should I set it up so
mt_srand(make_seed()) is called only once?

Such as take the result from the last mt_rand(1,$highnum) and make it the seed once its been called before.

An example of this since im horrible at explaining:

User loads page
Seed generator is called (miroctime()*....)
Rand is called and returns a value
That value is placed in a cookie
User loads app again and app checks for cookie, if exists take value of cookie and make it the new seed

Would this have any effect as with a hot or not script people only take as long as it does for the pic to load before they click....while this is not millionths of a second it can definately be half a second or so further cutting down the randomness.

laserlight

"That said of course, it's certainly possible (and it has been done) to write a script that will connect to a genuinely random source of bits that may be available and use that."
hmm... where is that script?
I would write one myself, if I could get my hands on a nice little source of radio-isotopes that give me counts fast enough 😃

Well, I think you should try to seed only once.
http://www.php.net/manual/en/function.mt-rand.php
Though as I mentioned, "since 4.2.0 this (seeding the pseudo-random number generator) is no longer necessary."

martyn

personally i use a name or email address as the seed 😉

Weedpacket

Originally posted by laserlight
I would write one myself, if I could get my hands on a nice little source of radio-isotopes that give me counts fast enough 😃

The archetypal source I first heard of is HotBits (though the generation rate's only 30bps - is that good enough for a seed?)

A past EE acquaintance of mine mentioned to me once how for a small project she'd constructed an entropy-generating card; from what I recall it involved inserting a particular diode backwards - against the current. Said diode would fail and allow current through on a genuinely random basis. (Where "genuinely random" of course means the same as in the case of radioisotopes: quantum-mechanically uncertain).

BeastRider

Originally posted by pointsplat
In a database of only 30 entries right now it returns the same results within only a couple clicks and even back to back sometimes.

Thanks in advance, Grant.[/code]😕

In reality, a true random number generator can (and should) be able to return the same number 50 times in a row... or more... randomness doesn't have to do with the values that get generated, it is with how they are generated.

The seeded random number generators are OK for some things, but I think they fail miserably if one tries to use them for such things as modelling quantum events or various noise filters.

You can add a larger element of randomness to your algorithm by taking more numbers (or translations of numbers) over which you have no influence. For example, how many users are active? What is the wind speed in 3 different cities. Current CPU utilization percentage? If you find sources of numbers that have zero correlation with one another, and are not generated as the result of an algorithm, then the should provide you with a highly random number set... whch may or may not produce back to back duplicates.

But, it seems like that for what you are trying to do, you can use a seeded random number generator with a cooked up seed as others have noted. Then, if dupes really bug you, keep a "most recently utilized" list to eliminate dupes that occur within a certain distance of the original.

Weedpacket

I'm kind of wondering if the generated sequence is actually as "nonrandom" as it might be appearing: with a range of [1..30] one should expect back-to-back duplicates about three percent of the time. Assuming that the seed is unpredictable enough, mt_rand(1,30) should be perfectly adequate for the given purpose (I wouldn't really trust rand() - for one thing it's platform/compiler-dependent and I know some compilers out there have crappy PRNGs).

What is the seed PHP uses if one is not specified:

$mtime=microtime();
$mtime=explode(' ', $mtime);
$mtime = $mtime[0]+$mtime[1];

If your system has a /dev/urandom device or analogous, there's nothing stopping one from getting entropy from that ... depending on how it operates one might feel justified in using it as the random source itself, instead of just a source for the seed.

BeastRider

If you are thinking about creating any kind of card game, a 32 bit seed is not enough to shuffle a deck of cards.

See

http://www.paradisepoker.com/rng.html

for a non technical explanation.

laserlight

well, the total number of permutations of cards in a deck of 52 cards is
52! = 8.07E67 (3 s.f.)

2²²⁶ = 1.08E68 (3 s.f.)

That would probably mean a 226 bit random seed would be (barely) enough for shuffling a deck of 52 cards, though mileage may vary since card games involve more than shuffling the deck.

"The archetypal source I first heard of is HotBits"
yeah, I use that sometimes, though sometimes it is unavailable due to too much demand for the stored random values.

BeastRider, it is true that a true random number generator can generate the same number many times in a row, but statistically that should not be maintained.
This is even more important in a pseudo-random number generator, since the numbers produced must appear random, especially to statistical tests.

BeastRider

Originally posted by laserlight
BeastRider, it is true that a true random number generator can generate the same number many times in a row, but statistically that should not be maintained.
This is even more important in a pseudo-random number generator, since the numbers produced must appear random, especially to statistical tests.

Agreed... I just thought I'd toss that out because the original complaint of "duplicate" random numbers reminded me of the experiences of a college professor who taught introductory statistics. One of his first assignments was to have his students flip a coin one hundred times and record the results. He always knew who actually did the experiment and those who simply made up the results.

How? In the real experiment, it was not unusual to get 8, 10, or even 15 runs of all heads or all tails. But, the made up results never showed such runs... just like the original poster here, it didn't seem "right" that you could randomly get a dozen heads in a row.

I had my first run in with psuedo random number generators while trying to build adaptive noise filters. Just 'twernt good enough... had to go find some real random noise.

Weedpacket

There are also beasties called "quasirandom" number sequences; these tend to look "more random" to people, because they seek to avoid "clumps" of values - if 42 has already come up a couple of times already, a QRNG would suppress the chances of 42 being picked the next time.

I've got code lying around here; I might port it when I get the time...(yeah, right.)

BeastRider

Originally posted by Weedpacket
There are also beasties called "quasirandom" number sequences; these tend to look "more random" to people, because they seek to avoid "clumps" of values

And that leads naturally to the "Law of Maturation of Chance", that belief that if a coin has come up six times in a row as heads, that somehow the probability of the next flip being tails is somehow higher than it would be if there were only one preceding head.

A bunch of those silly lotto number pickers are based upon this theory as are some double up betting schemes.

Uh huh!