11 ms·

So which algorithm ended up being fastest?

jacobolus 8y ago
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.
Cyph0n 8y ago
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.
- Buge 8y ago
  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.
  - the8472 8y ago
    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.
    - glhaynes 8y ago
      Could you say a little more about what relevance 0.48 has here?
      - mrastro 8y ago
        From the article: "about 48% of the points chosen are discarded".
      - magicalhippo 8y ago
        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.
  - garmaine 8y ago
    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.
- cs_ 8y ago
  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
  - charmides 8y ago
    Those results are surprisingly close.
  - dmurray 8y ago
    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.
    - blattimwind 8y ago
      But why would you do that?

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.

Cyph0n 8y ago

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.

Buge 8y ago
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.
- the8472 8y ago
  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.
  - glhaynes 8y ago
    Could you say a little more about what relevance 0.48 has here?
    - mrastro 8y ago
      From the article: "about 48% of the points chosen are discarded".
    - magicalhippo 8y ago
      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.
- garmaine 8y ago
  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.
cs_ 8y ago
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
- charmides 8y ago
  Those results are surprisingly close.
- dmurray 8y ago
  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.
  - blattimwind 8y ago
    But why would you do that?