作者：未知 来源：月光软件站 加入时间：2005-2-28　月光软件站

; ======================================================================
;
;          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
;; > 

相关软件：