乐正

Actions speak louder than words.

Sicp-ex1-7

问题

对于确定很小的数的平方根而言,在计算平方根而言,在计算平方根中使用的检测good-enough? 是很不好的。还有,在现实的计算机里,算术运算总是以一定的有限精度进行的。这也会使 我们的检测不适合特别大的数的计算。请解释上述论断,用例子说明对很小和很大的数, 这种检测都可能失败。实现good-enough?的另一种策略是监视猜测值在从一次迭代到下一 次的变化情况,当改变值对于猜测值的比率很小时就结束。请设计一个采用这种终止测试方 式的平方根过程。对于很大和很小的数,这一方式都能工作吗?

解答

由于验证一个猜测是否足够好的方式为计算 $$ \begin{array}{l} |guess^2 - x| & < 0.001 \\ guess^2 & <= 0.001 + x \\ guess & <= 0.031 \end{array} $$ 所以,当所求平方根数足够小的时候,只要猜测数小于等于0.031,便会满足验证是否足够好的方 程,从而被错误的认为是所求的平方根数。

1
2
3
4
5
6
7
;;; 例子

(sqrt 0.0001)
;Value: 0.03230844833048122

(sqrt 0.00003)
;Value: 0.03156903722951577

对于特别大的数,mit-scheme 实现的小数精度不足以表示两个大数之间的差,所以sqrt会 陷入死循环而无法得出正确结果。

如题所述,使用另一种策略监视猜测值:

1
2
3
4
5
6
7
8
(define (good-enough? guess new-guess)
  (< (/ (abs (- guess new-guess)) guess) 0.001))

(define (sqrt-iter guess x)
  (if (good-enough? guess (imporve guess x))
      (improve guess x)
      (sqrt-iter (improve guess x)
                  x)))

新版函数对于很小的数和很大的数都能有效计算。

draft

« sicp-ex1-6 sicp-ex1-8 »

Comments