home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / sci / math / 18654 < prev    next >
Encoding:
Internet Message Format  |  1993-01-22  |  1.9 KB
  1. Path: sparky!uunet!mcsun!uknet!comlab.ox.ac.uk!comlab.ox.ac.uk!mnewman
  2. From: mnewman@comlab.ox.ac.uk (Matthew Newman)
  3. Newsgroups: sci.math
  4. Subject: Square root alg.
  5. Message-ID: <1993Jan22.160539.5493@client41.comlab.ox.ac.uk>
  6. Date: 22 Jan 93 16:05:39 GMT
  7. Sender: mnewman@comlab.ox.ac.uk (Matthew Newman)
  8. Organization: Oxford University Computing Laboratory, UK
  9. Lines: 65
  10. Originator: mnewman@client41.comlab
  11.  
  12. Someone asked for a square root algorithm.
  13.  
  14. To work out what the algorithm is observe
  15. that if N = a1 + 100a2 (+ 10000a3 + ...)
  16. and Sqrt(N) = b1 + 10b2 (+ 100 b3 + ...)
  17. then N = (b1 + 10b2)(b1 + 10b2) = b1^2 + 100b2^2 + 20b1b2
  18.  
  19. So, suppose you want to calculate the square root of N, we keep
  20. track of three numbers, Res (the result), Rem (a remainder type
  21. variable) and Add (something else!).
  22.  
  23. From the decimal point, pair off the digits of N (both left and
  24. right e.g. N = 127.345 -> 01 27 . 34 50)
  25.  
  26. Initially Res = 0
  27.           Rem = Left most pair from N
  28.           Add = 0
  29.  
  30. Recursively choose x largest such that (Add + x)x <= Rem
  31.  
  32. Next, let Res' = Res*10 + x
  33.           Rem' = 100*(Rem-(Add + x)x) + next pair of digits from N
  34.           Add' = 10*(Add + 2x)
  35.  
  36. and repeat 'till done (i.e. until Rem=0 or Res is long enough). You have
  37. to keep track of where the decimal point comes into Res, but it's fairly
  38. obvious (!).
  39.  
  40. An example might help !
  41.  
  42.   N = 4096  = 40 96
  43.   Res = 0
  44.   Rem = 40
  45.   Add = 0
  46.  So the first x is 6 (since 6*(0+6)=36, and 7*(0+7)=49)
  47.   Res' = 6
  48.   Rem' = 400 + 96 = 496
  49.   Add = 120
  50.  The next x is thus 4, since 4*(120+4)=496
  51.   Res'' = 64
  52.   Rem'' = 0
  53.   Add = 256
  54. and we're done
  55.  
  56.   N = 2 = 02 . 00 00 00 00 ...
  57.   Res = 0
  58.   Rem = 2
  59.   Add = 1
  60.  so x is 1
  61.   Res' = 1
  62.   Rem' = 100
  63.   Add' = 20
  64.  so x is 4
  65.   Res'' = 1.4 (note that the decimal point comes in here ...)
  66.   Rem'' = 400
  67.   Add'' = 280
  68.  so x is 1
  69.   Res''' = 1.41
  70.   Rem''' = 11900
  71.   Add''' = 2820
  72.  so x is 4
  73.   Res'''' = 1.414
  74.   Rem'''' = 60400
  75.   Add'''' = 28280
  76.  and so on for ever ...
  77.