scheme - SICP Ex。 1.17 - "fast-multiply"比 "multiply"慢？

Question

以下函数作为本练习的介绍，说明了用加法定义的乘法。这是最简单的“容易写下来”的递归定义。

(define (star a b)
  (if (= b 0)
      0
      (+ a (star a (- b 1)))))

当我看到这一点时，我做的第一件事就是按照之前的练习，编写一个不会破坏堆栈的迭代形式:

(define (star a b)
  (star-iter a b 0))
(define (star-iter a counter sum)
  (if (= counter 0)
      sum
      (star-iter a (- counter 1) (+ a sum))))

练习 1.17 鼓励我们找到一个不变量，以减小问题规模，其想法是从 O(n) 到 O(logn) 步数(当执行该特定步骤时，无需执行任何更新结果的事情 - 我们在该步骤中所做的就是减少/转换问题定义 - 这就是“找到不变量”的含义)(参见下面第一个代码块的第 3 行 - 没有添加任何内容导致该步骤)。

对于快速版本，问题说我们应该使用函数halve和double，并且似乎暗示这些函数可以作为机器操作使用(恒定时间？)。我已经实现了“快速”版本，只是欺骗了这些函数，如下所示:

(define (fast-star a b)
  (cond ((or (= b 0) (= a 0)) 0)
        ((even? a)      (fast-star (/ a 2) (* 2 b)))
        (else      (+ a (fast-star a       (- b 1))))))

迭代形式的相同内容(即 O(1) 空间):

(请注意上面第 4 行中的 + a 如何移动到下面第 6 行末尾的累加器，以将其置于尾部位置)

(define (fast-star b)
  (fast-star-iter a b 0))
(define (fast-star-iter a b sum)
  (cond ((or (= a 0) (= b 0)) sum)
        ((even? a) (fast-star-iter (/ a 2) (* 2 b) sum))
        (else      (fast-star-iter a       (- b 1) (+ a sum)))))

所以这是一个“有什么意义”的问题 - 这些函数比上面给出的前两个函数慢。这四个函数中的第一个会破坏堆栈，因此它没有用。但第二个没有。在我的测试中，这个版本比这两个“快速”版本中的任何一个都更快。

我在这里遗漏了什么吗？很好奇是否有一种方法可以实现减半和双倍，以便它们实际上给出此处建议的 log(n) 结果。一定有，否则这个问题就没有意义。

请注意，如果 a 和 b 的大小不同，则它们的顺序很重要 - 例如乘以 2、100 次或 100、2 次，第一个是 100 步，后一个是 2 步。这将是稍后添加到此功能中的内容。但首先对 half 和 double 感到好奇。

Answer 1

您的代码中有一个微妙的错误，这就是它很慢的原因。对于版本 3 和 4，这应该可以解决这个问题:

(define (fast-star a b)
  (cond ((or (= b 0) (= a 0)) 0)
        ((even? b) (fast-star (* 2 a) (/ b 2.0)))
        (else (+ a (fast-star a (- b 1))))))

(define (fast-star-iter a b sum)
  (cond ((or (= a 0) (= b 0)) sum)
        ((even? b) (fast-star-iter (* 2 a) (/ b 2.0) sum))
        (else (fast-star-iter a (- b 1) (+ a sum)))))

这个想法是在每次迭代中不断添加a并减少b，但根据情况有时您会减少 b 有时你会加倍!另请注意，我将 b 除以 2.0 以消除精确算术，这样速度较慢。

当然，您也可以反过来做:添加 b 并减少 a - 重要的是要一致它，将一个参数的问题减半，并将另一个参数加倍，加倍的参数就是我们需要添加到最终结果中的参数。