Ch1.3.3 The n-th Root Algorithm

• The n-th root of a number \( x \) is

  \[ \sqrt[\leftroot{-1}\uproot{3}n]{x} = x^{1/n} \]

• Examples

• \( x = 9, \,\, n = 2: \,\,\sqrt{9} = 9^{1/2} = 3 \)

• \( x = 8, \,\, n = 3: \,\, \sqrt[\leftroot{-1}\uproot{3}3]{8} = 8^{1/3} = 2 \)

\[ \begin{align*} x_{n+1} & = \frac{x_n}{2} + \frac{1}{x_n} \\ x_0 & = 1\\ x_1 & = \frac{x_0}{2} + \frac{1}{x_0} = 1.5 \\ x_2 & = \frac{x_1}{2} + \frac{1}{x_1} = 1.4167 \\ & \vdots \\ x &= 1.414213...\\ \end{align*} \]

• To find \( \sqrt[\leftroot{-1}\uproot{3}n]{a} \):

\[ \begin{align*} x_0 & = 1\\ x_{k+1} & = \frac{1}{n}\left[ x_k*(n-1) + \frac{a}{x_k^{n-1}} \right] \end{align*} \]

• For \( a = 2, \,\, n = 2 \):

\[ x_{k+1} = \frac{1}{2}\left( x_k + \frac{2}{x_k} \right) \]

• The n-th root algorithm is iterative
• The loop computes a value of interest
• That value is then plugged back into loop
• The result becomes progressively better

\[ \begin{align*} x_0 & = 1\\ x_{k+1} & = \frac{1}{n}\left[ x_k*(n-1) + \frac{a}{x_k^{n-1}} \right] \end{align*} \]

\[ \begin{align*} x_0 & = 1\\ x_{k+1} & = \frac{1}{n}\left[ x_k*(n-1) + \frac{a}{x_k^{n-1}} \right]\\ & = x_k + \frac{1}{n}\left(\frac{a}{x_k^{n-1}} - x_k\right) \\ & = x_k + \Delta x_k \end{align*} \]

deltax <- (1/n)*(a/x^(n-1) - x)
x <- x + deltax

nthroot <- function (a, n, tol = 1/1000) {
  x <- 1
  deltax <- tol * 10

  while (abs( deltax ) > tol) {
    deltax <- (1/n)*(a/x^(n-1) - x)
    x <- x + deltax }
  return (x)
}

\[ \begin{align*} x_{k+1} & = x_k + \frac{1}{n}\left(\frac{a}{x_k^{n-1}} - x_k\right) \\ & = x_k + \Delta x_k \end{align*} \]

nthroot <- function (a, n, tol = 1/1000) {
  x <- 1
  deltax <- tol * 10

  while (abs( deltax ) > tol) {
    deltax <- (1/n)*(a/x^(n-1) - x)
    x <- x + deltax }
  return (x)
}

nthroot(10,2)

[1] 3.162278

nthroot2 <- function (a, n, tol = 1/1000) {
  x <- 1
  deltax <- tol * 10
  iter <- 0
  cat("n = ", iter,",", "x(n) = ", x, "\n")
  while (abs( deltax ) > tol) {
    deltax <- (1/n)*(a/x^(n-1) - x)
    x <- x + deltax
    iter <- iter + 1 
    cat("n = ", iter,",", "x(n) = ", x, "\n") }
  return (x)
}

nthroot2(10,2)

n =  0 , x(n) =  1 
n =  1 , x(n) =  5.5 
n =  2 , x(n) =  3.659091 
n =  3 , x(n) =  3.196005 
n =  4 , x(n) =  3.162456 
n =  5 , x(n) =  3.162278 

[1] 3.162278

\[ \begin{align*} x_0 & = 1, \,\, n = 2, \,\, a = 10 \\ x_{k+1} & = x_k + \frac{1}{n}\left(\frac{a}{x_k^{n-1}} - x_k\right) \end{align*} \]

nthroot2(100,2)

n =  0 , x(n) =  1 
n =  1 , x(n) =  50.5 
n =  2 , x(n) =  26.2401 
n =  3 , x(n) =  15.02553 
n =  4 , x(n) =  10.84043 
n =  5 , x(n) =  10.03258 
n =  6 , x(n) =  10.00005 
n =  7 , x(n) =  10 

[1] 10

nthroot2(21,3)

n =  0 , x(n) =  1 
n =  1 , x(n) =  7.666667 
n =  2 , x(n) =  5.230204 
n =  3 , x(n) =  3.742697 
n =  4 , x(n) =  2.994854 
n =  5 , x(n) =  2.777022 
n =  6 , x(n) =  2.759042 
n =  7 , x(n) =  2.758924 

[1] 2.758924

21^(1/3)

[1] 2.758924

nthroot2(pi,2)

n =  0 , x(n) =  1 
n =  1 , x(n) =  2.070796 
n =  2 , x(n) =  1.793945 
n =  3 , x(n) =  1.772583 
n =  4 , x(n) =  1.772454 

[1] 1.772454

sqrt(pi)

[1] 1.772454

nthroot <- function (a, n, tol = 1/1000) {
  x <- 1
  deltax <- tol * 10

  while (abs( deltax ) > tol) {
    deltax <- (1/n)*(a/x^(n-1) - x)
    x <- x + deltax }
  return (x)
}

\[ \begin{align*} x_{k+1} & = x_k + \frac{1}{n}\left(\frac{a}{x_k^{n-1}} - x_k\right) \\ & = x_k + \Delta x_k \end{align*} \]