home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / os / msdos / programm / 10729 < prev    next >
Encoding:
Text File  |  1992-11-17  |  2.0 KB  |  73 lines
  1. Newsgroups: comp.os.msdos.programmer
  2. Path: sparky!uunet!charon.amdahl.com!pacbell.com!ames!elroy.jpl.nasa.gov!sdd.hp.com!ux1.cso.uiuc.edu!news.cso.uiuc.edu!uxa.cso.uiuc.edu!jas37876
  3. From: jas37876@uxa.cso.uiuc.edu (John A. Slagel)
  4. Subject: Re: Fast Square Root (All integer?)
  5. References: <wagner.902.722036355@main.mndly.umn.edu>
  6. Message-ID: <Bxw6oM.IKC@news.cso.uiuc.edu>
  7. Sender: usenet@news.cso.uiuc.edu (Net Noise owner)
  8. Organization: University of Illinois at Urbana
  9. Date: Wed, 18 Nov 1992 03:21:55 GMT
  10. Lines: 61
  11.  
  12. wagner@main.mndly.umn.edu (Rick Wagner) writes:
  13.  
  14. >Does anyone have any ideas (or code) on how to implement a FAST square root 
  15. >algorythm in C that only uses integers?  Obviously this only needs to be 
  16. >an approximation of the square root, the key factor here is speed.
  17.  
  18. >Any Ideas?
  19.  
  20.    Well, from a Numerical Computing class, we have this algorithm:
  21.  
  22.    procedure square root of c with error <= E
  23.        x := 1;  y := x;
  24.        while abs(x-y) > 2*E do
  25.        x:=(x+y)/2; y:= c/x
  26.        end while
  27.        return (x+y)/2
  28.  
  29.    I wrote it in Microsoft inline assembly for int's, with an error
  30.    of 1.  Enjoy.
  31.  
  32.  
  33. int isqrt( int c )
  34. {
  35.     _asm {
  36.     mov     cx, 1
  37.     mov     bx, c
  38.     jmp     skip_iterate
  39.  
  40. iterate:
  41.     mov     ax, cx
  42.     sub     ax, bx   ; AX = x - y
  43.     cwd
  44.     xor     ax, dx
  45.     sub     ax, dx  ; AX = abs( AX )
  46.     cmp     ax, 2   ; 2 is the allowed error * 2, so we're getting within 1.
  47.     jl      done    ; if abs(x-y) > 2 then goto done
  48. skip_iterate:
  49.     mov     ax, cx
  50.     add     ax, bx
  51.     shr     ax, 1
  52.     mov     cx, ax   ; x = (x+y)/2
  53.     cwd
  54.     mov     ax, c
  55.     idiv    cx
  56.     mov     bx, ax   ; y = c / x
  57.     jmp     iterate
  58.  
  59. done:
  60.     mov     ax, cx
  61.     add     ax, bx
  62.     shr     ax, 1
  63.     mov     c, ax
  64.     }
  65.     return c;
  66. }
  67.  
  68. -- 
  69. -----------------------------------------------------------------------------
  70.  John A. Slagel              "My old man used to tell me, before he left this
  71.  j-slagel1@uiuc.edu           shitty world, never chase buses or women- you
  72.  (217) 337-7930               always get left behind." -The Marlboro Man
  73.