19
$\begingroup$

A recent answer mentioned the use of Fortuna or Mersenne Twister Random Number Generators (RNGs) to seed a Monte Carlo simulation. I hadn't heard of Fortuna before so I looked it up - looks like it is mainly intended for cryptographic use.

I currently use a Mersenne Twister in production code to seed a K-Means algorithm.

Which (Fortuna or Mersenne Twister) is considered the best for "algorithmic seeding" applications (eg. seeding Monte Carlo and K-Means)? Or is it a "toss up" - i.e. use the most convenient.

From where I am sitting, "best" should provide the highest quality random numbers, operate quickly, and (possibly) have a low memory footprint. Of these, quality is probably the most important for most of us.

Improve this question
$\endgroup$
5
  • 6
    $\begingroup$ Cryptographic PRNGs tend to be way slower than most other PRNGs; if you're doing a Monte Carlo simulation where your PRNG operations number in the millions, you'll find cryptographic methods to be terribly expensive. $\endgroup$
    – J. M.
    Dec 2, 2011 at 1:46
  • 1
    $\begingroup$ @J. M. - With a little more detail, I think your comment would be good as an answer. It would certainly be interesting to look at whether modern hardware accelerated crypto functionality could be used to create a high performance stream of cryptographically secure pseudo random numbers. $\endgroup$
    – Mark Booth
    Dec 2, 2011 at 11:26
  • $\begingroup$ @JM good point about cryptographic RNGs being slow - mark against Fortuna $\endgroup$
    – winwaed
    Dec 3, 2011 at 3:38
  • $\begingroup$ heres a good list of PRNG's and many different stats that you may find useful hope it helps > boost.org/doc/libs/1_48_0/doc/html/boost_random/… $\endgroup$
    – pyCthon
    Dec 11, 2011 at 9:18
  • $\begingroup$ My problem with cstdlib was the granularity - only RAND_MAX=32768 possible values. I'm currently using MT for Monte Carlo raytracing sim. However, I don't see MT as a performance bottleneck in my profiler, probably because I'm do "random" generation of things like ray directions as a preprocess. For example, I might generate an array of 100,000 rays at startup, store them in an array, and randomly select array start position at runtime (running for 10,000 rays or so of the collection). This has a relatively high memory overhead, in exchange for good random number distributions. $\endgroup$
    – bobobobo
    Feb 13, 2012 at 21:10

4 Answers 4

Reset to default
14
$\begingroup$

Well, everything is a trade-off of some sort or another. For random number generators, I group them into 3 basic categories:

  1. Good enough for homework.
  2. Good enough to bet your company on.
  3. Good enough to bet your country on.

Linear congruential PRNGs (the method generally implemented in most libraries) are solidly in category 1. Both Fortuna and Mersenne Twister are solidly in category 2.

For an interesting article on how messing up a shuffling algorithm can cost you your company/casino, I recommend this one from 1999. Due to link rot, the images are gone, but figure 4, the one where you plot next number out of the PRNG against the previous number generated, is a set of parallel lines.

As J.M. points out, Fortuna is slow. As you've pointed out, Mersenne Twister is reasonably fast.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ Quickly skimming through the article's printable version, "figure 4" seems to be code instead of a picture. "Figure 5" looks kaput, but this is the image I got from the WayBack Machine. $\endgroup$
    – J. M.
    Dec 2, 2011 at 8:19
  • $\begingroup$ Thanks. looks like speed is a mark against Fortuna in this case. Re. Bad shuffles: yes I know enough (not much!) that it is easy to "undo" the randomness of an RNG - for example, by choosing a bad starting seed. $\endgroup$
    – winwaed
    Dec 3, 2011 at 3:40
  • $\begingroup$ Another version with better pictures is at: cigital.com/papers/download/developer_gambling.php $\endgroup$
    – Tangurena
    Nov 8, 2012 at 21:58
  • 1
    $\begingroup$ 96-bit LCGs with 32 bit outputs pass more statistical tests than Mersenne Twisters. Nobody should be using a Mersenne Twister nowadays, given it's so easy to make decent non-cryptographic PRNGs that are far better than the MT in every meaningful regard. $\endgroup$
    – Veedrac
    Apr 16, 2017 at 17:11
4
$\begingroup$

The default choice in the "cryptographic" category is Blum-Blum-Shub, I think. As the wikipedia page says already, this is not suitable for simulations because it's just too darn slow.

If you are running on a unix-like system, then you could also consider getting your random numbers directly from /dev/urandom, the operating system service that provides good (though not necessarily crypto) quality random numbers. Depending on the particular OS you are using, this may use the Yarrow algorithm - of which Fortuna is a variant. But the most interesting aspect is that the operating system has access to some true random numbers: thermal noise from internal temperature sensors, for example. Typically, this data is mixed into the random pool whenever it becomes available to keep the data unpredictable.

This concept of mixing in randomness suggests that it might be possible to get the best of both worlds as follows. Use a faster, reasonably good quality random number generator such as Mersenne as your basic RNG. Maintain a second, better quality random number generator as well - e.g. Fortuna. Every so many numbers, say 25, run one iteration of the better RNG and add the result into the state of your basic RNG. This way you would get fairly high performance and fairly high quality results. (I would guess it would be useless for crypto, because the strength of this composite generator might well be the strength of the weakest link. But for simulations, where you typically do not have a malicious adversary, it might work.)

Improve this answer
$\endgroup$
2
  • $\begingroup$ /dev/urandom is secure to use for cryptography on linux and free-bsd. Look at this answer $\endgroup$
    – Adam Kurkiewicz
    Aug 24, 2015 at 13:39
  • $\begingroup$ For simulations, why would it be a desirable features for random numbers to be true? Sure, some pseudo-random number generators are worse, but others will be en par for all practical purposes. So, why do you consider trueness as a good feature per se? $\endgroup$
    – Wrzlprmft
    Jun 16, 2017 at 12:09
2
$\begingroup$

I wanted to chime in to say that, I've recently gone through this process with a simulation and I should note that using Fortuna is not out of the question if it is really necessary. In our case, we were concerned that MT's entropy wasn't high enough which would translate in our simulation to a bias. So for our simulation we used Fortuna pulling about 65 billion random numbers from that algo. Point being, computers are fast, if you really need to you can use it if you have a reason. If you are just doing something like a monte carlo integration, stick with MT.

Improve this answer
$\endgroup$
0
$\begingroup$

I think the answer very much depends on the application you're intending for the RNG to be used for. I'd suggest a forth category for Tangurena's rough classification: "Good with no real gain".

For many applications, it may simply not matter, and a properly cryptographic-grade RNG may simply slow down your tasks without any commensurate gain in validity. For example, much of the research I do just requires many, many millions of numbers coming roughly from a distribution I specify. Almost any RNG will do, so all I need is one that's not so catastrophically poor as to be worthless as an RNG. Anything else is simply slowing down the work unnecessarily. I tend to use Mersenne Twister, but that's simply because it works well enough, I have the code, and it's reasonably fast.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.