nomad

05-17-2002, 01:25 AM

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

View Full Version : fast sqrt()

nomad

05-17-2002, 01:25 AM

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

hoshi55

05-17-2002, 02: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

'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, 02: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, 08: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

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, 08:50 PM

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

rts

05-17-2002, 09: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)); \

}

#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, 03: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

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, 04:59 AM

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

Powered by vBulletin® Version 4.2.3 Copyright © 2017 vBulletin Solutions, Inc. All rights reserved.