Hacker News Reader

Comment by nightcracker | Hacker News Reader

Some would say Monte Carlo methods, but I'd disagree. If the results are reliant on your RNG method I would not settle for less than crypto strength (and methods like ChaCha20 can generate random data at 4GB+ per core per second on a modern CPU).

There is a time and place for non-CS rngs, and it is in randomized methods whos correctness/results does not rely on the RNG.

View on HN

This surprises me. With Monte Carlo methods, wouldn't you rather want quasi-random numbers[0], because they allow the simulation to converge asymptotically faster? Those are certainly not anything like crypto-strength.

[0]: https://en.wikipedia.org/wiki/Low-discrepancy_sequence

This is my understanding as well. In a classic MC problem, global illumination with path tracing, low discrepancy-based sampling converges about twice as fast as random numbers. The Cycles renderer in Blender doesn't even give you the option to use random numbers, just a choice of low discrepancy sequnces [1].

[1] "Pattern" section here: http://builder.openhmd.net/blender-hmd-viewport-temp/render/...

The suggested constants for additive recurrence in that wiki article have given me grief in the past. It is surprisingly simple to do extremely well with better choice of constants:

http://extremelearning.com.au/unreasonable-effectiveness-of-... (yes, no HTTPS, but incredibly illustrative)

Discussed in 2018: https://news.ycombinator.com/item?id=17873284

You're going to validate your results anyways, aren't you? Non-cryptographic random number generators are not guaranteed to introduce bias, a given implementation of a monte carlo simulation might introduce bias via a bug or a poorly chosen modeling. If you need to validate for bias anyways, so you might as well verify by checking against a cryptographic random number generator as well as whatever bias tests you may have at your disposal and then switch over for the speed.

A good non-cryptographic random number generator like xoshiro256 can generate at 4 times the speed of a chacha20 random number generator. Depending on how many models you need to compute and the desired precision of those models and how many random samples you need per model, this can easily be the difference between hours and days, or days and weeks.

> If the results are reliant on your RNG method I would not settle for less than crypto strength

Whenever a post on PRNGs comes up, I'm reminded of this post from a while back about Chrome:

https://medium.com/@betable/tifu-by-using-math-random-f1c308...

Near the end is a Monte Carlo estimate of Pi using 10^10 iterations:

  Chrome  3.1418697000 0.0002770464 1301.903s
  Firefox 3.1416998084 0.0001071548  249.595s
  Safari  3.1416692728 0.0000766192 7172.207s

The first observation is that the error was significantly higher for Chrome. The second is that Safari, which apparently did use a CSPRNG, was an order of magnitude slower. If you let Firefox run that long, I imagine that it would have performed many more iterations, resulting in much lower error.

>methods like ChaCha20 can generate random data at 4GB+ per core per second on a modern CPU

That's around 30x slower than a decent version of PCG, which also has a lot of variants to cover a lot of use cases.

> methods like ChaCha20 can generate random data at 4GB+ per core per second on a modern CPU

For MC path tracing (graphics) this is at least an order of magnitude too slow.

Can you expand on this? I’d like to read more. Do you mean you’d like 40GB/core/second, or something else?

Well I mean you might need quite a number of random numbers per second, in this case 32bit floats was what we used.

Even fairly trivial scenes can require over 20 random floats per sample and more complex scenes over 100. And you want to actually use those random numbers for calculating reflections, intersections etc. In the renderer I worked on the PRNG typically took at most 10% of total CPU time.

So assuming the above those 4GB/s would translate into less than 5k samples/sec, which would be considered quite slow.

Just to refresh my memory I just ran a quick test with a fairly simple scene. There's 6 samples for the camera, at least 3 per path vertex up (depth 32) and another 2 per light (8 in this scene). There might be some more I'm forgetting but lets use that a lower bound. For this scene then that means 6 + 3 * 32 + 2 * 8 = 118 random numbers per sample. On a single core I got 14.04kS/s, so that works out to at least 1.6M random numbers per second.

And this renderer was focusing more on physics and fidelity rather than speed. For animations and similar you'd need a renderer that's at least an order of magnitude faster than the one I worked on.

For reading further you could try PBRT[1]. It's a great book but not free. Luckily enough though the free chapter is about sampling and reconstruction so you can get a feel from that what is needed.

[1]: https://pbrt.org/

This is a great answer and very helpful, thank you.

It is you that is off by several orders of magnitude. 4GB/sec is 10^9 random floats per sec, and using your 118 random numbers per sample that'd be 8.5 million samples/sec. In other words, it's not the RNG that's your bottleneck at all.

Well that was certainly embarrassing. On the other hand I overlooked that in my test scene it samples the lights at every vertex, and I forgot it had textures which needs at least 2 coordinates per vertex. So it needs at least 10 * 32 * 2 = 960 random values for that.

I also recall that we tried MT but found a quite noticeable impact on speed compared to what we had, and on the PGC performance page MT is listed in the tens of GB/s. Perhaps our implementation was considerably worse though, I can't recall us testing it alone like that.

As I mentioned though, that renderer was more about physics and fidelity. Typical render times for even a preview would be a minute, for final single-frame stills tens of hours to several days on a single computer was common.

For animations you don't have that kind of time, so you need a orders of magnitude more samples/sec.

Yes and no. How do you ensure you don't hit a bad stream? I don't think there is any guarantee. For a very long stream, crypto is going to be good. For a not so long one, I am not so sure

Reply on news.ycombinator.com