[ View Thread ] [ Post Response ] [ Return to Index ] [ Read Prev Msg ] [ Read Next Msg ]

BGonline.org Forums

RANDOM NUMBER GENERATION

Posted By: Timothy Chow
Date: Monday, 21 June 2010, at 11:46 p.m.

In Response To: RANDOM NUMBER GENERATION (Ray Kershaw)

There is no "best" method of generating pseudorandom numbers because it depends, at minimum, on what tradeoff you want between "how random" the digits are and how quickly you want to generate them.

The gold standard as far as the quality of the random digits goes is that the generated digits should pass all polynomial-time statistical tests for randomness. This means passing not only all the standard statistical tests but also all the statistical tests that nobody has explicitly written down yet, but that could conceivably be written down in the future and executed in a feasible amount of time. This is the strongest possible standard for randomness; however, in order to prove that your random number generator meets this standard, you would at least have to prove the famous "P != NP" conjecture, which is the most famous open problem in theoretical computer science and for which there is a $1 million prize waiting for you if you can solve it. On the other hand, people have written down some random number generators which might meet this standard. For example, the Blum-Blum-Shub generator meets the gold standard under the assumption that factoring large integers is hard. These kinds of random number generators are known as cryptographic, because they are based on the same principles that cryptographic systems are (if you can detect a pattern in the digits then you will be able to break some of the strongest cryptographic systems available today).

Cryptographic random number generators, however, run slowly. There are many other random number generators that run much faster. Someone mentioned the Mersenne Twister. For most normal purposes the Mersenne Twister is fine. It passes most ordinary statistical tests. However, as explained on Wikipedia, if you observe enough digits and you know that they are being generated by the Mersenne Twister, then you can predict all future digits, so the digits don't pass all statistical tests for randomness.

Messages In This Thread

 

Post Response
Your Name:
Your E-Mail Address:
Subject:
Message:

If necessary, enter your password below:

Password:
 

 

[ View Thread ] [ Post Response ] [ Return to Index ] [ Read Prev Msg ] [ Read Next Msg ]

BGonline.org Forums is maintained by Stick with WebBBS 5.12.