Well, you can use something like the fast square root hack in IEEE floating point, which takes an initial guess: http://www.azillionmonkeys.com/qed/sqroot.html Here, the previous value is a really good estimate of the next one. On Mon, Sep 14, 2009 at 2:10 PM, Paul Reiners <paul.reiners@gmail.com> wrote:

This is a programming question I ran across.  Does anyone happen to know the answer?

I am processing a series of points which all have the same Y value, but different X values. I go through the points by incrementing X by one. For example, I might have Y = 50 and X is the integers from -30 to 30. Part of my algorithm involves finding the distance to the origin from each point and then doing further processing.

After profiling, I've found that the sqrt call in the distance calculation is taking a significant amount of my time. Is there an iterative way to calculate the distance?

In other words:

I want to efficiently calculate: r[n] = sqrt(x[n]*x[n] + y*y)). I can save information from the previous iteration. Each iteration changes by incrementing n, so x[n] = x[n-1] + 1. I can not use sqrt or trig functions because they are too slow except at the beginning of each scanline.

I can use approximations as long as they are good enough (less than 0.l% error) and the errors introduced are smooth (I can't bin to a pre-calculated table of approximations). The original question was posted here:

http://stackoverflow.com/questions/1423918/is-there-an-iterative-way-to-calc... _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike http://reperiendi.wordpress.com

Quoting Paul Reiners <paul.reiners@gmail.com>:

This is a programming question I ran across. Does anyone happen to know the answer? ..... After profiling, I've found that the sqrt call in the distance calculation is taking a significant amount of my time. Is there an iterative way to calculate the distance?

This problem was alreay vexing programmers at the ENIAC. Depending on the context, particularly if it was a matter of comparing distances and they were greater than 1, comparing squares sufficed and completely sidestepped the square roots. Pure square roots (don't use logarithms) in floating point are actually fairly economical; half the exponent and three cycles of Newton's approximation leave them only slightly worse than a few multiplications. -hvm ------------------------------------------------- www.correo.unam.mx UNAMonos Comunicándonos

On Mon, 14 Sep 2009, Paul Reiners wrote:

This is a programming question I ran across. Does anyone happen to know the answer?

I am processing a series of points which all have the same Y value, but different X values. I go through the points by incrementing X by one. For example, I might have Y = 50 and X is the integers from -30 to 30. Part of my algorithm involves finding the distance to the origin from each point and then doing further processing.

Here are some very low-tech approaches: If your X and Y domain is small, you could precompute a table of distances. If only your Y domain is small, precompute for x between -ymax^2 and ymax^2 and use distance~=abs(x) beyond that.