PDA

View Full Version : fast sqrt()



nomad
05-17-2002, 02:25 AM
Hi, anyone here knows how to do fast square roots? Thanks.

hoshi55
05-17-2002, 03:03 AM
there is a fast pythagoras approximation, if that's what you need. i think it's

'larger value minus (smaller value divided by 4)', so you can speed up the by 4 part with a shift <<2.
maybe that's the wrong formula i'll look it up when i get home but it goes something like that. also works for 3 coefficients, run the formula with first two coefficients then witht he result and the third coeff.

note that this approximation returns extremely wrong results for *few* conditions so you better not rely on this for some very important tasks.
consider that the math coprocesssors that CPUs nowadays are fitted with are incredibly speedy for square roots and you'll probably won't have any performance hit.

hth
eik

Robbo
05-17-2002, 03:46 AM
I agree with the above. FPU sqrt timings are pretty quick these days anyway - surely quicker than using approximation algorithms.

hoshi55
05-17-2002, 09:11 AM
anyway, here's the code:

GLfloat fastdist2(GLfloat x, GLfloat y)
{
// fast pythagoras approximation
if(x<0) x=-x;
if(y<0) y=-y;

if(x>y)
return (x+(y/4.0));
else
return (y+(x/4.0));
// return sqrt(x*x+y*y);
}


GLfloat fastdist3(GLfloat x, GLfloat y, GLfloat z)
{
// the same, only for 3 dimensions
GLfloat res;

if(x<0) x=-x;
if(y<0) y=-y;
if(z<0) z=-z;

if(x>y)
res = (x+(y/4.0));
else
res = (y+(x/4.0));
return fastdist2(res, z);
//return sqrt(x*x+y*y+z*z);
}

where x,y,z are the vector from one point to another...

play with it but it won't make your app faster i guess http://www.opengl.org/discussion_boards/ubb/smile.gif

eik

nomad
05-17-2002, 09:50 PM
really? i didn't knew sqrt()s these days are faster...thanks anyway guys!

rts
05-17-2002, 10:28 PM
It doesn't get much faster than this (note: GNU syntax here, adapt as needed. Also note this is x86 only)




#define fsqrt(f) \
({float _f = (f), _ans; asm ("fsqrt" : "=t" (_ans) : "0" (_f)); _ans;})

#define fsin(a) \
({float _a = (a), _s; asm ("fsin" : "=t" (_s) : "0" (_a)); _s;})

#define fcos(a) \
({float _a = (a), _c; asm ("fcos" : "=t" (_c) : "0" (_a)); _c;})

#define fabs(f) \
({float _f = (f), _ans; asm ("fabs" : "=t" (_ans) : "0" (_f)); _ans;})

#define fsincos(a, s, c) \
{ \
float _a = (a); \
float *_s = (s); \
float *_c = (c); \
\
asm ("fsincos" \
: "=t" (*_c), "=u" (*_s) \
: "0" (_a)); \
}

05-20-2002, 04:54 PM
Just for historical meanings... there was a guy called HERON who thought about interpolating a square root of any given number iteratively...

calculating the sqrt of value
x(0) should be a good guess or any other number, for example value/2

x(n+1) = 0.5 * ( x(n) + value / x(n) )

this thing terminates after just a few steps, depending how much into comma-detail you want to go...

have fun with it

Thug
05-22-2002, 05:59 AM
If you just want to compare distances, compare the distance squared and forget about the square root.