News for hackers. Stuff that matters.
Re:Generating random points inside a sphere by alstange on Saturday August 04, 2018 @07:14PM (#17688891)
So which algorithm ended up being fastest?
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.

Re:Generating random points inside a sphere by cs_ on Saturday August 04, 2018 @11:12PM (#17689466)
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.