Exercise 1.45.  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.

――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――

If we search for a fixed point of f: y ↦ x/y by repeated application, we get:

y → x/y → y → x/y …

If instead we take f: y ↦ (y + x/y) / 2, we get

y → (y + x/y) /2 → (y + x/((y + x/y)/2) /2 = y/2 + x/(y + x/y) = y/2 + xy/(x+y) = (y² + 3xy) / (2x + 2y)

If we can show that |f(f(y)) - √x| < |y - √x| , for all y ≠ √x, then we can 
see that this converges.

(define (f x n m)
  (fixed-point (lambda (x)
                       ((repeated a

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

1 ]=> (fixed-point (average-damp (lambda (y) (/ 16 (* y y y)))) 5.0)

x = 16
y = 2.01

16 / y^3 = 16 / 8.12061 = 1.9702975186196192

avg = 1.9851487593098094

(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)
    (display guess) (newline)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

(define (compose f g) (lambda (x) (f (g x))))

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

(define (nth-root n x dampings)
  (fixed-point ((repeated average-damp dampings) (lambda (y) (/ x (expt y (- n 1))))) 1.0))

Experimentation suggests that floor(log₂ n) dampings are necessary and sufficient for convergence.

(define (nth-root n x)
  (let ((dampings (floor (/ (log n) (log 2)))))
    (fixed-point ((repeated average-damp dampings) (lambda (y) (/ x (expt y (- n 1)))))
                 1.0)))