Editing Nth root (section)

==Computing principal roots==

===Using Newton's method===

The {{mvar|n}}th root of a number {{math|''A''}} can be computed with [[Newton's method]], which starts with an initial guess {{math|''x''<sub>0</sub>}} and then iterates using the [[recurrence relation]]

<math display="block">x_{k+1} = x_k-\frac{x_k^n-A}{nx_k^{n-1}}</math>

until the desired precision is reached. For computational efficiency, the recurrence relation is commonly rewritten 

<math display="block">x_{k+1} = \frac{n-1}{n}\,x_k+\frac{A}{n}\,\frac 1{x_k^{n-1}}.</math>

This allows to have only one [[exponentiation]], and to compute once for all the first factor of each term.

For example, to find the fifth root of 34, we plug in {{math|1=''n'' = 5, ''A'' = 34}} and {{math|1=''x''<sub>0</sub> = 2}} (initial guess). The first 5 iterations are, approximately:

{{block indent|{{math|1=''x''<sub>0</sub> = 2}}}}
{{block indent|{{math|1=''x''<sub>1</sub> = 2.025}}}}
{{block indent|{{math|1=''x''<sub>2</sub> = 2.02439 7...}}}}
{{block indent|{{math|1=''x''<sub>3</sub> = 2.02439 7458...}}}}
{{block indent|{{math|1=''x''<sub>4</sub> = 2.02439 74584 99885 04251 08172...}}}}
{{block indent|{{math|1=''x''<sub>5</sub> = 2.02439 74584 99885 04251 08172 45541 93741 91146 21701 07311 8...}}}}

(All correct digits shown.)

The approximation {{math|''x''<sub>4</sub>}} is accurate to 25 decimal places and {{math|''x''<sub>5</sub>}} is good for 51.

Newton's method can be modified to produce various [[generalized continued fraction#Roots of positive numbers|generalized continued fractions]] for the ''n''th root. For example,

<math display="block">
  \sqrt[n]{z} = \sqrt[n]{x^n+y} = x+\cfrac{y} {nx^{n-1}+\cfrac{(n-1)y} {2x+\cfrac{(n+1)y} {3nx^{n-1}+\cfrac{(2n-1)y} {2x+\cfrac{(2n+1)y} {5nx^{n-1}+\cfrac{(3n-1)y} {2x+\ddots}}}}}}.
</math>

=== Digit-by-digit calculation of principal roots of decimal (base 10) numbers ===
[[Image:PascalForDecimalRoots.svg|right|thumb|[[Pascal's triangle]] showing <math>P(4,1) = 4</math>.]]
Building on the [[Methods of computing square roots#Decimal (base 10)|digit-by-digit calculation of a square root]], it can be seen that the formula used there, <math>x(20p + x) \le c</math>, or <math>x^2 + 20xp \le c</math>, follows a pattern involving Pascal's triangle.  For the ''n''th root of a number <math>P(n,i)</math> is defined as the value of element <math>i</math> in row <math>n</math> of Pascal's Triangle such that <math>P(4,1) = 4</math>, we can rewrite the expression as <math>\sum_{i=0}^{n-1}10^i P(n,i)p^i x^{n-i}</math>.  For convenience, call the result of this expression <math>y</math>.  Using this more general expression, any positive principal root can be computed, digit-by-digit, as follows.

Write the original number in decimal form. The numbers are written similar to the [[long division]] algorithm, and, as in long division, the root will be written on the line above. Now separate the digits into groups of digits equating to the root being taken, starting from the decimal point and going both left and right. The decimal point of the root will be above the decimal point of the radicand. One digit of the root will appear above each group of digits of the original number.

Beginning with the left-most group of digits, do the following procedure for each group:

# Starting on the left, bring down the most significant (leftmost) group of digits not yet used (if all the digits have been used, write "0" the number of times required to make a group) and write them to the right of the remainder from the previous step (on the first step, there will be no remainder). In other words, multiply the remainder by <math>10^n</math> and add the digits from the next group. This will be the '''current value ''c'''''.
# Find ''p'' and ''x'', as follows:
#* Let <math>p</math> be the '''part of the root found so far''', ignoring any decimal point. (For the first step, <math>p = 0</math> and <math>0^0 = 1</math>).
#* Determine the greatest digit <math>x</math> such that <math>y \le c</math>.
#* Place the digit <math>x</math> as the next digit of the root, i.e., above the group of digits you just brought down. Thus the next ''p'' will be the old ''p'' times 10 plus ''x''.
# Subtract <math>y</math> from <math>c</math> to form a new remainder.
# If the remainder is zero and there are no more digits to bring down, then the algorithm has terminated. Otherwise go back to step 1 for another iteration.

====Examples====
{{MOS|section|date=April 2022}}

'''Find the square root of 152.2756.'''

         <u>  1  2. 3  4 </u>
     <u> </u>  /
      \/  01 52.27 56          (Results)    (Explanations)
    &nbsp;
          01                   x = 1        10{{sup|0}}·1·0{{sup|0}}·'''1'''{{sup|2}} + 10{{sup|1}}·2·0{{sup|1}}·'''1'''{{sup|1}}     ≤      1   <   10{{sup|0}}·1·0{{sup|0}}·2{{sup|2}}   + 10{{sup|1}}·2·0{{sup|1}}·2{{sup|1}}
         <u> 01 </u>                  y = 1        y = 10{{sup|0}}·1·0{{sup|0}}·1{{sup|2}}   + 10{{sup|1}}·2·0{{sup|1}}·1{{sup|1}}   =  1 +    0   =     '''1'''
          00 52                x = 2        10{{sup|0}}·1·1{{sup|0}}·'''2'''{{sup|2}} + 10{{sup|1}}·2·1{{sup|1}}·'''2'''{{sup|1}}     ≤     52   <   10{{sup|0}}·1·1{{sup|0}}·3{{sup|2}}   + 10{{sup|1}}·2·1{{sup|1}}·3{{sup|1}}
         <u> 00 44 </u>               y = 44       y = 10{{sup|0}}·1·1{{sup|0}}·2{{sup|2}}   + 10{{sup|1}}·2·1{{sup|1}}·2{{sup|1}}   =  4 +   40   =    '''44'''
             08 27             x = 3        10{{sup|0}}·1·12{{sup|0}}·'''3'''{{sup|2}} + 10{{sup|1}}·2·12{{sup|1}}·'''3'''{{sup|1}}   ≤    827   <   10{{sup|0}}·1·12{{sup|0}}·4{{sup|2}}  + 10{{sup|1}}·2·12{{sup|1}}·4{{sup|1}}
            <u> 07 29 </u>            y = 729      y = 10{{sup|0}}·1·12{{sup|0}}·3{{sup|2}}  + 10{{sup|1}}·2·12{{sup|1}}·3{{sup|1}}  =  9 +  720   =   '''729'''
                98 56          x = 4        10{{sup|0}}·1·123{{sup|0}}·'''4'''{{sup|2}} + 10{{sup|1}}·2·123{{sup|1}}·'''4'''{{sup|1}} ≤   9856   <   10{{sup|0}}·1·123{{sup|0}}·5{{sup|2}} + 10{{sup|1}}·2·123{{sup|1}}·5{{sup|1}}
               <u> 98 56 </u>         y = 9856     y = 10{{sup|0}}·1·123{{sup|0}}·4{{sup|2}} + 10{{sup|1}}·2·123{{sup|1}}·4{{sup|1}} = 16 + 9840   =  '''9856'''
                00 00

Algorithm terminates: Answer is 12.34

'''Find the cube root of 4192 truncated to the nearest thousandth.'''

      <u>   1   6.  1   2   4</u>
  <u>3</u>  /
   \/  004 192.000 000 000          (Results)    (Explanations)
    &nbsp;
       004                          x = 1        10{{sup|0}}·1·0{{sup|0}}·'''1'''{{sup|3}}    +  10{{sup|1}}·3·0{{sup|1}}·'''1'''{{sup|2}}   + 10{{sup|2}}·3·0{{sup|2}}·'''1'''{{sup|1}}    ≤          4  <  10{{sup|0}}·1·0{{sup|0}}·2{{sup|3}}     + 10{{sup|1}}·3·0{{sup|1}}·2{{sup|2}}    + 10{{sup|2}}·3·0{{sup|2}}·2{{sup|1}}
      <u> 001 </u>                         y = 1        y = 10{{sup|0}}·1·0{{sup|0}}·1{{sup|3}}   + 10{{sup|1}}·3·0{{sup|1}}·1{{sup|2}}   + 10{{sup|2}}·3·0{{sup|2}}·1{{sup|1}}   =   1 +      0 +          0   =          '''1'''
       003 192                      x = 6        10{{sup|0}}·1·1{{sup|0}}·'''6'''{{sup|3}}    +  10{{sup|1}}·3·1{{sup|1}}·'''6'''{{sup|2}}   + 10{{sup|2}}·3·1{{sup|2}}·'''6'''{{sup|1}}    ≤       3192  <  10{{sup|0}}·1·1{{sup|0}}·7{{sup|3}}     + 10{{sup|1}}·3·1{{sup|1}}·7{{sup|2}}    + 10{{sup|2}}·3·1{{sup|2}}·7{{sup|1}}
      <u> 003 096 </u>                     y = 3096     y = 10{{sup|0}}·1·1{{sup|0}}·6{{sup|3}}   + 10{{sup|1}}·3·1{{sup|1}}·6{{sup|2}}   + 10{{sup|2}}·3·1{{sup|2}}·6{{sup|1}}   = 216 +  1,080 +      1,800   =      '''3,096'''
           096 000                  x = 1        10{{sup|0}}·1·16{{sup|0}}·'''1'''{{sup|3}}   + 10{{sup|1}}·3·16{{sup|1}}·'''1'''{{sup|2}}   + 10{{sup|2}}·3·16{{sup|2}}·'''1'''{{sup|1}}   ≤      96000  <  10{{sup|0}}·1·16{{sup|0}}·2{{sup|3}}   + 10{{sup|1}}·3·16{{sup|1}}·2{{sup|2}}   + 10{{sup|2}}·3·16{{sup|2}}·2{{sup|1}}
          <u> 077 281 </u>                 y = 77281    y = 10{{sup|0}}·1·16{{sup|0}}·1{{sup|3}}  + 10{{sup|1}}·3·16{{sup|1}}·1{{sup|2}}  + 10{{sup|2}}·3·16{{sup|2}}·1{{sup|1}}  =   1 +    480 +     76,800   =     '''77,281'''
           018 719 000              x = 2        10{{sup|0}}·1·161{{sup|0}}·'''2'''{{sup|3}}  + 10{{sup|1}}·3·161{{sup|1}}·'''2'''{{sup|2}}  + 10{{sup|2}}·3·161{{sup|2}}·'''2'''{{sup|1}}  ≤   18719000  <  10{{sup|0}}·1·161{{sup|0}}·3{{sup|3}}  + 10{{sup|1}}·3·161{{sup|1}}·3{{sup|2}}  + 10{{sup|2}}·3·161{{sup|2}}·3{{sup|1}}
              <u> 015 571 928 </u>         y = 15571928 y = 10{{sup|0}}·1·161{{sup|0}}·2{{sup|3}} + 10{{sup|1}}·3·161{{sup|1}}·2{{sup|2}} + 10{{sup|2}}·3·161{{sup|2}}·2{{sup|1}} =   8 + 19,320 + 15,552,600   = '''15,571,928'''
               003 147 072 000      x = 4        10{{sup|0}}·1·1612{{sup|0}}·'''4'''{{sup|3}} + 10{{sup|1}}·3·1612{{sup|1}}·'''4'''{{sup|2}} + 10{{sup|2}}·3·1612{{sup|2}}·'''4'''{{sup|1}} ≤ 3147072000  <  10{{sup|0}}·1·1612{{sup|0}}·5{{sup|3}} + 10{{sup|1}}·3·1612{{sup|1}}·5{{sup|2}} + 10{{sup|2}}·3·1612{{sup|2}}·5{{sup|1}}

The desired precision is achieved. The cube root of 4192 is 16.124...

===Logarithmic calculation===

The principal ''n''th root of a positive number can be computed using [[logarithm]]s. Starting from the equation that defines ''r'' as an ''n''th root of ''x'', namely <math>r^n=x,</math> with ''x'' positive and therefore its principal root ''r'' also positive, one takes logarithms of both sides (any [[logarithm#Particular bases|base of the logarithm]] will do) to obtain

<math display="block">n \log_b r = \log_b x \quad \quad \text{hence} \quad \quad \log_b r = \frac{\log_b x}{n}.</math>

The root ''r'' is recovered from this by taking the [[antilog]]:

<math display="block">r = b^{\frac{1}{n}\log_b x}.</math>

(Note: That formula shows ''b'' raised to the power of the result of the division, not ''b'' multiplied by the result of the division.)

For the case in which ''x'' is negative and ''n'' is odd, there is one real root ''r'' which is also negative. This can be found by first multiplying both sides of the defining equation by −1 to obtain <math>|r|^n = |x|,</math> then proceeding as before to find |''r''|, and using {{nowrap|''r'' {{=}} −{{!}}''r''{{!}}}}.