What is the best way to create the best pseudo-random number generator? (any language works)
+17
A:
Best way to create one is to not to.
Pseudo-random number generators are a very complex subject, so it's better off to use the implementations produced by the people that have a good understanding of the subject.
coobird
2009-02-25 03:12:47
+3
A:
Yikes, that can get VEEEEEERY complicated! There seem to be a number of metrics for how to measure the "randomness" of a random number generator, so it's difficult to meaure which are "best". I would start with Numerical Recipes in C (or whatever langauge you can find one for) for a few examples. I coded up my first simple one from the examples given there.
EDIT: It's also important to start by determining how complex you need your random number generator to be. I remember a rude awakening I had in C years ago when I discovered that the default random number generator had a period somewhere around 32,767, meaning that it tended to repeat itself periodically after generating that many numbers! If you need a few dice rolls, that's fine. But not when you need to generate millions of "random" values for a simulation.
gnovice
2009-02-25 03:13:23
Numerical Recipes is a dangerous field, as they don't allow you to use the code unless you purchase a license for every user. That's a trap we ran into with a university simulation framework which created a major hassle. And for the C RNG the period is usually around 2^32, it only emits just 15 bits
Joey
2009-03-04 15:46:00
+6
A:
It all depends on the application. The generator that creates the "most random" numbers might not be the fastest or most memory-efficient one, for example.
The Mersenne Twister algorithm is a fairly fast pseudo-random number generator that produces quite good results. However it is not deemed good enough for cryptographic applications.
This is just one example; without more details about your specific application it is impossible to give a conclusive answer.
Thomas
2009-02-25 03:14:02
MT also has the advantage of drawing n-tuples evenly over n*[0-1)-space for large n. Something that not every PRNG can do. This is a reason for it being very popular in Monte Carlo studies across many fields.
dmckee
2009-02-25 03:25:01
"it is not deemed good enough for cryptographic applications": no, MT is *absolutely forbidden* for crypto, because a sequence of 624 output numbers from MT lets you predict its entire future output! Capturing the output sequence of a proper crypto RNG gives NO information on its future output.
kquinn
2009-02-25 04:16:17
"Capturing the output sequence of a proper crypto RNG gives NO information on its future output." Thats wrong, the information is there. The future output just needs to be infeasibly hard to compute.
starblue
2009-02-25 09:47:30
A:
Steal the one out of knuth seminumeric. It is high quality and simple to implement. It uses a pair of arrays, addition, and a couple of ifs. Cheap, effective, and a nice long period 2^55 if i recall correctly.
EvilTeach
2009-02-25 03:15:40
I vaguely remember something about a RNG from a famous book being pretty crappy, but widely used because it was in a famous book. I can't find anything about this anymore, though. It might well have been a different book. Be sure to check this before you use it for any critical purpose, though.
Thomas
2009-02-25 03:21:30
+4
A:
The German magazine C't tested a number of software and hardware generators in the 2/2009 issue and ran the results through various statistical tests.
I scanned the results here.
I would not bother writing my own. The article mentions that even Donald Knuth failed with his "Super-random number generator", which was not so random after all. Get one that passed all tests (had a result > 0 in all columns). They also tested a setup with a VIA EPIA M10000 mobo, which has a hardware RNG. I like this option for a commercial or semi-commercial setup that requires a robust random number server with high throughput.
Unless, of course, you are just playing around, in which case this may be good enough.
cdonner
2009-02-25 03:42:10
Hardware RNGs are a no-go if you specifically need a PRNG, i. e. something that has reproducible output, which is a very important trait for use in simulations.
Joey
2009-03-04 15:43:15
A:
See this link for the TestU01 suite of tests, which includes several batteries of tests.
http://www.iro.umontreal.ca/~simardr/testu01/tu01.html
In the paper, the author demonstrates the test result on a variety of existing RNGs, but not .NET System.Random (as far as I can tell). Though he does test VB6's generator.
Very few pass all the tests...
Jason B
2009-10-16 16:24:29
A:
If you're going to work in C++, Boost has a collection of PRNGs that I'd trust a lot more than whatever comes in standard libraries. The documentation might be helpful in picking one out. As always, how good a PRNG is depends on what you're using it for.
David Thornley
2009-10-16 16:31:26