🚀 go-pugleaf

In article <1idsq6INNced@flop.ENGR.ORST.EDU> murrayk@prism.CS.ORST.EDU (the Dodger) writes:
>
>Well? Does anyone know of a quick and dirty way to get a reasonably accurate
>square root of a fixed point integer number? My numbers are stored in a 16.16
>bit format. I've heard of a few ways, but I'm open for ideas. I just want to
>keep on avoiding floating point for ethical reasons. 8^)
I have read a method for integers in a computer magazine some time
ago, and it should work for fixed point numbers, also.

Here we go: You can interpret the 16.16 number as (32bit int)/(2^16),
true? The result can be up to 8.16 accurate, but this depends on the
upper 16 bits of your fixed point number. I'll show you a fast way for
8.8 accuracy and leave the remaining 8 bit as an exercise to the
reader ;-)...

The way to go is succesive approximation:
root is the (yet to be calculated) root  8, radicant is the radicant
<< 16, which is obtained by simply interpreting the fix as long.

	for (j = 128, root = 0; j || root*root == radicant; j >>= 1)
	  if ((root + j)*(root + j) >= radicant)
	    root += j;
	root <<= 8;	/* now you can cast it back to the fix format */

If you need performance, you can do some bit optimization by
calculating (root + j)^2 iteratively from the last value:

	for (j = 128, jj = 16384, root = 0, rr2 = rr = 0;
			 j || rr = radicant; j >>= 1, jj >>= 2, rr2 >>= 1)
	  if ((rr1 = rr + rr2 + jj) >= radicant)
	    root += j, rr = rr1, /* = root^2 */ rr2 += jj*2 /* = 2*root*j */; 

-- 
				- Thomas

   greve@rs1.thch.uni-bonn.de
   unt145@dbnrhrz1