Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

PCG, A Family of Better Random Number Generators

pcg-random.org

Post reply on HN
Print view View original

11–20 of 57 posts

Re: PCG, A Family of Better Random Number Generators

#11

Post by zaroth »

daurnimator wrote: post #6

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 (…

> I'm not sure why I want k-Dimensional Equidistribution

For the party tricks, of course! http://www.pcg-random.org/party-tricks.html

Re: PCG, A Family of Better Random Number Generators

#12

Post by nightcracker »

daurnimator wrote: post #10
nightcracker wrote: post #9

Earlier quoted context omitted.

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 This is also the implementation used for the benchmark at the pcg-random.org homepage.

How does it compare to the libsodium implementation: 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.

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.

Re: PCG, A Family of Better Random Number Generators

#13

Post by [deleted] »

daurnimator wrote: post #6

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 (…

[deleted]

Re: PCG, A Family of Better Random Number Generators

#14

Post by bradleyjg »

daurnimator wrote: post #6

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 (…

Just as you wouldn't want to use a general purpose PRNG for security applications so too you wouldn't want to use a secure PRNG for general purposes, particularly demanding applications such as Monte Carlo simulations.

Your dismissal strikes me as both ignorant and rude.

Re: PCG, A Family of Better Random Number Generators

#15

Post by JoachimS »

bradleyjg wrote: post #14
daurnimator wrote: post #6

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 (…

Just as you wouldn't want to use a general purpose PRNG for security applications so too you wouldn't want to use a secure PRNG for general purposes, particularly demanding applications such as Monte Carlo simulations. Your dismissal strikes me as both ignorant and rude.

What are the random number data rates for those applications?

One of the good features of ChaCha is that it is fast. A modern CPU can churn out Gbps of data. And in HW you can do it at low clock frequencies. This is the reason we use ChaCha as the CSPRNG in the Cryptech HSM.

Re: PCG, A Family of Better Random Number Generators

#16

Post by slavik81 »

daurnimator wrote: post #6

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 (…

What's your application? When I wrote a ray tracer that did photon mapping, I needed about 300 000 000 random numbers per light to get half-decent results. Admittedly, I could have done more to optimize my use of those numbers, but the point remains that you need huge numbers of random samples.

I used mt19937 for this and it worked ok. I suspect that using pcg might have shaved a few percentage points off the total run time of the program (maybe I should do a benchmark sometime). If so, not a huge win, but noticeable. Especially if you're doing renders on a larger scale than I was. A couple percentage points could trim a few computers from a render farm.

Re: PCG, A Family of Better Random Number Generators

#17

Post by dminor »

trebor wrote: post #2

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.

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

Re: PCG, A Family of Better Random Number Generators

#18

Post by daurnimator »

bradleyjg wrote: post #14
daurnimator wrote: post #6

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 (…

Just as you wouldn't want to use a general purpose PRNG for security applications so too you wouldn't want to use a secure PRNG for general purposes, particularly demanding applications such as Monte Carlo simulations. Your dismissal strikes me as both ignorant and rude.

> Just as you wouldn't want to use a general purpose PRNG for security applications so too you wouldn't want to use a secure PRNG for general purposes, particularly demanding applications such as Monte Carlo simulations.

Why not? It's perfectly valid to use a secure RNG for non-secure purposes.

As I mentioned, I've used ChaCha20 for those sort of purposes too. And the random number generation barely shows up as a fraction of the runtime.

i.e. improving 1% of the runtime by 99% isn't worth the overhead of having more than one random number generator.

Re: PCG, A Family of Better Random Number Generators

#20

Post by netheril96 »

nightcracker wrote: post #9
daurnimator wrote: post #6

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 (…

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 This is also the implementation used for the benchmark at the pcg-random.org homepage.

What is the stream parameter in the constructor `explicit ChaCha(uint64_t seedval, uint64_t stream = 0);`?
Post reply on HN