section_path: Computing principal roots/Using Newton's method
section_name: Using Newton's method
paragraph_text: Using Newton's method
  
  The n th root of a number A can be computed with Newton's method, which starts with an initial guess x and then iterates using the recurrence relation
  
  x k + 1 = x k − x k n − A n x k n − 1 {\displaystyle x_{k+1}=x_{k}-{\frac {x_{k}^{n}-A}{nx_{k}^{n-1}}}}
  
  until the desired precision is reached. For computational efficiency, the recurrence relation is commonly rewritten
  
  x k + 1 = n − 1 n x k + A n 1 x k n − 1. {\displaystyle x_{k+1}={\frac {n-1}{n}}\,x_{k}+{\frac {A}{n}}\,{\frac {1}{x_{k}^{n-1}}}.}
  
  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 n = 5, A = 34 and x = 2 (initial guess). The first 5 iterations are, approximately:
  
  (All correct digits shown.)
  
  The approximation x is accurate to 25 decimal places and x is good for 51.
  
  Newton's method can be modified to produce various generalized continued fractions for the n th root. For example,
  
  z n = x n + y n = x + y n x n − 1 + (n − 1) y 2 x + (n + 1) y 3 n x n − 1 + (2 n − 1) y 2 x + (2 n + 1) y 5 n x n − 1 + (3 n − 1) y 2 x + ⋱. {\displaystyle {\sqrt{z}}={\sqrt{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 }}}}}}}}}}}}.}