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.
So I'd wager that the 50% reject rate would still be cheaper at scale than evaluating trigonometric functions.