fast sqrt()

Hi, anyone here knows how to do fast square roots? Thanks.

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

I agree with the above. FPU sqrt timings are pretty quick these days anyway - surely quicker than using approximation algorithms.

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&gt;y)
	return (x+(y/4.0));
else
	return (y+(x/4.0));

// return sqrt(xx+yy);
}

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

if(x&lt;0) x=-x;
if(y&lt;0) y=-y;
if(z&lt;0) z=-z;

if(x&gt;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

eik

really? i didn’t knew sqrt()s these days are faster…thanks anyway guys!

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 = ©;

asm (“fsincos”
: “=t” (
_c), “=u” (
_s)
: “0” (_a));
}

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

If you just want to compare distances, compare the distance squared and forget about the square root.