代码

下面是书中求平方根的代码:

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

(define (sqrt x)
  (sqrt-iter 1.0 x))

以及一些辅助函数/过程:

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

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

(define (improve guess x)
  (average guess (/ x guess)))

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))

问题

这里的 good-enough?, 有一些比较隐晦的问题

它通过 guess * guess - x 的绝对值是否小于 0.001, 来判断是否足够接近答案
但当你要求一个很小很小很小很小的数字的平方根时, 不管怎么样, 差值的绝对值都肯定远小于 0.001 这个锚点
也就是说当数字超级小时, 根据我们给的约束, 不管怎么样都是足够逼近的

举个例子: 0.000009 = 0.003 * 0.003, 因此我们希望 (sqrt 0.000009) 的结果差不多是 0.003

(sqrt 0.000009)
; 0.03134584760656851

0.03, 0.003, 两者差了整整一个数量级! 这是因为我们定的锚点是 0.001, 这对于太小的数字实在是不够用
将 0.03 作为 guess 反代进 good-enough? 中, 则 0.03 * 0.03 = 0.0009, 而 abs(0.000009 - 0.0009) 为 0.000891
这小于 0.001, 那么自然应该算作 "足够逼近的标准", 毕竟是我们自己定义的这么一个精度

当你要求星球之间的距离精确到 0.1m 时这毫无问题 当你要求原子之间的距离精确到 0.1m 时......嘛......

为了更好地理解, 我们可以修改一下 good-enough?:

(define (good-enough? guess x)
  (<= (abs (- (* guess guess) x)) 1))

(sqrt 2)
; 1.5

我们将 0.001 改成了 1, 于是当我们传入某个一般大的数字(这里是2)时, 会因为精度要求太大, 求得1.5就认为足够逼近了

那么可能就有人要说了:
既然 0.001 作为精度不够, 那么我来一个 0.0000000000000001

(define (good-enough? guess x)
  (<= (abs (- (square guess) x)) 0.0000000000000001))

(sqrt 2)

此时会发生无限死循环, 因为我们给的精度要求实在是太小, 再加上浮点数误差(应该说, 不准确(inexact)), 导致永远无法达到要求
以上述代码为例, guess 的数值会是:

1.0
1.5
1.4166666666666665
1.4142156862745097
1.4142135623746899
1.414213562373095
1.414213562373095
1.414213562373095
1.414213562373095
1.414213562373095
1.414213562373095
1.414213562373095

我们实际上已经算出来了 1.414213562373095 这个值, 但因为 good-enough? 的精度要求太小, 其永远返回 #f
且因为浮点数不准确的原因, (improve 1.414213562373095 2) 等于 1.414213562373095
因此我们将永远无限循环下去

对于很大很大很大很大的数字也是一样的道理:
因为数字太大, 能够作为小数部分的数字随着数字的数量级增大, 是有限的
当对这样的数字进行计算时, 最后的结果因为无法表示某个相当准确的浮点数, 只能将末尾的小数进行四舍五入来保存
因此对于很大的数字, 一样有可能造成无限死循环

解决

既然你这也不行那也不行, 0.001你嫌弃, 0.00000000001你也嫌弃, 那怎么办! (愤怒)
正如题目给出的提示: 不是监视差值, 而是监视 guess 迭代时的变化情况

只要上一次的guess, 与这一次的guess, 两者之间的变化值, 与这一次的 guess 比较
只要改变值相对于猜测值的比率很小, 那么就算作已经足够逼近

因此我们需要修改先前的函数:

(define (good-enough? old-guess guess)
  (> 0.01
    (/ (abs (- guess old-guess))
        old-guess)))

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

这样已经基本上解决了先前的问题, 当然我们也可以将 0.01 写成 0.00001 来变得更加准确

上一篇: 1-6
下一篇: 1-8