8 ms·

PCG, A Family of Better Random Number Generators

88 points by aburan28 11y ago

trebor 11y ago
I'm impressed by how fast this algorithm is. I wrote a toy implementation in Go, and it was only ~50ns/op to generate random numbers. And it's very even in distribution, but I'd have to rerun my tests to find the percentage again.
- dminor 11y ago
  Same here - first thing I wrote in go, just to play with the language: https://github.com/davidminor/gorand https://github.com/davidminor/gorand
mturmon 11y ago
Seems perfectly reasonable and worth knowing about. Thanks for submitting.
jey 11y ago
Sounds awesome, if it lives up to its claims. Have the domain experts weighed in on this yet?
- carterehsmith 11y ago
  The latest word is, "This paper is currently submitted to ACM Transactions on Mathematical Software, where it is currently under review. "
ufo 11y ago
There is a seminar about PCG from its author available on youtube. https://www.youtube.com/watch?v=45Oet5qjlms https://www.youtube.com/watch?v=45Oet5qjlms Its a bit long but I highly recommend it. I learned a lot about RNGs from it.
- vtsrh 11y ago
  Speaker mentions[0] that it is possible to get a different statistically random value every time you run the program, without any input to the program, apparently by using some tricks, but she refuses to elaborate for the camera. Can anyone explain how that works? Has this something to do with address space randomization? [0]:https://youtu.be/45Oet5qjlms?t=1h3m3s https://youtu.be/45Oet5qjlms?t=1h3m3s
  - echaozh 11y ago
    > (This last one relies on the operating system placing myRNG at a different address every time the program is run. It's not as strong as the other techniques.) from: http://www.pcg-random.org/useful-features.html#id2 http://www.pcg-random.org/useful-features.html#id2
    - justincormack 11y ago
      Linux gives each process a 32 bit random seed, which is probably more useful (as is making a syscall). On an embedded system the address seed may well be useless anyway.
  - pdw 11y ago
    Probably not what she meant, but Linux has a RNG that extracts randomness from CPU execution time jitter: https://lwn.net/Articles/642166/ https://lwn.net/Articles/642166/
- chinpokomon 11y ago
  So good. I'm only about 20 minutes into it, but it addresses so many of the questions and ideas I've had about RNG.
- jacobolus 11y ago
  Great talk! The video is also linked from the site, under 'Video' in the banner: http://www.pcg-random.org/posts/stanford-colloquium-talk.html http://www.pcg-random.org/posts/stanford-colloquium-talk.htm... For those who didn’t bother poking around and are interested in random number generation and C++, the blog also great: http://www.pcg-random.org/blog/ http://www.pcg-random.org/blog/
daurnimator 11y ago
Unless it's secure, I see no motivation to use it. In their table, they acknowledge that Arc4Random and ChaCha20 as secure. The only negatives against ChaCha20 is that it's not 'fast enough' and k-Dimensional Equidistribution. In my experience it's never showed up in my profiling, so I feel it's fast enough; and I'm not sure why I want k-Dimensional Equidistribution. So... I'll keeping using ChaCha20 when I need to (it's part of nacl/libsodium if you don't know where to get it from).
- nightcracker 11y ago
  I wrote a standalone C++11 (compatible with the standard RNG library) implementation of ChaCha (with the number of rounds as a parameter), available here: https://gist.github.com/orlp/32f5d1b631ab092608b1 https://gist.github.com/orlp/32f5d1b631ab092608b1 This is also the implementation used for the benchmark at the pcg-random.org homepage.
  - daurnimator 11y ago
    How does it compare to the libsodium implementation: https://github.com/jedisct1/libsodium/blob/master/src/libsodium/crypto_stream/chacha20/ref/stream_chacha20_ref.c https://github.com/jedisct1/libsodium/blob/master/src/libsod... Btw, libsodium prefers salsa20 instead of chacha20, I don't know why; but I trust they made a good decision.
    - nightcracker 11y ago
      It's essentially the same, except for the API. However, you linked to the reference implementation. My implementation also contains a SIMD implementation, if your CPU supports it. I assume that libsodium has a similar implementation in its codebase somewhere too. My SIMD implementation can be made to run a bit faster, but this would mean computing more blocks in parallel, and thus increase the state size of the RNG even more. I chose to only compute one block at a time. An optimized stream cipher implementation will have all the implementations with different parellel block sizes embedded, to achieve optimal speed for long messages. --- ChaCha20 is a stronger more modern variation on Salsa20. But the differences are minor. But, to be precise, libsodium prefers XSalsa20 to ChaCha20. The core feature about XSalsa20 is that it supports a 192-bit nonce instead of the 64-bit nonce of ChaCha20. This means that it is safe to use a randomly generated nonce, while randomly generating a 64-bit nonce would result in collisions eventually. I believe this is the reason they chose XSalsa20. XSalsa20 is a simple variation on Salsa20 that does a bit more initialization to turn the normal 64-bit nonce into 192-bit. I assume the same construction can be applied to ChaCha20, but since djb (the author of both Salsa, XSalsa and ChaCha) hasn't done it, I think that libsodium went with the safe approach and just used XSalsa20.
panax 11y ago
This is fine for quickly generating random numbers for simulations, just don't use it for cryptographic applications. If you want random numbers for crypto use a CSPRNG.
- danieltillett 11y ago
  For non-crypto applications it is really good. Very fast and simple.
dchest 11y ago
Experimental Go implementation by Rob Pike, as a replacement for math/rand: https://go-review.googlesource.com/#/c/10161/ https://go-review.googlesource.com/#/c/10161/
danieltillett 11y ago
Wow talk about a coincidence - I just implemented this algorithm today as the RNG for some bootstrapped statistic code. One thing I can say is it very fast, but the code for seeding is not great on any platform without /dev/random.
- LoSboccacc 11y ago
  I implemented the mersenne twister to generate 2d planets in a galaxy of a game I am working on a while ago.. I didn't know about this pcg and it's an interesting read! I had been limited in selection on the random number generator reproducibility (so that each planet is only stored as the seed for the generator) I'll have a try later on, it'd be interesting how a sampling of planets turn out from both rngs, if they are visually different - the rng is used both for features and for the perlin noise that generates cloud&land textures, so any artifact should come up easy in the textures
  - danieltillett 11y ago
    Give it a try - I just used the minimum C code function and implemented my own seeding function.
joseraul 11y ago
Looks like a very good and fast PRNG. How could it possibly achieve higher statistical quality than a secure PRNG? I guess that depends on how you define quality.
- explorigin 11y ago
  It does not claim to be security quality.
vtsrh 11y ago
This is great, but everything so far is overly positive. Can we get some negative criticism as well. Anyone qualified?
- yoklov 11y ago
  I'm not really qualified to speak as to its statistical properties, but I've used this generator a couple times. The biggest downside I ran into is that it requires 64 bit numbers even for the 32 bit RNG, which means its very simple code becomes more complex on a platform with only 32 bit numbers, or in a scripting language. Also, it's not a CSPRNG, if this matters to you. This is minor though, and I would use it again. It's flexibility for seeding and easy serialization outweigh this IMO (and it's still simple compared to e.g. mtrand)
- dhekir 11y ago
  I must have done something wrong, but I tried the basic C implementation (https://github.com/imneme/pcg-c-basic https://github.com/imneme/pcg-c-basic) on a quick Diehard-like test and it failed. I'm still trying to understand why. Probably not its fault, just that the code is not as forgiving and ready-to-consume as I had expected.
  - vtsrh 11y ago
    It passed for me. Where did you get the diehard test? If you compiled it directly from http://www.stat.fsu.edu/pub/diehard/ http://www.stat.fsu.edu/pub/diehard/ then it is because that source is broken.
    - panax 11y ago
      Try using Dieharder. It incorporates most of the Diehard tests, as well as other tests and is much more rigorous. sudo apt-get install dieharder http://www.phy.duke.edu/~rgb/General/dieharder.php http://www.phy.duke.edu/~rgb/General/dieharder.php If you make a GSL interface for the RNG it will make using dieharder much easier
      - deleted 11y ago
kabouseng 11y ago
Shouldn't the title read: ....better psuedo-random ...
Amiga64 11y ago
Interesting. I don't think people realize just how slow rand() can be if it is called frequently in your c/c++ program. Marsaglia's xorshf is the fastest algorithm that I know of that also give a ok statistical quality.

88 points by aburan28 11y ago

I'm impressed by how fast this algorithm is. I wrote a toy implementation in Go, and it was only ~50ns/op to generate random numbers. And it's very even in distribution, but I'd have to rerun my tests to find the percentage again.

dminor 11y ago
Same here - first thing I wrote in go, just to play with the language: https://github.com/davidminor/gorand https://github.com/davidminor/gorand

mturmon 11y ago

Seems perfectly reasonable and worth knowing about. Thanks for submitting.

jey 11y ago

Sounds awesome, if it lives up to its claims. Have the domain experts weighed in on this yet?

carterehsmith 11y ago
The latest word is, "This paper is currently submitted to ACM Transactions on Mathematical Software, where it is currently under review. "

ufo 11y ago

There is a seminar about PCG from its author available on youtube. https://www.youtube.com/watch?v=45Oet5qjlms https://www.youtube.com/watch?v=45Oet5qjlms Its a bit long but I highly recommend it. I learned a lot about RNGs from it.

vtsrh 11y ago
Speaker mentions[0] that it is possible to get a different statistically random value every time you run the program, without any input to the program, apparently by using some tricks, but she refuses to elaborate for the camera. Can anyone explain how that works? Has this something to do with address space randomization? [0]:https://youtu.be/45Oet5qjlms?t=1h3m3s https://youtu.be/45Oet5qjlms?t=1h3m3s
- echaozh 11y ago
  > (This last one relies on the operating system placing myRNG at a different address every time the program is run. It's not as strong as the other techniques.) from: http://www.pcg-random.org/useful-features.html#id2 http://www.pcg-random.org/useful-features.html#id2
  - justincormack 11y ago
    Linux gives each process a 32 bit random seed, which is probably more useful (as is making a syscall). On an embedded system the address seed may well be useless anyway.
- pdw 11y ago
  Probably not what she meant, but Linux has a RNG that extracts randomness from CPU execution time jitter: https://lwn.net/Articles/642166/ https://lwn.net/Articles/642166/
chinpokomon 11y ago
So good. I'm only about 20 minutes into it, but it addresses so many of the questions and ideas I've had about RNG.
jacobolus 11y ago
Great talk! The video is also linked from the site, under 'Video' in the banner: http://www.pcg-random.org/posts/stanford-colloquium-talk.html http://www.pcg-random.org/posts/stanford-colloquium-talk.htm... For those who didn’t bother poking around and are interested in random number generation and C++, the blog also great: http://www.pcg-random.org/blog/ http://www.pcg-random.org/blog/

daurnimator 11y ago

Unless it's secure, I see no motivation to use it. In their table, they acknowledge that Arc4Random and ChaCha20 as secure. The only negatives against ChaCha20 is that it's not 'fast enough' and k-Dimensional Equidistribution. In my experience it's never showed up in my profiling, so I feel it's fast enough; and I'm not sure why I want k-Dimensional Equidistribution. So... I'll keeping using ChaCha20 when I need to (it's part of nacl/libsodium if you don't know where to get it from).

nightcracker 11y ago
I wrote a standalone C++11 (compatible with the standard RNG library) implementation of ChaCha (with the number of rounds as a parameter), available here: https://gist.github.com/orlp/32f5d1b631ab092608b1 https://gist.github.com/orlp/32f5d1b631ab092608b1 This is also the implementation used for the benchmark at the pcg-random.org homepage.
- daurnimator 11y ago
  How does it compare to the libsodium implementation: https://github.com/jedisct1/libsodium/blob/master/src/libsodium/crypto_stream/chacha20/ref/stream_chacha20_ref.c https://github.com/jedisct1/libsodium/blob/master/src/libsod... Btw, libsodium prefers salsa20 instead of chacha20, I don't know why; but I trust they made a good decision.
  - nightcracker 11y ago
    It's essentially the same, except for the API. However, you linked to the reference implementation. My implementation also contains a SIMD implementation, if your CPU supports it. I assume that libsodium has a similar implementation in its codebase somewhere too. My SIMD implementation can be made to run a bit faster, but this would mean computing more blocks in parallel, and thus increase the state size of the RNG even more. I chose to only compute one block at a time. An optimized stream cipher implementation will have all the implementations with different parellel block sizes embedded, to achieve optimal speed for long messages. --- ChaCha20 is a stronger more modern variation on Salsa20. But the differences are minor. But, to be precise, libsodium prefers XSalsa20 to ChaCha20. The core feature about XSalsa20 is that it supports a 192-bit nonce instead of the 64-bit nonce of ChaCha20. This means that it is safe to use a randomly generated nonce, while randomly generating a 64-bit nonce would result in collisions eventually. I believe this is the reason they chose XSalsa20. XSalsa20 is a simple variation on Salsa20 that does a bit more initialization to turn the normal 64-bit nonce into 192-bit. I assume the same construction can be applied to ChaCha20, but since djb (the author of both Salsa, XSalsa and ChaCha) hasn't done it, I think that libsodium went with the safe approach and just used XSalsa20.

panax 11y ago

This is fine for quickly generating random numbers for simulations, just don't use it for cryptographic applications. If you want random numbers for crypto use a CSPRNG.

danieltillett 11y ago
For non-crypto applications it is really good. Very fast and simple.

dchest 11y ago

Experimental Go implementation by Rob Pike, as a replacement for math/rand: https://go-review.googlesource.com/#/c/10161/ https://go-review.googlesource.com/#/c/10161/

danieltillett 11y ago

Wow talk about a coincidence - I just implemented this algorithm today as the RNG for some bootstrapped statistic code. One thing I can say is it very fast, but the code for seeding is not great on any platform without /dev/random.

LoSboccacc 11y ago
I implemented the mersenne twister to generate 2d planets in a galaxy of a game I am working on a while ago.. I didn't know about this pcg and it's an interesting read! I had been limited in selection on the random number generator reproducibility (so that each planet is only stored as the seed for the generator) I'll have a try later on, it'd be interesting how a sampling of planets turn out from both rngs, if they are visually different - the rng is used both for features and for the perlin noise that generates cloud&land textures, so any artifact should come up easy in the textures
- danieltillett 11y ago
  Give it a try - I just used the minimum C code function and implemented my own seeding function.

joseraul 11y ago

Looks like a very good and fast PRNG. How could it possibly achieve higher statistical quality than a secure PRNG? I guess that depends on how you define quality.

explorigin 11y ago
It does not claim to be security quality.

vtsrh 11y ago

This is great, but everything so far is overly positive. Can we get some negative criticism as well. Anyone qualified?

yoklov 11y ago
I'm not really qualified to speak as to its statistical properties, but I've used this generator a couple times. The biggest downside I ran into is that it requires 64 bit numbers even for the 32 bit RNG, which means its very simple code becomes more complex on a platform with only 32 bit numbers, or in a scripting language. Also, it's not a CSPRNG, if this matters to you. This is minor though, and I would use it again. It's flexibility for seeding and easy serialization outweigh this IMO (and it's still simple compared to e.g. mtrand)
dhekir 11y ago
I must have done something wrong, but I tried the basic C implementation (https://github.com/imneme/pcg-c-basic https://github.com/imneme/pcg-c-basic) on a quick Diehard-like test and it failed. I'm still trying to understand why. Probably not its fault, just that the code is not as forgiving and ready-to-consume as I had expected.
- vtsrh 11y ago
  It passed for me. Where did you get the diehard test? If you compiled it directly from http://www.stat.fsu.edu/pub/diehard/ http://www.stat.fsu.edu/pub/diehard/ then it is because that source is broken.
  - panax 11y ago
    Try using Dieharder. It incorporates most of the Diehard tests, as well as other tests and is much more rigorous. sudo apt-get install dieharder http://www.phy.duke.edu/~rgb/General/dieharder.php http://www.phy.duke.edu/~rgb/General/dieharder.php If you make a GSL interface for the RNG it will make using dieharder much easier
    - deleted 11y ago

kabouseng 11y ago

Shouldn't the title read: ....better psuedo-random ...

Amiga64 11y ago

Interesting. I don't think people realize just how slow rand() can be if it is called frequently in your c/c++ program. Marsaglia's xorshf is the fastest algorithm that I know of that also give a ok statistical quality.