Tuesday, October 10

Random Number Generator

A computer can not create random number, because everything is under control--except the Blue Screen of Death.

So, the "random number" in the computer actually is "pseudo random number". It is generated following some function. If you know the function and some other conditions, you can actually predict what will be the next "random" number. A simple function is:
xn+1 = (xn)2 Mod M
where M is a large number. For example, if we know M equals to 1,000,000, and the last number generated is 8372, we can calculate and know the next "random" number will be 90384, and the one next to it will be 267456. Pretty simple, isn't it?

Another question is: Each time you get "8372", the next number must be 90384. We can know the whole sequence of random number. If this random number generator is applied in a game, you can predict computer's next step when the last step is familiar. The game is not fun at all?!

So the number M must be changed every time. The next number after "8372" will be something else. We give an initial "seed", and the sequence will be different, if the initial seed is different.

The standard method to initialize a random number generator is C language is:
srand ( time(NULL) );
when the time() function creates a long number which is the colapsed seconds from midnight of Jan, 1, 1970. This number increases every second, so you can never get the same random number sequence.

Some new programmers forget to initial seed before using rand() function, and the function creates the same sequence of numbers. That is funny. XJ takes advantage of this feature, use the same seed to create the same sequence of random numbers, so that he can trace his code again and again during debuging.

One parameter to justify if a function is a good random number generator is the distribution of generated numbers. The created number should be randomized enough. If you are creating numbers between 1 and 1000, then the chance that one number is between 100 and 200 should be the same as the chance that is is between 500 and 600.

One online gambling website publiced its source code to convince its players that the game was fair, there was no trick in this website. Three yeas ago an MIT PHD student found a bug in the random number generator. After he got several cards, he could guess what the "seed" was, then the next "random" number and the next card would not be a secret to him. The more cards he got, the more accurate his guess would be. He could have won big money using his knowledge. Instead, he published his research :D That is how a real researcher works.

So if an intruder knows the algorithm, the seed, and historic number, he can easily calculate the whole sequence of the number and predict the next one. That's why it is always a "pseudo random number". It's hard to hide the algorithm, because sometimes an intruder can get your source code. The intruder can be an insider, or the programmer who creates this software. So make sure you hide the seed perfectly. Some algorithms can create random numbers in good distribution, but people can guess the seed from historic numbers. This kind of algorithms can't be used in security area then.



At October 11, 2006 3:40 PM, Anonymous xlsyu said...

I intentionally create the same random sequence over and over again to make sure I get the same "random" sample so that my results will be the same. You don't want to revise your table again and again whenever you rerun the program. This is also a good practice to generate reproducible analysis.

To generate a good sample, there is a simple but excellent algorithm called KISS--a double random generator.

At October 11, 2006 4:08 PM, Blogger Ben said...

I've never though of using the random numbers in this way. That's creative. Using the same seed can guarantee to get the same sequence of number.

How can I find this "KISS" generator? This name is so normal, and I got millions of pages from Google.

At October 11, 2006 4:20 PM, Anonymous xlsyu said...

google George Marsaglia and KISS random number generator

At October 11, 2006 9:33 PM, Anonymous Anonymous said...

--a computer can not create random numberS.
--the random number in the(A) computer actually is (A) pseudo random number.
--it is generated (BY) following some function. (not it following, so you should add 'by')
--we can know the whole sequence of random numberS.
--Jan. 1st, 1970
--historic numberS

At January 24, 2007 9:48 PM, Anonymous Anonymous said...

wow gold


Links to this post:

Create a Link

<< Home