* Paul Reiners <paul.reiners@gmail.com> [Sep 15. 2009 12:54]:
[...]
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). [...]
Could you use the inverse sqrt? (should be fine if the quantity is used only for comparison) If so, compute the first 1/sqrt(.) and update with the divisionless iteration (second or third order) for 1/sqrt(.): 1/sqrt(d)= x*1/sqrt(1-y) where y=1-d*x^2 1/sqrt(d) = x * ( 1 + y/2 + 3*y^2/8 + ... ) 2nd order iteration is x_+ := x * ( 1 + y/2 ) 3rd order is x_+ := x * ( 1 + y/2 + 3*y^2/8 ) Also pulling out y may help: sqrt(y^2+(x+1)^2) == y* sqrt(1 + ((x+1)/y)^2 ) (precompute 1/y, so division becomes multiplication) Btw. SIMD instruction sets tend to have a fast and low accuracy sqrt() ( and slightly faster 1/sqrt() ).