SICP exercise 1.45

From Drewiki

Problem

We saw in section 1.3.3 of the text that attempting to compute square roots by naively finding a fixed point of 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 . Unfortunately, the process does not work for fourth roots -- a single average damp is not enough to make a fixed-point search for converge. On the other hand, if we average damp twice (i.e., use the average damp of the average damp of ) the fixed-point search does converge. Do some experiments to determine how many average damps are required to compute nth roots as a fixed-point search based upon repeated average damping of . Use this to implement a simple procedure for computing nth 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.

Solution

Here are the average-damp and fixed-point procedures from text:

(define (average x y) (/ (+ x y) 2))
 
(define (average-damp f)
  (lambda (x) (average x (f x))))
 
(define tolerance 0.00001)
 
(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 (fixed-point-of-transform g transform guess)
  (fixed-point (transform g) guess))

Here are procedures to calculate square and cube root using a single average damp:

(define (sqrt x)
  (fixed-point-of-transform (lambda (y) (/ x y))
                            average-damp
                            1.0))
 
(define (square x) (* x x))
 
(define (cube-root x)
  (fixed-point-of-transform (lambda (y) (/ x (square y)))
                            average-damp
                            1.0))

As indicated in the text, we need two applications of average damping for fourth roots. Let's use the procedures from the solution to exercise 1.43:

(define (compose f g)
  (lambda (x) (f (g x))))
 
(define (inc x) (+ x 1))
 
(define (repeated f n)
  (define (repeated-iter i result)
    (if (= i n)
        result
        (repeated-iter (inc i) (compose f result))))
  (repeated-iter 1 f))
 
(define (cube x) (* x x x))
 
(define (fourth-root x)
  (fixed-point-of-transform (lambda (y) (/ x (cube y)))
                            (repeated average-damp 2)
                            1.0))

Test it (results shown are from Chicken Scheme 3.1 on a MacBook Pro running Mac OS X 10.5):

(fourth-root 16)

Output:

2.0000000000022

(fourth-root (* 3 3 3 3))

Output:

3.00000000000003

(fourth-root (* 7 7 7 7))

Output:

7.0

Are two average damps sufficient for 5th roots? Let's try, but first we'll define an exponentiation procedure (let's use the one from the solution to exercise 1.16):

(define (fast-expt b n)
  (fast-expt-iter b n 1))
 
(define (fast-expt-iter b n a)
  (cond ((= n 0) a)
        ((even? n) (fast-expt-iter (square b) (/ n 2) a))
        (else (fast-expt-iter b (- n 1) (* a b)))))
 
(define (fifth-root x)
  (fixed-point-of-transform (lambda (y) (/ x (fast-expt y 4)))
                            (repeated average-damp 2)
                            1.0))

Test:

(fifth-root (* 2 2 2 2 2))

Output:

2.00000151299576

(fifth-root (* 3 3 3 3 3))

Output:

3.00000088774963

(fifth-root (* 20 20 20 20 20))

Output:

20.000000551502

Looks good. What about 6th roots?

(define (sixth-root x)
  (fixed-point-of-transform (lambda (y) (/ x (fast-expt y 5)))
                            (repeated average-damp 2)
                            1.0))

Test:

(sixth-root (* 2 2 2 2 2 2))

Output:

2.00000293346621

(sixth-root (* 20 20 20 20 20 20))

Output:

20.0000029326938

Also looks good. In fact, it works for 7th roots, too... but not for 8th roots. If you try to find 8th roots using this method with only two applications of average-damp, your calculation will not converge. (If you do attempt this calculation, be prepared to interrupt or kill the process running the calculation!)

However, 3 average damps for 8th roots works fine.

(define (eighth-root x)
  (fixed-point-of-transform (lambda (y) (/ x (fast-expt y 7)))
                            (repeated average-damp 3)
                            1.0))

Test:

(eighth-root (fast-expt 2 8))

Output:

2.00000000000397

(eighth-root (fast-expt 7 8))

Output:

7.0

Looking at the results, we can begin to see a pattern emerging: 1 average damp works for up to 3rd roots, 2 are required for 4th through 7th roots, and 3 are required for 8th roots. 4 is 2² and 8 is 2³, so it looks like we need floor(log₂(n)) average damps to find nth roots, where floor is defined as the function that returns the integer part of a real number.

We can test this hypothesis by defining 15th-roots, which should require only 3 average damps if our theory is correct:

(define (fifteenth-root x)
  (fixed-point-of-transform (lambda (y) (/ x (fast-expt y 14)))
                            (repeated average-damp 3)
                            1.0))

Test:

(fifteenth-root (fast-expt 2 15))

Output:

2.0000040951543

(fifteenth-root (fast-expt 7 15))

Output:

7.00000459175445

That works. And if we tried to define the procedure sixteenth-root using only 3 average damp applications, we'd find that it would not converge; but it does work with 4 average damps:

(define (sixteenth-root x)
  (fixed-point-of-transform (lambda (y) (/ x (fast-expt y 15)))
                            (repeated average-damp 4)
                            1.0))

Test:

(sixteenth-root (fast-expt 2 16))

Output:

2.00000000007696

(sixteenth-root (fast-expt 8 16))

Output:

8.0

In order to do this procedurally, we need to calculate floor(log₂(n)). It turns out that we can implement it by performing successive arithmetic right shifts (each is equivalent to dividing by 2) and counting the number of shifts required to reach zero starting from n, and then subtracting one. Many Scheme implementations implement the arithmetic-shift primitive; in the combination shown below, arithmetic-shift's 2nd argument -1 tells the procedure to shift right by one bit:

(define (floor-log2 n)
  (define (iter m count)
    (if (= m 0)
        (- count 1)
        (iter (arithmetic-shift m -1) (inc count))))
  (iter n 0))

Tests:

(floor-log2 1)

Output:

0

(floor-log2 2)

Output:

1

(floor-log2 3)

Output:

1

(floor-log2 4)

Output:

2

(floor-log2 7)

Output:

2

(floor-log2 8)

Output:

3

Those are all correct values. Now we can implement the procedure requested by the exercise, namely, one that finds nth roots by fixed point searches and average damping:

(define (nth-root x n)
  (let ((number-of-damps (floor-log2 n)))
    (fixed-point-of-transform (lambda (y) (/ x (fast-expt y (- n 1))))
                              (repeated average-damp number-of-damps)
                              1.0)))

Finally, a few tests:

(nth-root (fast-expt 2 8) 8)

Output:

2.00000000000397

(nth-root (fast-expt 9 13) 13)

Output:

8.999997309254

(nth-root (fast-expt 8 17) 17)

Output:

8.00000009324061