🚀 go-pugleaf

In article <16075@watdragon.waterloo.edu> afscian@violet.waterloo.edu (Anthony Scian) writes:
>Does anybody remember the algorithm or any references?
Thanks to everybody for the e-mail, here it is:
Nobody knew of any references.

e.g., sqrt(2)

1) group digits into pairs outward from decimal point

      _______________
    \/ 02.00 00 00 00

2) first digit is the approximate root (floor(sqrt())) of the first 2 digits
        1
      _______________
  1 \/ 02.00 00 00 00

3) multiply and subtract and bring two digits down
        1
      _______________
  1 \/ 02.00 00 00 00
        1
       --
        1 00

4) double current root, multiply by 10, units digit is the unknown
        1  x
      _______________
  1 \/ 02.00 00 00 00
    |   1
    |  --
 2x |   1 00

5) a good estimate of x is current remainder divided by number with x=0
   (in this case 100/20=5, OK, in this case it is bad!)
        1  5
      _______________
  1 \/ 02.00 00 00 00
    |   1
    |  --
 25 |   1 00
        1 25 (too large!)

6) find proper guess, multiply and repeat

        1  4  x
      _______________
  1 \/ 02.00 00 00 00
    |   1
    |  --
 24 |   1 00
    |     96
    |   ----
28x |      4 00

etc...

        1  4  1  4  2
      _______________
  1 \/ 02.00 00 00 00
    |   1
    |  --
 24 |   1 00		(100/20 ~= 5 ) (adjust to 4)
    |     96
    |   ----
281 |      4 00		(400/280 ~= 1)
    |      2 81
    |      ----
2824|      1 19 00	(11900/2820 ~= 4)
    |      1 12 96
    |      -------
28282|        6 04 00	(60400/28280 ~= 2)
     |        5 65 64

The above method can be generalized to nth roots but the
calculation is not simple beyond n=2. (Thanks to D.Bradley for this)
------
From dmbradley@poppy.waterloo.edu  Wed Aug 23 15:49:52 1989

Break up the number into digit-blocks of length n, starting at the decimal
point.  The first answer-digit a1 is obtained by minimizing r = d - a1^n over
the non-negative integers, where d is the leftmost digit-block. Put a = a1. 
Put e = r.
  
Loop until e==0 and no more non-zero digit-blocks to "bring down". 
    Put d = next digit-block to the right.
    Put r = e * 10^n + d.  "Bring down more digits and adjoin to remainder"
    To obtain the next answer-digit b, minimize the expression 
    e = r - ( ( 10 * a + b )^n - ( 10 * a )^n ) over the non-negative integers.
    Put a = a * 10 + b. 
    
Answer is a.

If the the number is not a perfect nth power, the algorithm never terminates,
but each iteration of the loop gives a another decimal place of accuracy.

Suppose you want cube_root( 30371328 ).
Split up the number like this: 30 371 328.000 000 000 
a1 = 3 minimizes 30 - a1^3.  So a = 3, e = r = 30 - 27 = 3.
 
Loop:
    d = 371, r = e * 1000 + 371 = 3371.
    b = 1 minimizes e = 3371 - (10*a + b)^3 + (10*a)^3 = 580.
    So a = 31, e = 580.

    d = 328, r = e * 1000 + 328 = 580328.
    b = 2 minimizes e = 580328 - (10*a +b)^3 + (10*a)^3 = 0.
    So a = 312, e = 0.
    Terminate with answer a = 312. 

Anthony
//// Anthony Scian afscian@violet.uwaterloo.ca afscian@violet.waterloo.edu ////
"I can't believe the news today, I can't close my eyes and make it go away" -U2