sicp-ex-1.45

QUESTION

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^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 ↦ 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 ↦ x/y^3) 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 y ↦ x/y^{n − 1}. 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.

ANSWER

 (import (scheme small)) 
  
  
 (define (nth-root x n) 
   (define (fixed-point f first-guess) 
     (define (try guess) 
       (let ((next (f guess))) 
         (if (close-enough? guess next) 
           guess 
           (try next)))) 
     (define (close-enough? x y) 
       (< (abs (- x y)) 0.00001)) 
     (try first-guess)) 
   (define (average-damp f) 
     (lambda (x) (/ (+ x (f x)) 2))) 
   (define (repeated f n) 
     (define (compose f g) 
       (lambda (x) (f (g x)))) 
     (if (= n 1) 
       f 
       (compose f (repeated f (- n 1))))) 
   (fixed-point 
     ((repeated average-damp (floor (log n 2))) 
       (lambda (y) (/ x (expt y (- n 1))))) 
     1.0)) 
  
  
 ; Average damping of y ↦ x/y^{n − 1} must be repeated ⌊log_2(n)⌋ times to compute nth roots of x as a fixed-point search. 
  
 (display (nth-root 2.0 2)) 
 (newline) 
 (display (nth-root 2.0 3)) 
 (newline) 
 (display (nth-root 2.0 4)) 
 (newline) 
 (display (nth-root 2.0 5)) 
 (newline) 
 (display (nth-root 2.0 6)) 
 (newline) 
 (display (nth-root 2.0 7)) 
 (newline) 
 (display (nth-root 2.0 8)) 
 (newline) 

I think the above number of average damps required to compute nth root is wrong.

 (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 (average a b) 
   (/ (+ a b) 2)) 
  
 (define (average-damp f) 
   (lambda (x) (average x (f x)))) 
  
 (define (square x) 
   (* x x)) 
  
 (define (fast-expt b n) 
   (cond ((= n 0) 1) 
         ((even? n) (square (fast-expt b (/ n 2)))) 
         (else (* b (fast-expt b (- n 1)))))) 
  
 (define (compose f g) 
   (lambda (x) 
     (g (f x)))) 
  
 (define (repeated f n) 
   (if (> n 1) 
     (compose (repeated f (- n 1)) f) 
     f)) 
  
 ;; avarage-damp d times 
 (define (nth-root x n d) 
   (fixed-point ((repeated average-damp d)  
                 (lambda (y) (/ x (fast-expt y (- n 1))))) 
                1.0)) 
  
 ;; Experimental results from 2rd to 20th root: 
 ;; Root  Required Average Damps 
 ;; 2     1 
 ;; 3     1 
 ;; 4     2 
 ;; 5     2 
 ;; 6     1 
 ;; 7     1 
 ;; 8     1 
 ;; 9     1 
 ;; 10    1 
 ;; 11    1 
 ;; 12    1 
 ;; 13    3 
 ;; 14    1 
 ;; 15    1 
 ;; 16    1 
 ;; 17    1 
 ;; 18    1 
 ;; 19    1 
 ;; 20    1