Hey, I need to find an algorithm to do a fast floating point square root. I don''t believe there is a way for me to get around using the sqrts, so I need them to be as fast as possible. Also, is there any way to get around an acos() call but with basically the same results? Thanks, Ben

are you sure you REALLY need to use square root ?
how about this instead.........(if you are using to check how far something is away from something else

    // your wayfloat distance = sqrt(diffX squared + diffY squared); //SLOOOWif (distance == testDistance)  doSeomthing();// better wayfloat distance = diffX squared + diffY squared;if (distance == testDistance_squared)  doSomething();    

"Now go away or I shall taunt you a second time"
- Monty Python and the Holy Grail
themGames Productions

How about using a lookup table?

There are some ways to do a fast approximation of the sqrt. I can't remember how to do this, but I bet if you lookup "fast phong" somewhere - you'll find more on fast sqrt approximations!



Edited by - baskuenen on October 20, 2000 10:13:44 PM

Go to Nvidia''s developer relations site, they have some source code for fast math functions (including quick lookup-table square root) under Programming Resources

You could use linear approximation if accuracy allows. Simply create a table of x, sqrt(x), and d/dx (sqrt(x)) for key values. Find the value closest to what you want to solve for, then use d/dx(sqrt(x)) (being the slope) and other values to create a line equation, solving for the true value. Not accurate, but really fast!
Example: x=5

Close to 4, so use 4, sqrt(4), and d/dx = 0.25. So, send a line through (4,2) with slope 0.25, solve for x=5! Voila, the approxmation yields 2.25, which isn''t too far from the real value of ~ 2.236.

You should''ve told how accurate sqrt you need.

Newton''s iteration is a quite good way to solve sqrt(c):

sqrt(c):
x0=c/2
x1=(x0+c/x0)/2
x2=(x1+c/x1)/2
x3=(x2+c/x2)/2
x4=(x3+c/x3)/2
x5=(x4+c/x4)/2

And now x5 is quite accurate value for sqrt(c)

Faster even if you are using C/C++ with ''/2'' replaced by ''>>1''

-Chris Bennett of Dwarfsoft - Site:"The Philosophers' Stone of Programming Alchemy" - IOL
The future of RPGs - Thanks to all the goblins over in our little Game Design Corner niche
          

quote: Original post by Anonymous Poster

You should''ve told how accurate sqrt you need.

Newton''s iteration is a quite good way to solve sqrt(c):

sqrt(c):
x0=c/2
x1=(x0+c/x0)/2
x2=(x1+c/x1)/2
x3=(x2+c/x2)/2
x4=(x3+c/x3)/2
x5=(x4+c/x4)/2

And now x5 is quite accurate value for sqrt(c)

It is the worst way to solve sqrt(c).
Each division is just <=2 times faster then sqrt.

I was going to paste a method of fast sqrt performance below, but it took to much room (150+ lines). But here is a link to my site and a zip (give me a few minutes to up load it). I didn't write this code - it's just lying around on my machine:-)

Apparently it does it in 20-30 cycles for a sqrt but is up to 6% inaccurate. Not suitable for raytracing, but in a rapidly moving game environment, perfectly acceptable.

http://homepage.dtn.ntl.com/grahamr/fastsqrt.zip

Stay Lucky, Graham "Mournblade" Reeds.
http://homepage.dtn.ntl.com/grahamr

Edited by - Graham Reeds on November 1, 2000 11:53:36 PM