sicp习题试解 (1.7)
; ======================================================================
;
; Structure and Interpretation of Computer Programs
; (trial answer to excercises)
;
; 计算机程序的构造和解释(习题试解)
;
; created: code17 02/24/05
; modified:
; (保持内容完整不变前提下，可以任意转载)
; ======================================================================
;; SICP No.1.7
;; 本期第一部分为理解题，第二部分为编程
;; 理解部分：关于误差
;; 函数"good-enough?"在参数值较大和较小时均会产生误差问题
;; (1) 正常的计算都会产生误差，比如1/3是无限循环小数，有无数个有效位(从
;; 左端的一个不为0的数字起至右端最后一位不为0的数字止)，而在计算机中
;; 或任何其他形式的机械计算中，分配给每个数字的存储空间都是有限位的。
;; 因此舍入误差在所难免。但在一般的普通计算中，因为计算机已经提供了
;; 相当多的存储位，右端较低位次上需要舍入的量级往往非常小，大部分情
;; 况下对计算结果没什么影响。
;; (2) 但当运算结果很大时，小数点左边位数很多，所进行舍入和非舍入的分界
;; 位置就可能很高，因此误差就会很大。设想一个最简单的模型，一共有10
;; 个有效位(小数点和其他控制位另算)，那么1.234567890123舍入为
;; 1.234567890，舍入误差为0.000000000123；而同样有效位的1234567890123
;; 则舍入为1234567890000，舍入误差为123，也就是说所有的1234567890xxx
;; 在计算存储以后只能获得同样的结果。因此在good-enough?的定义中，当参
;; 数很大时，自动的舍入误差已经相当大，绝对误差很大的数也可能被舍入为
;; 同样的数值，从而导致判断为good-enough，
;; > (* 123456789.1 123456789.1)
;; 15241578774881878.0
;; ;; 实际值15241578774881878.81，舍入误差0.81，所以
;; > (good-enough? 123456789.1 15241578774881878)
;; #t
;; ;; 而根据表达式(square guess)和x的实际差是0.81>>>0.001
;; (3) 当参数很小时，同样会发生舍入误差。但正如我们所说的低位的舍入误差
;; 绝对值很小。问题在于，在一个固定的绝对误差标准(比如这里的<0.001)
;; 下，如果参数本身的量级足够小，那么这个绝对误差标准所允许的误差相
;; 对于参数本身的相对误差可能是惊人的。比如
;; > (good-enough? 0.00001 0.0000000001)
;; #t
;; ;; 准确值0.00001 * 0.00001 = 0.0000000001
;; > (good-enough? 0.0001 0.0000000001)
;; #t
;; ;; 比准确值大了10倍的0.0001，一样可以通过测试。因为
;; ;; 0.0001 * 0.0001 -0.0000000001 同样小于0.0001
;; 和上一种情况不同，这里的判断是严格符合我们的程序逻辑的，而不是
;; 自动的舍入造成的问题(这里的有效位是1位)，但这样的结果是没有意义的。
;; 而问题在于在这个问题中，无论我们规定多小的误差标准，总存在足够小的
;; 参数使得这种绝对误差标准没有意义。
;; 由此可见，首先，在考虑误差相关的计算时，应该尽量避免过大的操作数，在
;; 原始的good-enough?定义中，比较(square guess) 和 x 不如比较guess和
;; (/ x guess)，这两种方法有着类似的含义，但后者的运算数的量级远小于前者。
;; 其次使用绝对误差在很多情况下是有问题的，而使用相对误差控制显然可以
;; 解决(3)中的问题，在某些情况下也可以降低运算数的量级从而改善(2)。
;; 程序部分:
(define (average x y)
(/ (+ x y)
2))
(define (improve guess x)
(average guess
(/ x guess)))
(define (good-enough? oldguess guess)
(< (abs (/ (- guess oldguess)
guess))
0.001))
(define (sqrt-iter oldguess guess x)
(if (good-enough? oldguess guess)
guess
(sqrt-iter guess
(improve guess x)
x)))
(define (sqrt x)
(sqrt-iter 0.1 1.0 x))
;; Test-it
;; > (sqrt 2)
;; 1.4142135623746899
;; > (sqrt 9)
;; 3.000000001396984
;; >
