Web Hosting Talk : Web Hosting Main Forums : Programming Discussion : Random Number Generation

[GavinPearce]

I was bored last night and decided to teach myself something. I had always wondered how a logical machine like a computer can generate a truly random number, so I done a little research.

Just thought I'd share my findings on the off chance that I wasn't the only person in the world who was wondering!

In basic - there are two types of computer generated random numbers:


1st
You could set a device to monitor a random natural event - a common example tends to be to place a piece of radioactive material in front of a Geiger counter with Geiger counter connected to a computer.

Since radioactive decay is random, the Geiger counter could create truly random numbers.

This approach is pretty rare, for the obvious (I hope) reason that many people do not have Geiger counters connected to their lovely machines.

2nd
You can do the much more common approach - and generate an almost random number, as per the case with most computers.

In a simple terms a formula that generates what is known as a 'pseudo-random number' is created. The idea of the formula is for it to produce a string of numbers that would look random to anyone who did not know the formula itself.

An example of a simple random-number formula from the book "The C Programming Language," by Kernighan and Ritchie:

int rand() 
{
  random_seed = random_seed * 1103515245 +12345; 
  return (unsigned int)(random_seed / 65536) % 32768; 
}

This formula assumes the existence of a variable (start number) called random_seed, which is initially set to some number. The random_seed variable is multiplied by 1,103,515,245 and then 12,345 gets added to the product and some more lovely mathmatical dividing and adding up. You then get out your first almost random value. Next time the script is run random_seed is then replaced by this new value creating an even more random value.

However can you see the problem here? You need a default value to start the formula. All you've done so far is change a few numbers around. Nothing random about it. If you always used the same value at the start you would always return the same numbers in the same order. So you need a random number to start of the random number sequence?? This was the bit that always used to stump me.

The simple answer is.....

It's impossible to create a truly random number for this value (unless you use the first method listed above) - what most machines resort to is second best - they convert the current date and time into an integer (for example the number of seconds or even miliseconds since 1st Jan 1970) and use this as the magic starting value for the seed.

They then have an always changing number to start off the formula, and hence always generate a different set of values each time the forumla is run!


So there you have it, computers and almost random, random numbers.

[John[H4Y]]

Interesting huh? And if you seed a random number generator with a value based on the exact time, technically, it could be considered seeding with a random, unpredictable event. In the case that the computer pulling the time information connects to a time server, which pulls data from an atomic clock, the time may not ALWAYS be what you expect. Large earthquakes such as the one that caused the tsunami in Indonesia, and meteors can throw off the Earth's time. And as of yet, we have no 100% way of predicting these types of events.

[GavinPearce]

Indeedy.

I rather wish I could attach a device to my postmen, and the log the time he turns up. Then you'd get a truly random number! Grr....

[John[H4Y]]

Makes me wonder what the approved way for online casinos and poker rooms would be for generating random cards. Apparently, there is some industry standard they all use.

[dspillettt]

If you need some "true" random numbers, have a look at http://random.org/

I wouldn't use it for large numbers of random numbers (I'd consider that to be misuse, though the site seems to suggest they aren't too bothered about that sort of tihng) but I have considered using it in a app to generate a truely random seed for a good arithmetic psuedo-random generator.

[GavinPearce]

I'm not to sure random.org is actually that random.

It works off atmospheric noise received by a radio tuner on a frequency no one transmits to.

I don't believe atmospheric noise to actually be that random, it's again logical. It's made up of thousands of signals that are all created somewhere, you could predict the event if you studied in enough detail the noise itself and where it comes from. (A lot is from space - again however their are reasons why this happens). Indeed I agree it makes pseudo-random number, but not so sure about being truly random.

[bigfan]

I wouldn't look to casinos for examples of true randomness, or even near-randomness. Their machines are all programmed to give them a winning edge, the size of which varies among casinos and jurisdictions.

[null]

Here's how PokerStars generates random cards:

http://www.pokerstars.com/poker/room/features/security/

[Lightwave]

http://www.lavarand.org/

Landon is a cool guy... I've always liked how he put "A job with an unspecified branch of the US Federal Government, 1979-82" (cough NSA cough) on his resume :p

[John[H4Y]]

Originally Posted by GavinPearce

I'm not to sure random.org is actually that random.

It works off atmospheric noise received by a radio tuner on a frequency no one transmits to.

I don't believe atmospheric noise to actually be that random, it's again logical. It's made up of thousands of signals that are all created somewhere, you could predict the event if you studied in enough detail the noise itself and where it comes from. (A lot is from space - again however their are reasons why this happens). Indeed I agree it makes pseudo-random number, but not so sure about being truly random.

There is background noise and radio interference from the big bang, sunspots, solar flares, etc. That would be QUITE random or at least WAYYYY too complicated to predict for any mere human.

[GavinPearce]

But still perdictable. :d

[Premier]

Originally Posted by GavinPearce

Indeedy.

I rather wish I could attach a device to my postmen, and the log the time he turns up. Then you'd get a truly random number! Grr....

That would have worked for me too at the last place I was living.



When I need random numbers in a script, I start with a seed that is determined by some calculations done with time and visitors IP. That way I'm starting with 2 unrelated variables to create the starting point.

[folsom]

I have always liked the way that AOLServer does random seeds.

The cool part is that the entropy comes from starting a counter in a different thread then grabbing the value of and resetting the counter at somewhat random times while it is running.