Hacker News Reader

Comment by charmides | Hacker News Reader

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.

View on HN

Does 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.

Isn’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.

That's true if you assume a while pending on rand() is constant, but that wasn't covered in my CS 101 on complexity analysis...

Average-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.

It never halts under the condition of infinitely small probability. So it never never halts.

Yeah, the worst case is more of a limit. If you're really unlucky the algorithm can take an arbitrarily long time to halt.

Measure 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.

(Getting 0.5 I think you mean :)

Right, thanks

Well, 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.

depends 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.

Reply on news.ycombinator.com