🚀 go-pugleaf

wagner@main.mndly.umn.edu (Rick Wagner) writes:

>Does anyone have any ideas (or code) on how to implement a FAST square root 
>algorythm in C that only uses integers?  Obviously this only needs to be 
>an approximation of the square root, the key factor here is speed.

>Any Ideas?

   Well, from a Numerical Computing class, we have this algorithm:

   procedure square root of c with error <= E
       x := 1;  y := x;
       while abs(x-y) > 2*E do
	   x:=(x+y)/2; y:= c/x
       end while
       return (x+y)/2

   I wrote it in Microsoft inline assembly for int's, with an error
   of 1.  Enjoy.


int isqrt( int c )
{
	_asm {
	mov     cx, 1
	mov     bx, c
	jmp     skip_iterate

iterate:
	mov     ax, cx
	sub     ax, bx   ; AX = x - y
	cwd
	xor     ax, dx
	sub     ax, dx  ; AX = abs( AX )
	cmp     ax, 2   ; 2 is the allowed error * 2, so we're getting within 1.
	jl      done    ; if abs(x-y) > 2 then goto done
skip_iterate:
	mov     ax, cx
	add     ax, bx
	shr     ax, 1
	mov     cx, ax   ; x = (x+y)/2
	cwd
	mov     ax, c
	idiv    cx
	mov     bx, ax   ; y = c / x
	jmp     iterate

done:
	mov     ax, cx
	add     ax, bx
	shr     ax, 1
	mov     c, ax
	}
	return c;
}

-- 
-----------------------------------------------------------------------------
 John A. Slagel              "My old man used to tell me, before he left this
 j-slagel1@uiuc.edu           shitty world, never chase buses or women- you
 (217) 337-7930               always get left behind." -The Marlboro Man