SICP练习题1.45——求n次方根

《SICP》第一章最后有个练习非常有意思：求n次方根。书的第一章几乎用了所有的篇幅来讲一些算法和抽象，并且在第一章第一节就说到了用牛顿迭代法来求一个数的平方根，在第一章最后一节的练习中要求一个数的n次方根。

根据书上前面几节的说法，求x的平方根就是求函数y->x/y的不动点，而不动点的求法就相当简单了，随便猜一个数带入函数，如果结果不好再将结果带入函数，最终函数总会得到不动点。但是如果直接这样求平方根会有一个问题：函数并不收敛（假设最开始猜y，那么带入函数会得到x/y，将结果再带入函数又得到y），补救办法就是使用一个叫average damp的方法（实在找不到中文的翻译，直译过来就是平均阻尼），average-damp可以直接用下面函数定义出来：

(define (average-damp f)
    (lambda (x)
        (average x (f x))))

这个函数的作用就是取函数返回值和函数参数的平均数，这样先对y->x/y这个函数取average damp，再对结果取不动点就能得到平方根了。我们也能用同样的方法取一个数的三次方根，只要将函数换为y->x/y²即可，但是对于四次方根无法得到结果，原因也是不收敛，而解决办法竟然是对原始函数取两次average damp。题目要求我们做实验得出为了取n次方根而必须取average damp次数的规律，这样我们可以定义下面的函数：

(define (fixed-point f guess)
 (define (close-enough? a b)
  (< (abs (- a b)) 0.0001))
 (let ((guess-value (f guess)))
  (if (close-enough? guess guess-value)
   guess
   (fixed-point f guess-value))))

(define (repeated f n)
 (define (iter f n result)
  (if (< n 1)
   result
   (iter f (- n 1) (lambda (x) (f (result x))))))
 (iter f n identity))

(define (average-damp f)
 (lambda (x)
  (average x (f x))))

(define (average a b)
 (/ (+ a b) 2))

(define (square x)
 (* x x))

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

其中fixed-point需要一个函数f，和一个最初的猜测数，返回满足要求的不动点；而repeated将带入的函数f迭代n次。
实验结果如下：

#;1> (nth-root 8 3)
2.00003461276416
#;2> (nth-root 128 7)
1.9999526734277

但是一到8次方根以上程序便会在两个数之间跳转，因此需要再将函数average damp一次，而函数到了16次方后又需要average damp一次。这样看基本上得出了规律：只需要将所求的根数取log₂即可，但是scheme只提供了以自然对数为底的log函数，不过只需要定义下面的函数就可以求以2为底的log了：

(define (log2 x)
 (/ (log x) (log 2)))

这样我们就能够解决1.45的习题了：

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

由于数学能力有限实在是无法证明为什么结果是这样，而且对于average damp这样一种方法维基百科上竟然没有！以前的数学实在学得不怎么样啊。不过《SICP》的习题做起来确实很有意思，还教你直接求tan、黄金分割数还有e的方法。