I don't know if it answers your question or not, but you should be aware of Hakmem #149 & following: http://home.pipeline.com/~hbaker1/hakmem/hacks.html#item149 At 02:10 PM 9/14/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.

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