代码之家 › 专栏 › 技术社区 › J. Mini

为什么我的迭代高阶过程比我的等价递归过程给出更精确的结果?

sicp higher-order-functions precision racket lisp

J. Mini · 技术社区 · 5 年前

Exercise 1.30 of SICP 邀请我们将以下代码重写为迭代(读:tail recursive)过程:

(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a)
         (sum term (next a) next b))))

为了帮助我们,我们获得了以下模板:

(define (sum term a next b)
  (define (iter a result)
    (if <??>
        <??>
        (iter <??> <??>)))
  (iter <??> <??>))

在一次错误的开始之后,我给出了以下答案,似乎是正确的:

(define (sumIT term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (+ (term a) result))))
  (iter a 0))

为了测试这一点,我从上面给出的练习中复制了以下代码:

(define (integral f a b dx)
  (define (add-dx x) (+ x dx))
  (* (sum f (+ a (/ dx 2.0)) add-dx b)
     dx))
(integral cube 0 1 0.01)
(integral cube 0 1 0.001)

并很快用 sumIT :

(define (integralIT f a b dx)
  (define (add-dx x) (+ x dx))
  (* (sumIT f (+ a (/ dx 2.0)) add-dx b)
     dx))
(integralIT cube 0 1 0.01)
(integralIT cube 0 1 0.001)

然后,当我在DrRacket的#lang sicp模式下运行时,它没有 cube 默认情况下,我还定义了:

(define (cube x) (* x x x))

最后,我运行了代码。

毫不奇怪, (integral cube 0 1 0.01) 和 (integralIT cube 0 1 0.01) 两者产生的结果完全相同:0.2499875000000042。但是,令我震惊和恐惧的是, (integral cube 0 1 0.001) 返回0.249999875000001,而 (integralIT cube 0 1 0.001) 返回更精确的答案0.24999987500000073。

这是为什么?为什么将递归高阶过程重写为尾部递归会提高结果的精度?我想不出代码中有任何部分或错误会导致这种情况。

0 回复 | 直到 5 年前

coredump 5 年前

浮点加法和乘法是交换的,但不是结合的。这意味着 (+ (+ a b) c) 可能不等于 (+ a (+ b c) ,由于错误传播。正如scar Lpez提到的alredy,参见 What Every Computer Scientist Should Know About Floating-Point Arithmetic .

我用Common Lisp重写了你的例子,我可以观察到同样的行为。

然后我通过插入反引号和逗号稍微修改了代码,这样函数就可以返回一棵树而不是一个数字。看见 Macros: defining your own 如果您不熟悉synax。

这棵树是由数字和符号组成的( * , + , ...) 并对应于每个版本中所做的操作。这应该有助于理解如何以及何时计算中间结果。

递归求和:

(defun sum (term a next b)
  (labels ((it (a)
             (if (> a b)
                 0
                 `(+ ,(it (funcall next a))
                     ,(funcall term a)))))
    (it a)))

尾部递归和:

(defun sum-it (term a next b)
  (labels ((it (a result)
             (if (> a b)
                 result
                 (it (funcall next a)
                     `(+ ,(funcall term a) ,result)))))
    (it a 0)))

递归积分:

(defun integral (f a b dx)
  (flet ((add-dx (x) (+ x dx)))
    `(* ,(sum f (+ a (/ dx 2.0d0)) #'add-dx b) ,dx)))

尾部递归积分:

(defun integral-it (f a b dx)
  (flet ((add-dx (x) (+ x dx)))
    `(* ,(sum-it f (+ a (/ dx 2.0d0)) #'add-dx b) ,dx)))

和立方体:

(defun cube (x) (* x x x))

测试时要小心 :由于target precision参数太精确,您将得到一个很大的结果。

您可以看到,这两种方法最终以不同的顺序计算结果:

CL-USER> (integral #'cube 0 1 0.4d0)
(* (+ (+ (+ 0 1.0d0) 0.21600000000000008d0) 0.008000000000000002d0) 0.4d0)

相比之下:

CL-USER> (integral-it #'cube 0 1 0.4d0)
(* (+ 1.0d0 (+ 0.21600000000000008d0 (+ 0.008000000000000002d0 0))) 0.4d0)

在上面的例子中,结果没有差别,但是对于一些输入,比如你找到的输入,结果会有差别。