Shifting nth root algorithm

The written root extraction is a method for calculating the square root of a natural number which can be carried out without a computer. It is similar to the long division and supplies at each computational step, a place of the result. Basis of the written finding roots are the binomial.

At school the written root extraction is barely taught today, even in earlier times it was seldom applied. The reasons are, firstly, the lower practical significance of the roots is in contrast to the basic arithmetic operations, on the other iterative methods such as the Heron procedures are to be performed ( Babylonian square root ) easier and faster usually supply a sufficient accuracy.

To draw the cube root in writing, is also possible. This even more rarely used method is an extension of the principle which is applied for extracting the square root.

Method

The radicand is first divided by the right in groups of two points. The front (one or two digit ) group provides the first digit of the result by the largest single-digit number is searched whose square is not greater than this number. The square is subtracted from the leading group, the difference is written in the next line and supplemented with the next group of two of the radicand.

To determine the next ( and each other ) place the first binomial formula is used:. b is the required next space, a is the result so far, to provide equitable representation with an appended zero. a ² was subtracted already by the previous steps from the cube root to append to the result of the point b may now have to be subtracted 2ab and b ² limbs.

The above- determined number is so divided by 2, the result is b, the rest must, however, be smaller than b ². After subtracting 2ab and b ² the next group of two of the radicand is consulted and the next calculation step in the same way. Ends the process is either when the radicand could be reduced by the repeated subtractions to zero ( then the radicand a perfect square ) or the result of having a sufficient accuracy ( decimal places than can the radicand as many zeros are appended ).

Representation means of a concrete example

It is the root are determined from 2916:

As a first step, the sequence of digits in the number is broken down into two groups namely starting from the decimal point. Missing a comma ( as in this example), then the starting point is the number that is right outside.

______ √ 29 16 =? The largest perfect square that fits in 29 's. The first digit of the result is thus 5 29-25 = 4 to the number 4 Add to that the rear two digits 16 and therefore receives 416:

______ √ 29 16 = 5   -25     4 16 To get the second digit of the result ( b ), you must now by (here ) share, with a sufficient rest must be 416 /100 = 4 remainder 16 The rest 16 corresponds to 4 ², so the calculation goes to zero, since 2916 a square number.

______ √ 29 16 = 54   -25    __     4 16    -4 00    - 16     ____        0 Similar to the written dividing the set justice indented representation is used to focus the calculation on the currently relevant points here.

By the rising of the bill can be found out without a trial account whether the cube root was actually a square number, iterative methods, however, still provide only an approximation in this method.

The Heron method is applied to the example of 2916 provides for choice of 50 as the starting value after two iterations of the approximation.

In the election of 2916 as the start value, however, about ten computation steps must be performed for a similar result.

The same procedure as grandmother knew ( square root of 2538413.6976 ):

Examples

Square root of 2 binary

1 0 1 1 0 1      ------------------     / 10:00 00 00 00 00 1 / \ / 1 1       ---------        1 00 100           0 0       -------------        1 00 00 1001          10 01 1       -----------------           1 11 00 10 101           1 01 01 1           -----------------              1 11 00 101100                    0 0              ------------------              1 11 00 00 1011001              1 01 10 01 1              ----------                 1 01 11 remaining Square root of 3

1 7 3 2 0 5      ----------------------     / 3.00 00 00 00 00 / \ / 1 = 20 * 0 * 1 1 ^ 2       -       2 00       1 89 = 20 * 1 * 7 7 ^ 2       ----         11 00         10 29 = 20 * 17 * 3 3 ^ 2         -----            71 00            69 24 = 20 * 173 * 2 2 ^ 2            -----             1 76 00                   0 = 20 * 1732 * 0 0 ^ 2             -------             1 76 00 00             1 73 20 25 = 20 * 17320 * 5 5 ^ 2             ----------                2 79 75 Cube root of 5

1 7 0 9 9 7      ----------------------    3/ 5000 000 000 000 000 / \ / 1 = 300 * (0 ^ 2 ) * 1 30 * 0 * (1 ^ 2) ^ 3 1       -       4000       3913 = 300 * (1 ^ 2) * 7 30 * 1 * (7 ^ 2) 7 ^ 3       -----          87 000               0 = 300 * (17 ^ 2) * 0 30 * 17 * (0 ^ 2) ^ 3 0         -------          87 million          78,443,829 = 300 * (170 ^ 2) * 9 30 * 170 * (9 ^ 2) ^ 3 9          ----------           8.556171 billion           7889992299 = 300 * (1709 ^ 2) * 9 30 * 1709 * (9 ^ 2) ^ 3 9           -------------             666 178 701 000             614 014 317 973 = 300 * ( 17099 ^ 2) * 7 30 * 17099 * (7 ^ 2) 7 ^ 3             ---------------              52,164,383,027 Fourth root of 7

1 6 2 6 5 7      ---------------------------    4/ 7 / \ / -       6 0000       5 5536 = 4000 * (1 ^ 3 ) * 6 600 * (1 ^ 2 ) * ( 6 ^ 2) 40 * 1 * (6 ^ 3 ) ^ 4 6       ------         4464 0000         3338 7536 = 4000 * (16 ^ 3 ) * 2 600 * (16 ^ 2 ) * ( 2 ^ 2) 40 * 16 * ( 2 ^ 3 ) ^ 4 2         ---------         1125 2464 0000         1026 0494 3376 = 4000 * (162 ^ 3 ) * 6 600 * (162 ^ 2 ) * ( 6 ^ 2) 40 * 162 * (6 ^ 3 ) ^ 4 6         --------------           99 1969 6624 0000           86 0185 1379 0625 = 4000 * ( 1626 ^ 3 ) * 5 600 * ( 1626 ^ 2 ) * ( 5 ^ 2 )           ----------------- 40 * 1626 * (5 ^ 3 ) ^ 4 5           13 1784 5244 9375 0000           12 0489 2414 6927 3201 = 4000 * ( 16265 ^ 3 ) * 7 600 * ( 16265 ^ 2 ) * ( 7 ^ 2 )           ---------------------- 40 * 16265 * (7 ^ 3 ) ^ 4 7            1 1295 2830 2447 6799 Web Links

• Web archive of June 08, 2001, the intercalated Website: The written drawing of cube roots
• Written square root Detailed explanation of the roots is written
• Detailed explanation of the algorithm with online generator

• Root ( mathematics)