walker...to the next step

(define (repeated-i f n)
  (define (iter accum k)
    (if (= k 1)
        accum
        (iter (lambda (x) (f (accum x))) (- k 1))))
  (iter f n))

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

(define (square-root x)
  (fixed-point (average-damp (lambda (y) (/ x y))) 1.0))

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

(define (fourth-root x)
  (fixed-point ((repeated-i average-damp 2) (lambda (y) (/ x (* y y y)))) 1.0))

(define (fifth-root x)
  (fixed-point ((repeated-i average-damp 2) (lambda (y) (/ x (* y y y y)))) 1.0))

(define (sixth-root x)
  (fixed-point ((repeated-i average-damp 2) (lambda (y) (/ x (* y y y y y)))) 1.0))

哎，看出来了么： 

(define (test-nth-root n times-to-damp)
  (lambda (x)
    (fixed-point ((repeated-i average-damp times-to-damp)
                  (lambda (y) (/ x (expt y (- n 1)))))
                 1.0)))

试了多次以后找到规律：

n             damp次数        关系

1-3          1

4-8          2                   8 = 2 ^ (2 + 1)

9-16        3                   16 = 2 ^ (3 + 1)

17-32      4                   32 = 2 ^ (4 + 1)

于是，求x的n次方：

(define (nth-root n x)
  (define (calc-damp n) (- (ceiling (/ (log n) (log 2))) 1))
  ((test-nth-root n (calc-damp n)) x))

注意其中的calc-damp，比如9-16的log2(n) ，结果肯定落在(3,4]，因此ceiling上去统一用16的，准没错儿。