afscian@violet.waterloo.edu (Anthony Scian) (08/23/89)
I've tried to find a reference for this technique but I can't seem to find any but it is alluded to in Knuth Vol2. Does anybody remember the algorithm or any references? 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
afscian@violet.waterloo.edu (Anthony Scian) (08/24/89)
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
pfratar@watshine.waterloo.edu ( DCS) (08/25/89)
In article <16075@watdragon.waterloo.edu> afscian@violet.waterloo.edu (Anthony Scian) writes: >I've tried to find a reference for this technique but >I can't seem to find any but it is alluded to in Knuth Vol2. > >Does anybody remember the algorithm or any references? > >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 Hi, The method I am familiar with is simply, subtract consecutive odd numbers starting at 1 ( 1, 3, 5 ...) from the nuber you want to take the square root of and count the number of times you subtract. When you have a remainder you can use long division to divide the next odd number into the remainder to get an approximate decimal. The root is the number of times you subtract + any decimal from the long division. Example square root of 24 sub 1 23 sub 3 20 sub 5 15 sub 7 8 sub 9 nope 8.00000 / 9 = .88888... square root of 24 is 4.8888888... Paul F...... -- -------------------------------------------------------------------------- Paul Frattaroli - Department of Computing Services < pfratar@watshine.waterloo.edu > < pfratar@watdcsu.waterloo.edu > --------------------------------------------------------------------------
lhf@aries5.uucp (Luiz H. deFigueiredo) (08/25/89)
In article <491@watshine.waterloo.edu> pfratar@watshine.waterloo.edu (Paul Frattaroli - DCS) writes: > > The method I am familiar with is simply, subtract consecutive odd >numbers starting at 1 ( 1, 3, 5 ...) from the nuber you want to take the >square root of and count the number of times you subtract. When you have >a remainder you can use long division to divide the next odd number into >the remainder to get an approximate decimal. The root is the number of >times you subtract + any decimal from the long division. This works because n^2 = 1 + 3 + ... + (2n-1) ------------------------------------------------------------------------------- Luiz Henrique de Figueiredo internet: lhf@aries5.waterloo.edu Computer Systems Group bitnet: lhf@watcsg University of Waterloo (possible domains are waterloo.edu and uwaterloo.ca) -------------------------------------------------------------------------------
ksbooth@watcgl.waterloo.edu (Kelly Booth) (08/25/89)
In article <491@watshine.waterloo.edu> pfratar@watshine.waterloo.edu (Paul Frattaroli - DCS) writes: > The root is the number of >times you subtract + any decimal from the long division. This algorithm requires OMEGA( root n ) steps to find the square root and is analogous to division by successive subtraction (without shifts). The earlier algorithm requires OMEGA( log n ) steps and is analogous to the standard long division algorithm (subtraction with shifts). It is easy to derive this directly from the binomial theorem: Let sqrt(X) = 10a + b, then X = (10a + b)**2 = 100a**2 + 20ab + b**2 The first division step finds a, then the iterative step finds b (note that 20ab is twice a in the tens place plus b).