乐正

Actions speak louder than words.

Sicp-ex1-45

问题

在1.3.3节里,我们看到企图用朴素的方法去找$y \mapsto \frac {x} {y}$的不动点,以便 计算平方根的方式不收敛,这个缺陷可以通过平均阻尼的方法弥补。同样的方法也可以用于 找立方根,将它看做是平均阻尼后的$y \mapsto \frac {x} {y^2}$的不动点。遗憾的是, 这以计算过程对于四次方根却行不通,一次平均阻尼不足以对$y \mapsto \frac {x} {y^3}$ 的不动点搜寻收敛。而在另一方面,如果我们请求了两次平均阻尼(即,用$y \mapsto \frac {x} {y^3}$的平均阻尼的平均阻尼),这一不动点搜寻就会收敛了。请做一些试验, 考虑将计算n次方根作为基于$y \mapsto \frac {x} {y^{n-1}}$的反复平均阻尼的不动点 搜寻过程,请设法确定各种情况下需要做多少次平均阻尼。并请基于这一认识实现一个过程, 它使用fixed-pointaverage-damp和练习1.43的repeated过程计算n次方根。假定你 所需要的所有算术运算都是基本过程。

解答

首先,需要一个用于计算乘幂的过程。我使用练习1.16的fast-expt

fast-expt (ex1-16.scm) download
1
2
3
4
5
6
7
8
9
10
(define (fast-expt b n)
  (define (even? n)
    (= (remainder n 2) 0))

  (define (fast-expt-iter b n product)
    (cond ((= n 0) product)
          ((even? n) (fast-expt-iter (square b) (/ n 2) product))
          (else (fast-expt-iter b (- n 1) (* product b)))))

  (fast-expt-iter b n 1))

因为要做多次的平均阻尼,所以也需要有一个多次计算平均阻尼的过程:

1
2
(define (repeated-average-damp f n)
  ((repeated average-damp n) f))

以上过程都准备好,再加上fixed-point过程便可以写出计算n次方根的过程:

1
2
3
4
5
6
7
8
(define (damped-nth-root n times)
  (define (f x)
    (lambda (y)
      (/ x (fast-expt y (- n 1)))))

  (lambda (x)
    (fixed-point (repeated-average-damp (f x) times)
                 1.0)))

最后需要做的就是观察试验数据,寻找收敛条件,得到需要计算几次平均阻尼。下面是我的 一些试验数据:

n次方根 平均阻尼次数
2 1
3 1
4 2
$\cdots$ $\cdots$
7 2
8 3
9 3
$\cdots$ $\cdots$
15 3
16 4
$\cdots$ $\cdots$
32 5

可以看出,最少需要的平均阻尼次数为$\log_2 n$次。

因为$\log_a x = \frac {\log_c x} {\log_c a}$,所以可以使用下面的过程求解平均 阻尼次数:

1
2
3
4
(define (average-damped-times n)
  (if (= n 1)
      1
      (floor (/ (log n) (log 2)))))

然后,便可以得出所需要的求解n次方根的过程nth-root

1
2
(define (nth-root n)
  (damped-nth-root n (average-damped-times n)))

将上面的程序集中到一起看:

练习1.45 (ex1-45.scm) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
(define (repeated-average-damp f n)
  ((repeated average-damp n) f))

(define (damped-nth-root n times)
  (define (f x)
    (lambda (y)
      (/ x (fast-expt y (- n 1)))))

  (lambda (x)
    (fixed-point (repeated-average-damp (f x) times)
                 1.0)))

(define (average-damped-times n)
  (if (= n 1)
      1
      (floor (/ (log n) (log 2)))))

(define (nth-root n)
  (damped-nth-root n (average-damped-times n)))

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
(define (sqrt n) ((nth-root 2) n))
;Value: sqrt

(sqrt 100)
;Value: 10.

(sqrt 4)
;Value: 2.000000000000002

(define (cbrt n) ((nth-root 3) n))
;Value: cbrt

(cbrt 27)
;Value: 2.9999972321057697

(define (32th-root n) ((nth-root 32) n))
;Value: 32th-root

(32th-root 65536)
;Value: 1.4142135625551093

(32th-root 4294967296)
;Value: 2.000000000000006

draft

« sicp-ex1-44 sicp-ex1-46 »

Comments