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 nth roots as a fixed-point search based upon repeated average damping of y ↦ x/yn-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.

(define tolerance 0.00001)
(define (average a b) (/ (+ a b) 2))
(define (fixed-point-damp-n f n first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (average-damp f)
    (lambda (x) (average x (f x))))
  (define (try guess guesses-left)
    (newline)
    (display guess)
    (let ((next (((repeated average-damp n) f) guess)))
      (cond ((close-enough? guess next) next)
	    ((= guesses-left 0) false)
	    (else (try next (- guesses-left 1))))))
  (try first-guess 1500))
 
(define (pow x n)
  (if (= n 0)
      1
      (* x (pow x (- n 1)))))
 
(fixed-point-damp-n (lambda(y) (/ 27 (* y y))) 1 2.0)   ; 3rd root converges
(fixed-point-damp-n (lambda(y) (/ 81 (* y y y))) 1 2.0) ; 4th root/1 damp does NOT
(fixed-point-damp-n (lambda(y) (/ 81 (* y y y))) 2 2.0) ; 4th root/2 damp does
(fixed-point-damp-n (lambda(y) (/ 81 (pow y 4))) 2 2.0) ; 5th rt/2 damp does
(fixed-point-damp-n (lambda(y) (/ 81 (pow y 5))) 2 2.0) ; 6th rt/2 damp does
(fixed-point-damp-n (lambda(y) (/ 81 (pow y 6))) 2 2.0) ; 7th rt/2 damp does
(fixed-point-damp-n (lambda(y) (/ 81 (pow y 7))) 2 2.0) ; 8th rt/2 damp does NOT
(fixed-point-damp-n (lambda(y) (/ 81 (pow y 7))) 3 2.0) ; 8th rt/3 damp does
(fixed-point-damp-n (lambda(y) (/ 81 (pow y 14))) 3 2.0) ; 15th rt/3 damp does
(fixed-point-damp-n (lambda(y) (/ 81 (pow y 15))) 3 2.0) ; 16th rt/3 damp does NOT
(fixed-point-damp-n (lambda(y) (/ 81 (pow y 15))) 4 2.0) ; 16th rt/4 damp does
 
; conclusion of experimentation use at least (floor (base-2-log n)) damps
(define (nth-root x n)
  (fixed-point-damp-n
   (lambda (y) (/ x (pow y (- n 1))))
   (floor (/ (log n) (log 2)))
   (/ (log x) (log n) )))
 
(nth-root 81 2)
(nth-root 1296 4)
(nth-root 12789452 16)
(nth-root 127894523423422 16)
(nth-root 127894523423422 17)
(nth-root 127894523423422 17)
(nth-root 1296422342342342342342324 123)
(nth-root 1296342 1234)
(nth-root 129 129)