SICP Exercise 1.45: Damp Roots

We saw in section 1.3.3 that attempting to compute square roots by naively finding a fixed point of y→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→x/y². Unfortunately, the process does not work for fourth roots -- a single average damp is not enough to make a fixed-point search for y→x/y³ converge. On the other hand, if we average damp twice (i.e., use the average damp of the average damp of y→x/y³) 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→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.

First of all we know that the n^th root of x can be calculated as the fixed point of the equation y→x/y^n-1, so let's define a procedure that generates the equivalent lambda expression:

(define (nth-root-function x n)
  (lambda (y) (/ x (expt y (- n 1)))))

And then we can produce some test code for figuring how many average damps we need for a particular root. To do this we want to apply average-damp some number of times to the appropriate nth-root-function expression, and then use that to try to calculate a fixed point. If we're not doing enough average damping then the algorithm will never converge and the interpreter will hang. Here's the test code:

(define (damped-nth-root x n a)
  (if (= a 0)
      (nth-root-function x n)
      ((repeated average-damp a) (nth-root-function x n))))

(define (test-nth-root-damping x n a)
  (fixed-point (damped-nth-root x n a) 1.0))

When we start experimenting with this we quickly find a pattern:

n	2 - 3	4 - 7	8 - 15	16 - 31	32 - 63
Required Average Damps	1	2	3	4	5

Note how the required average damps increases by one each time n reaches the next power of 2. In other words, we want to average damp ⌊log₂n⌋ times.

Now let's define a procedure that does this:

(define (nth-root x n)
  (let ((damps (floor (/ (log n) (log 2)))))
    (fixed-point (damped-nth-root x n damps) 1.0)))

And we can check it works:

> (nth-root 4 2)
2.000000000000002
> (nth-root 4 4)
1.414213562373095
> (nth-root 4 8)
1.1892071150032364
> (nth-root 4 16)
1.0905077327148582
> (nth-root 4 32)
1.0442737827236872
> (nth-root 4 64)
1.0218971491473008
> (nth-root 4 128)
1.0108892864974073
> (nth-root 4 256)
1.0054299014117003
> (nth-root 4 512)
1.002711275223178
> (nth-root 4 1024)
1.001354719985141
> (nth-root 4 2048)
1.000677130741309
> (nth-root 4 4096)
1.0003386176117304