Jump to content
  • Advertisement
Sign in to follow this  
Zmurf

The Square-Root Formula

This topic is 4723 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Advertisement
Guest Anonymous Poster
Derive the Taylor power series of the function, take the partial sum of however many terms you want (more terms yield better accuracy), and evaluate it at x, the argument of sqrt(x).

Share this post


Link to post
Share on other sites
try newtons method

float SQRT( float Number )
{
float Answer= my_favorite_number;

for ( num_iterations )
{
Answer= 0.5 * ( Answer * Answer + Number ) / ( Answer);
}
}

i hope this is right its from my head

Share this post


Link to post
Share on other sites
Newton approximation implemented in C:


float IterSqrtf(float r, int numtries)
{
float m(0.0f);
float b(0.0f);
float currx=r;
float curry(0.0f);
float root(0.0f); //this is what gets returned

while(numtries--)
{
curry = (currx*currx) - r; //y1
//Check to see if curry is < 0
m = 2 * currx;
b = (-m*currx) + curry;
root = -b / m;
currx = root;
}
return root;
}





Newton approximation implemented in x87 (FPU) assembly):


Number DD ?
TestResult DW?
Two DD 2.0
MaxRelErr DD 0.5E-6

Sqrt:
fld1
REPEAT01:
fld ST
fld Number
fdiv ST,ST(1)
fadd ST,ST(1)
fDiv Two
fst ST(2)

fsub
fabs
fld MaxRelErr
fmul ST,ST(2)
fcompp
fstsw TestResult
fwait
mov ax, TestResult
sahf
jna REPEAT01
ret




Square root hack approximation that doesn't even rely on the FPU along with the explanation for how it works


float Faster_Sqrtf(float f)
{
float result;

_asm
{
mov eax, f
sub eax, 0x3f800000
sar eax, 1
add eax, 0x3f800000
mov result, eax
}

return result;
}



1. Although the magic number 0x3f800000 just happens to be the
floating point representation of +1.0, here it is represents the bias
in a 32-bit float. (127)

2. The sar instruction is "shift arithmetic right" which replicates
the top bit but shifts all other bits one to the right. This has the
effect of dividing by two. It could just as well be "shr". The use of
sar means that it returns the square root of a negative number as a
negative number.

The sub instruction effectively converts the exponent to a unsigned
integer from a bias-127 integer.
The SAR instruction then divides both the mantissa and the unsigned
integer by 2. Where we had n= 1.x * 2^y we now have either 1.1x *
2^(y\2) or 1.0x * 2(y\2), depending on whether the low order bit of
the exponent was set. You can work out the algebra to see what
happens when you square these things. (Note that in base 10 these
represent 2.5+x and 2.0+x respectively) You get a very crude
approximation of a square root. It undoubtedly has more accuracy in a
certain limited range.

The final add then converts the exponent back to a bias-127 exponent.

consider
45000000h = 2048

sub eax, 3f800000h ->
0100 0101 0000 0000 0000 0000 0000 0000
-0011 1111 1000 0000 0000 0000 0000 0000

= 0000 0101 1000 0000 0000 0000 0000 0000

sar eax,1 _>
= 0000 0010 1100 0000 0000 0000 0000 0000

add eax, 3f800000h ->
0000 0010 1100 0000 0000 0000 0000 0000
+0011 1111 1000 0000 0000 0000 0000 0000
=0100 0010 0100 0000 0000 0000 0000 0000 = 42400000 = 48

The square root of 2048 is 42.something, and 48 * 48 = 2304.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!