SICP Exercise 1.45

Question

We saw in 1.3.3 that attempting to compute square roots by naively finding a fixed point of \(y\mapsto x/y\) does not converge, and that this can be fixed by average damping. The same method works for finding cube roots as fixed points of the average-damped \(y\mapsto x/y^2\).

Unfortunately, the process does not work for fourth roots—a single average damp is not enough to make a fixed-point search for \(y\mapsto x/y^3\) converge. On the other hand, if we average damp twice (i.e., use the average damp of the average damp of \(y\mapsto x/y^3\)) the fixed-point search does converge.

Do some experiments to determine how many average damps are required to compute $n$-th roots as a fixed-point search based upon repeated average damping of \(y\mapsto x/y^{n-1}\). Use this to implement a simple procedure for computing $n$-th roots using fixed-point, average-damp, and the repeated procedure of exercise 1.43. Assume that any arithmetic operations you need are available as primitives.

Answer

(define (compose f g)
  (λ (x) (f (g x))))

(define (repeated f n)
  (if (= n 1)
      (λ (x) (f x))
      (repeated (compose f f) (- n 1))))

(define (average x y)
  (/ (+ x y) 2))

(define (average-damp f)
  (λ (x) (average x (f x))))

(define tolerance 0.00000001)

(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

(define (calc-root x n num-avg-damp)
  (display n) (display ": ")
  (fixed-point ((repeated average-damp num-avg-damp) (λ (y) (/ x (expt y (- n 1))))) 1.0))

(calc-root 4 2 1)
(calc-root 16 4 2)
(calc-root 256 8 3)
(calc-root 4294967296 32 4)
(calc-root 4294967296 512 5)
(calc-root 4294967296 1000000 5)

Results:

2: 2.0
4: 2.0
8: 2.0000000086140393
32: 2. 0000000691617332
512: 1.04427505183215
1000000: 1.00002P21886712453

By average-damping 5 times, you can compute the $n$-th root of a number for pretty much any \(n\) that you will ever need. Beyond this, the numbers get so large that computing power becomes a bottleneck and it becomes impossible to tell whether the calculation converges or not (at least on my system. Maybe you have a supercomputer in your basement and can verify this for me).