4 ms·
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 infini
by 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 agoThe 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 agoCould you say a little more about what relevance 0.48 has here?
- mrastro 8y agoFrom the article: "about 48% of the points chosen are discarded".
- magicalhippo 8y agoIt'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 agoBut 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.