Hey. I was wondering if anyone new of a very fast sqrt approximation function. I just need it to be accurate to integers... no floating point necessary. Also, it can''t be a lookup table, because I''m dealing with numbers that are much too big. -Derek

Honestly, the fastest way I know of is to not use the square root. If you are looking for distance comparisons, square both sides of the equation.

i.e. distance^2=(x*x+y*y) ... involes no nasty 70 cycle approximation.

You could use this method to get integral square roots:

int sqrt(int A)
{
int x = A;
int OldA;
do
{
OldA = A;
A = (x + A / x) >> 1;
} while(OldA != A)
return A;
}
I haven''t tried the code example above. (It could have some faults in it)
You can change the line: int x = A;
to: int x = A >> 1;
This will make it much faster but it just works for numbers above 3.

I don''t think it''s the fastest way to do it but it squares 100 in 4 iterations and I think thats pretty good. It could be optimized by writing it in assembler. My advice to you is to use the square root function in your math library because it makes use of your math coprocessor which definitely is the fastest way to do this.

I found this in PDF format:
http://www.worldserver.com/turk/computergraphics/FixedSqrt.pdf