4
$\begingroup$

I have a demand for extremely fast acceptable-quality random number generator (RNG). This means rand()%2 should not alternate between 0 and 1 (that totally kills the simulation, as in one problem I indeed to rand()%2 every second time rand() is called). In my simulation, speed is absolutely the most important criterion apart from rand()%2 not alternating between 0 and 1. So, my requirements in the order of importance are:

  1. rand()%2 should have a high-quality output
  2. The speed should be extraordinarily high
  3. Statistical quality of the random number generator must be good (not that important)

I have found that permuted congruential generator (PCG) is faster than Mersenne Twister (MT), and Mersenne Twister is faster than e.g. minstd_rand. Both Mersenne Twister and PCG satisfy the rand()%2 requirement. The only generator I have found that is faster than MT and PCG is standard linear congruential generator (LCG) which has poor output for rand()%2.

For my application, I therefore believe that PCG is the best choice. But I'm starting to have some doubts about the statistical quality of PCG.

There is some marketing on the PCG website. However, PCG does not have any paper in a reputable scientific journal, the paper being just a preprint. Although it was stated that the reason for not accepting the paper was its length, this blog post says they missed some relevant literature.

However, Mersenne Twister has been published in a reputable journal.

So, my question is, can I believe the marketing on the PCG website? Is there a RNG that is a better choice when both performance and statistical quality are considered? Is there something in the literature that is better than PCG, which I believe might be the case due to the review comments of the PCG paper?

I'm planning to publish my results in a reputable scientific journal, so a RNG that has been published in a reputable scientific journal (so that I could cite it) would be appreciated, but not if the performance is much poorer than PCG.

$\endgroup$
  • $\begingroup$ Could you please spell out your acronyms? $\endgroup$ – kjetil b halvorsen Apr 1 '18 at 13:34
  • $\begingroup$ Wouldn't it fit crypto.stackexchange.com better? $\endgroup$ – Tim Apr 1 '18 at 15:11
  • $\begingroup$ There are lots of generators that are much faster than the Mersenne Twister that are also high-quality, surely high quality enough for your purposes, so don't feel those are your only two choices! $\endgroup$ – jbowman Apr 1 '18 at 15:56
  • $\begingroup$ @Tim this question is about non-cryptographical generators. Those cannot be used for cryptography. $\endgroup$ – juhist Apr 1 '18 at 16:04
3
$\begingroup$

Other people have looked at the statistical qualities of the PCG generators and found them to be good, see for example https://lemire.me/blog/2017/08/22/testing-non-cryptographic-random-number-generators-my-results/. On that page you will also find references to other RNGs, that are all faster than MT. If being published and raw speed are important for you, you could use one of the RNGs from http://xoroshiro.di.unimi.it/, but note that in the + or * versions the lowest two bits are of problematic quality and are the reason why these generators fail some tests. So you should not use rand() % 2 to get a random boolean. You could use a sign test instead. The ** versions should produce high quality output for all bits though.

$\endgroup$
  • $\begingroup$ Thanks! I tested xoroshiro128plus. In microbenchmarks, it is faster than PCG32 but for some strange reason, in the whole application test it makes the application run slightly (about 6%) slower than PCG32... Not sure why. Actually, now that I took a second look at std::uniform_int_distribution, it isn't using rand()%2 but division instead. An older version of my code used rand()%2. $\endgroup$ – juhist Apr 2 '18 at 9:33
  • $\begingroup$ Now when testing it again, I observed that 100 million 32-bit divisions take 0.29 s, whereas 100 million 64-bit divisions take 0.84 s. I could make a wrapper around xoroshiro128+ to make it return two 32-bit integers instead of one 64-bit integer... $\endgroup$ – juhist Apr 2 '18 at 9:40
  • $\begingroup$ @juhist That makes sense if 32 bits of randomness are enough for your needs (besides random booleans). $\endgroup$ – Ralf Stubner Apr 2 '18 at 21:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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