NetNews Usenet Archive 1992 #27/NN_1992_27.iso/spool/comp/os/msdos/programm/10879

Internet Message Format | 1992-11-24 | 2.6 KB

Path: sparky!uunet!zaphod.mps.ohio-state.edu!usc!elroy.jpl.nasa.gov!ames!sun-barr!cs.utexas.edu!ut-emx!slcs.slb.com!leo.asc.slb.com!nobelium!hargrove
From: [e-mail] (Jim Hargrove)
Newsgroups: comp.os.msdos.programmer
Subject: Re: Fast Square Root (All integer?)
Message-ID: <[e-mail]>
Date: 23 Nov 92 23:12:07 GMT
References: <[e-mail]> <[e-mail]>
Sender: hargrove@nobelium (Jim Hargrove)
Organization: Schlumberger Austin Systems Center
Lines: 67
NNTP-Posting-Host: nobelium.asc.slb.com

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 <[e-mail]>, [e-mail] (John A. Slagel) writes:
|> [e-mail] (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
|>  [e-mail]           shitty world, never chase buses or women- you
|>  [phone]               always get left behind." -The Marlboro Man

--

        -- jwh