4 ms·
The graphics are nice, but this article really could have used some complexity analysis and some probability theory. The author neither discusses the asymptoma
by charmides 8y ago
The graphics are nice, but this article really could have used some complexity analysis and some probability theory.
The author neither discusses the asymptomatic complexity of the algorithms, nor the run-time of his implementation (which is more pertinent here), nor gives any proofs of why some of the algorithms sample uniformly from the unit ball and why some of them don't.
Also, it would have been really nice to generalize this problem to n dimensions. I assume that there is some small value of n where naive rejection sampling is worse in practice than one of the more sophisticated methods.
- jpatokal 8y agoDoes he need to? All algorithms given except the first appear to be O(N), and their performance is going to depend almost entirely on how fast the local implementations of trig operations involved are.
- gamegoblin 8y agoIsn’t the first method still O(N)? You will reject a constant percentage of points on average (the author says 48%), but constants fall out of big-O.
- jpatokal 8y agoThat's true if you assume a while pending on rand() is constant, but that wasn't covered in my CS 101 on complexity analysis...
- Sharlin 8y agoAverage-case constant. Worst case? Never halts. Generating a single point doesn’t depend at all on our choice of n (the number of points generated). But yeah, complexity analysis of stochastic algorithms is fairly advanced stuff.
- heavenlyblue 8y agoIt never halts under the condition of infinitely small probability. So it never never halts.
- Sharlin 8y agoYeah, the worst case is more of a limit. If you're really unlucky the algorithm can take an arbitrarily long time to halt.
- bo1024 8y agoMeasure 0 and "never" are subtly different. There do exist sets of random draws for which the algorithm never halts. The probability of getting such a draw is zero, but they exist. It's like picking a random number uniformly between 0 and 1 (in theory, not on a discrete computer). Getting 2 is impossible, never happens. Getting say 1.5 has probability 0, but it is possible.
- deleted 8y ago[deleted]
- Sharlin 8y ago(Getting 0.5 I think you mean :)
- bo1024 8y agoRight, thanks
- heavenlyblue 8y agoWell, for the starts - I said it was an "infinitely small probability" (just as you've said it's zero), so I said "never" because it's more of a practical question. With the same logic you can say that sha-256 is easily reversible by iterating over all possible mappings from sha256(z) to x. But it isn't. Purely because of the sheer scale of that number. And to be clear: reversing sha-256 under the condition of sha-256 being a perfect hash function is the same as drawing 256 zeros from a purely random function. The best way to go about the complexity of this algorithm is the runtime density function, where the total number of samples defines how many additional (false) iterations we'd need to do on average.
- xxs 8y agodepends how random works, techinically it may never exit the loop. Rejection algos could be quite dangerous under specific conditions. I would agree with the grandparent - it's a weak article.