Hacker News Reader

Comment by alstange | Hacker News Reader

So which algorithm ended up being fastest?

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

Those results are surprisingly close.

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.

But why would you do that?

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.

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.

Could you say a little more about what relevance 0.48 has here?

From the article: "about 48% of the points chosen are discarded".

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.

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.

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.

Reply on news.ycombinator.com