7
$\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.

Improve this question
$\endgroup$
4
  • $\begingroup$ Could you please spell out your acronyms? $\endgroup$
    – kjetil b halvorsen ♦
    Apr 1, 2018 at 13:34
  • $\begingroup$ Wouldn't it fit crypto.stackexchange.com better? $\endgroup$
    – Tim ♦
    Apr 1, 2018 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, 2018 at 15:56
  • 3
    $\begingroup$ @Tim this question is about non-cryptographical generators. Those cannot be used for cryptography. $\endgroup$
    – juhist
    Apr 1, 2018 at 16:04

2 Answers 2

Reset to default
8
$\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.

Improve this answer
$\endgroup$
3
  • $\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, 2018 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, 2018 at 9:40
  • 1
    $\begingroup$ @juhist That makes sense if 32 bits of randomness are enough for your needs (besides random booleans). $\endgroup$
    – Ralf Stubner
    Apr 2, 2018 at 21:59
2
$\begingroup$

PCG generators are more or less fine if you use them single-stream in a single application (albeit they will be very slow if you use a state larger than 64 bits). In all other situations, they should be avoided. You can find a very detailed discussion here: http://prng.di.unimi.it/pcg.php .

As for benchmarking: a PCG32 generator fits a single register due to the small state size (64 bits). xoroshiro128+ (or ++) uses more registers, and this takes time (they must be loaded and saved). In microbenchmarks this will not show up because the compiler keeps all the state in registers (which is why I always suggest to benchmark inside an application). Note, however, that a period of $2^{64}$ bits is really too short for any scientific application. You should have a period at least large as the square of the number of outputs you are using.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Could you please elaborate the "You should have a period at least large as the square of the number of outputs you are using."? $\endgroup$
    – gyuunyuu
    Mar 30, 2020 at 13:52
  • $\begingroup$ This is a standard consideration from the literature. For example, imagine you have a 64-bit generator using 64-bit values, and that the generator can emit all possible values. This means that as you emit values, you will see a duplicate only after $2^{64}$ outputs. But you should see duplicates roughly after $2^{32}$ steps (a little bit more, see the distribution for the Birthday Paradox). So if you use less than the square root of the period, you'll never see this statistical flaw. $\endgroup$
    – seba
    Mar 30, 2020 at 18:33
  • 2
    $\begingroup$ Detailed rebuttal from the PCG author: pcg-random.org/posts/on-vignas-pcg-critique.html $\endgroup$
    – Shai Coleman
    Oct 15, 2020 at 12:01

Your Answer

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

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