Zmurf 100 Report post Posted November 11, 2005 I was wondering, what exactly is the forumla for finding the square root of a number? 0 Share this post Link to post Share on other sites
Guest Anonymous Poster Report post Posted November 11, 2005 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). 0 Share this post Link to post Share on other sites
Genjix 100 Report post Posted November 11, 2005 here's something nice. 0 Share this post Link to post Share on other sites
Raymond_Porter420 136 Report post Posted November 11, 2005 try newtons methodfloat 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 0 Share this post Link to post Share on other sites
tthibault 100 Report post Posted November 11, 2005 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.0MaxRelErr DD 0.5E-6Sqrt: fld1REPEAT01: 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 retSquare root hack approximation that doesn't even rely on the FPU along with the explanation for how it worksfloat 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 = 2048sub 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 0000sar eax,1 _>= 0000 0010 1100 0000 0000 0000 0000 0000add 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 = 48The square root of 2048 is 42.something, and 48 * 48 = 2304. 0 Share this post Link to post Share on other sites
ury 476 Report post Posted November 11, 2005 Check out this thread.PS. Raymond, you have a very good memory. :) 0 Share this post Link to post Share on other sites
Zmurf 100 Report post Posted November 11, 2005 thanks this is good 0 Share this post Link to post Share on other sites