StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I'm disappointed that the great old mathematical tricks seem to be getting lost. Here is the answer you're asking for. Source is Paul Hsieh's excellent web site: <a href="http://www.azillionmonkeys.com/qed/sqroot.html" rel="nofollow noreferrer">http://www.azillionmonkeys.com/qed/sqroot.html</a> . Note that you don't care about distance; you will do fine for your sort with square of distance, which will be much faster.</p> <hr> <p>In 2D, we can get a crude approximation of the distance metric without a square root with the formula:</p> <blockquote> <p>distanceapprox (x, y) = <a href="http://www.wolframalpha.com/input/?i=%281+%2B+1%2F%284-2*sqrt+2%29%29%2F2+*+minimum%28%281+%2F+sqrt+2%29*%28%7Cx%7C%2B%7Cy%7C%29%2C+max+%28%7Cx%7C%2C+%7Cy%7C%29%29" rel="nofollow noreferrer">(1 + 1/(4-2*√2))/2 * min((1 / √2)*(|x|+|y|), max (|x|, |y|)) http://i52.tinypic.com/280tbnc.gif</a></p> </blockquote> <p>which will deviate from the true answer by at most about 8%. A similar derivation for 3 dimensions leads to:</p> <blockquote> <p>distanceapprox (x, y, z) = <a href="http://www.wolframalpha.com/input/?i=%281+%2B+1%2F%284+sqrt+3%29%29%2F2+*+minimum%28%281+%2F+sqrt+3%29*%28%7Cx%7C%2B%7Cy%7C%2B%7Cz%7C%29%2C+max+%28%7Cx%7C%2C+%7Cy%7C%2C+%7Cz%7C%29%29" rel="nofollow noreferrer">(1 + 1/4√3)/2 * min((1 / √3)*(|x|+|y|+|z|), max (|x|, |y|, |z|)) http://i53.tinypic.com/2vlphz8.gif</a></p> </blockquote> <p>with a maximum error of about 16%.</p> <p>However, something that should be pointed out, is that often the distance is only required for comparison purposes. For example, in the classical mandelbrot set (z←z2+c) calculation, the magnitude of a complex number is typically compared to a boundary radius length of 2. In these cases, one can simply drop the square root, by essentially squaring both sides of the comparison (since distances are always non-negative). That is to say:</p> <pre><code> √(Δx2+Δy2) < d is equivalent to Δx2+Δy2 < d2, if d ≥ 0 </code></pre> <p>I should also mention that Chapter 13.2 of Richard G. Lyons's "Understanding Digital Signal Processing" has an incredible collection of 2D distance algorithms (a.k.a complex number magnitude approximations). As one example:</p> <blockquote> <p>Max = x > y ? x : y;</p> <p>Min = x < y ? x : y;</p> <p>if ( Min < 0.04142135Max )</p> <pre><code>|V| = 0.99 * Max + 0.197 * Min; </code></pre> <p>else</p> <pre><code>|V| = 0.84 * Max + 0.561 * Min; </code></pre> </blockquote> <p>which has a maximum error of 1.0% from the actual distance. The penalty of course is that you're doing a couple branches; but even the "most accepted" answer to this question has at least three branches in it.</p> <p>If you're serious about doing a super fast distance estimate to a specific precision, you could do so by writing your own simplified fsqrt() estimate using the same basic method as the compiler vendors do, but at a lower precision, by doing a fixed number of iterations. For example, you can eliminate the special case handling for extremely small or large numbers, and/or also reduce the number of Newton-Rapheson iterations. This was the key strategy underlying the so-called "Quake 3" <a href="https://en.wikipedia.org/wiki/Fast_inverse_square_root" rel="nofollow noreferrer">fast inverse square root</a> implementation -- it's the classic Newton algorithm with exactly one iteration.</p> <p>Do not assume that your fsqrt() implementation is slow without benchmarking it and/or reading the sources. Most modern fsqrt() library implementations are branchless and really damned fast. <a href="https://opensource.apple.com/source/Libm/Libm-93/ppc.subproj/sqrt.c" rel="nofollow noreferrer">Here for example is an old IBM floating point fsqrt implementation.</a> <a href="https://en.wikipedia.org/wiki/Program_optimization" rel="nofollow noreferrer">Premature optimization</a> is, and always will be, the root of all evil.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload