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.
[ Parent
| on HN ]
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.