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

Question

Exercise 1.30 of SICP 邀请我们将以下代码重写为迭代（阅读：尾递归）过程：

(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.24998750000000042。但是，令我震惊和恐惧的是，(integral cube 0 1 0.001) returns 0.249999875000001 而 (integralIT cube 0 1 0.001) returns 更精确的答案是 0.24999987500000073.

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

Answer 1

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

我用 Common Lisp 重写了您的示例，我可以观察到相同的行为。

然后我通过插入反引号和逗号稍微更改了代码，这样函数 returns 就变成了一棵树而不是一个数字。如果您不熟悉语法，请参阅 Macros: defining your own。

树由数字和符号（*、+、...）组成，对应于每个版本中所写的操作。这应该有助于理解如何以及何时计算中间结果。

递归求和：

(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))

测试时要小心：目标精度参数过于精确，结果会很大。

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

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)

在上面的例子中，结果并没有不同，但是对于像你找到的那样的一些输入，会有不同。

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

Why does my iterative higher-order procedure give more precise results than my equivalent recursive procedure?

lisp

precision

recursion

sicp

racket