quick distance algorithm

Yeah, if you wanted to find out if the distance was less than 12 you could just see if D < 144 (D being x^2 + y^2). Unfortunately, you couldn''t find the exact distance and typing in the squares of all the numbers doesn''t seem too efficient either. What you could do is if you don''t always need to find the distance, use that algorithm to see if you do, and then use the sqrt equation. This way you aren''t using it all the time.

Masters Software

I asked this question once. It''s somewhere deep within the gamedev message board. Most of the responses said something about using table based square roots. It isn''t that accurate, but it should work. It''s obviously not good for something like lighting calculations.

------------------------
Captured Reality

Yeah, I think tables wouldn''t be so great in this situation.
The way you''re doing it should be pretty fast.

lntakitopi@aol.com - http://www.geocities.com/guanajam

If you wanted something a little more accurate than using A LUT then you could generate a Taylor Series for the square root function and Use a second, third, or fourth Degree Taylor Polynomial to calculate the square roots, which would be faster than using sqrt and more acurrate than using a LUT.

DAMMIT! I was just going to say that.

Taylor series rule.

Of course, you have to be sure your order of magnitue is such that leaving of higher polynomials will not _TOO_ adversely affect the calculation.

Also, if you do it this way, make sure you do the polynomial the smart way:
x^3 + 2x^2 - 5x + 4 == 4 + x * ( -5 + x * (2 + x * (x) ) )

[evil grin]

It seems that y = sqrt(x) is a nightmare.
I have done a simple test and I found that sqrt is only 10 times slower than a simple floating point multiplication : is it true?
(I've made the test in C with a PIII 500MHz)

How many sqrt did you need in your application ?
If you mantain a frame rate of 50Hz and you need only one test per frame you have only 50 sqrt per second!

I'm not sure that sqrt algorithm uses Taylor series : Taylor series are useful to approximate a function in a point but you need the value of the function in that point ( that is sqrt(x) )
and the values of the derivates in that point.
But of course: I'm not sure!

Dear Stoffel, what is your formula?
sqrt(x) != x^3 + 2x^2 - 5x + 4

A simple algorithm is the Newton one:

y = sqrt(x) -> y' = 0.5 * ( y + x/y )
with an initial value of y (for example y=x/2 ) we get y'...we use y' and get y'' and so on.

My question: is it faster than a simple (but super assembler optimized) sqrt() ?
A lot of commercial games have used (and use) look up tables with fixed point math but I think that the age of fixed point math is finished !

Edited by - Andrea on July 7, 2000 7:15:51 PM