🚀 go-pugleaf

The following seems to be a very reasonable solution for the GENERAL case. If, on the other hand, you have a smaller range of integers, you may want to use a table lookup instead. This trick has been used in computer graphics for years. It works best when you are limited to 12 bits or less. Then the table is a reasonable size.
In article <Bxw6oM.IKC@news.cso.uiuc.edu>, jas37876@uxa.cso.uiuc.edu (John A. Slagel) writes:
|> 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

-- 

        -- jwh