Re:Generating random points inside a sphere
by alstange on Saturday August 04, 2018 @07:14PM
(#17688891)
So which algorithm ended up being fastest?
[ Parent
| on HN ]
Re:Generating random points inside a sphere
by Cyph0n on Saturday August 04, 2018 @07:26PM
(#17688917)
To my untrained eye, it looks like the first naive algorithm would be fastest. Two of them require trig functions while the other relies on sqrt and cube root, all of which are expensive functions when compared to the first approach.
So I'd wager that the 50% reject rate would still be cheaper at scale than evaluating trigonometric functions.
A quick test with C++'s <random> library agrees. For n = 100,000,000 points, the rejection method beat out the improved spherical by 7.8%. Using the normal distribution was even slower.
XYZ: 16.418057 seconds
Gauss: 23.415560 seconds
Spherical: 17.705553 seconds
Re:Generating random points inside a sphere
by charmides on Sunday August 05, 2018 @12:00AM
(#17689593)
Those results are surprisingly close.
Re:Generating random points inside a sphere
by dmurray on Sunday August 05, 2018 @05:41AM
(#17690522)
Youll get a different result if random number generation is made more expensive, e.g. if you need to use a hardware RNG instead of a PRNG.
Re:Generating random points inside a sphere
by blattimwind on Sunday August 05, 2018 @08:50AM
(#17691072)
But why would you do that?
Re:Generating random points inside a sphere
by Buge on Saturday August 04, 2018 @07:48PM
(#17688971)
But you might want to consider average case time and worst case time. The first algorithm might have a good average case time, but its worst case time is infinity, which might be unacceptable.
Re:Generating random points inside a sphere
by the8472 on Saturday August 04, 2018 @08:09PM
(#17689021)
The probability of experiencing bad cases decays exponentially with the number of iterations. 0.48^n.
Your CPU would spontaneously undergo fusion by tunneling before hitting on a case where it's stuck on a bad case for more than 10 microseconds.
Re:Generating random points inside a sphere
by glhaynes on Saturday August 04, 2018 @09:57PM
(#17689298)
Could you say a little more about what relevance 0.48 has here?
Re:Generating random points inside a sphere
by mrastro on Saturday August 04, 2018 @10:04PM
(#17689316)
From the article: "about 48% of the points chosen are discarded".
Re:Generating random points inside a sphere
by magicalhippo on Sunday August 05, 2018 @02:44AM
(#17690068)
It's the fraction of the volume of a cube enclosing (bounding) a sphere to the volume of that sphere.
1 - 4/3*pi*r^3 / (2*r)^3 = ~0.4764
The algorithm samples points inside a unit cube and rejects those not inside the unit sphere, so that's the fraction of points it'll be discarding.
Re:Generating random points inside a sphere
by garmaine on Sunday August 05, 2018 @04:46AM
(#17690388)
But if the randomness was based on secret information, you've now introduced a timing or power analysis attack to extract that secret information. The other solutions, although slower, have the advantage of being constant-time.
Re:Generating random points inside a sphere
by jacobolus on Saturday August 04, 2018 @07:19PM
(#17688906)
Depends on how fast your PRNG is, but I would expect the rejection method to be best under pretty much any circumstances. The code is also simplest. If PRNG speed becomes a bottleneck just use a faster PRNG.