Path: utzoo!utgpu!watmath!watdragon!violet!afscian From: afscian@violet.waterloo.edu (Anthony Scian) Newsgroups: uw.general Subject: Re: Pencil & Paper Square root method (summary) Message-ID: <16080@watdragon.waterloo.edu> Date: 24 Aug 89 02:14:43 GMT References: <16075@watdragon.waterloo.edu> Sender: daemon@watdragon.waterloo.edu Reply-To: afscian@violet.waterloo.edu (Anthony Scian) Distribution: uw Organization: U. of Waterloo, Ontario Lines: 113 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