3 ms·
See [1] [2] and there is a great treatment of the topic in this book [3]. I don't know exactly what's he doing, but if I was doing some kind of monte carlo int
by PaulHoule 2y ago
See [1] [2] and there is a great treatment of the topic in this book [3]. I don't know exactly what's he doing, but if I was doing some kind of monte carlo integration (like the family of energy surfaces in 6-dimensional space that I plotted the volume of as a function of energy for my PhD thesis) I'd be really concerned about the "uniform" part.
[1] https://en.wikipedia.org/wiki/Low-discrepancy_sequence https://en.wikipedia.org/wiki/Low-discrepancy_sequence
[2] https://extremelearning.com.au/unreasonable-effectiveness-of-quasirandom-sequences/ https://extremelearning.com.au/unreasonable-effectiveness-of...
[3] https://numerical.recipes/ https://numerical.recipes/
- fouronnes3 2y agoThanks for the links. Yeah, I'm not too sure that "uniform" is the right term here. I'm happy to be corrected on what the best term is for that specific set of requirements. It's surprising how hard a time I've had googling this problem. Surely I'm far from the first to wonder about it. I think a mix of AI enshittification, and the ambiguous meanings of "sampling" and "uniform" made it hard to find good material on it.
- PaulHoule 2y agoSampling points on a disc is a special problem that turns up a lot in practice. One obvious thing to do is just sample points on the square and throw out the ones that aren't in the disc but numericists don't like the throwing away bit because of performance. That Numerical Recipes book [1] has a section on it (has one on disc sampling and those sexy quasirandom numbers), the #1 answer on this StackOverflow page describes an algorithm that I remember from it. https://stats.stackexchange.com/questions/481543/generating-random-points-uniformly-on-a-disk https://stats.stackexchange.com/questions/481543/generating-... [1] I took a class on numerics taught by one of the authors; great book but it's a shame about the software license
- mturmon 2y ago> ...numericists don't like the throwing away bit... Although in 2 dimensions (setting of OP), this isn't that bad (you waste a proportion of (1-pi/4), or 21%, of your samples) -- perhaps 21% might be worth worrying about for some applications. Of course, it gets much worse in higher dimensions, because the unit ball is much smaller than the unit cube there.
- mattkrause 2y agoThis obviously depends on a million other factors too (implementation, language, architecture, etc) but I've benchmarked this a few times and, at least for naive implementations in 2D/3D, rejection sampling was often faster.
- a_e_k 2y agoIn graphics, we also often try to avoid any kind of rejection sampling because it wrecks importance sampling.
- mturmon 2y agoHmm, interesting. Is this still the case if the rejection factor is known explicitly (as it would be here)?
- cozzyd 2y agoMaybe you mean something like regular? I wouldn't call this sampling uniform.
- Sharlin 2y agoOne use case that immediately comes to mind as a hobbyist graphics coder is generating rays to simulate things like depth of field or soft shadows.