scheme - SICP Ex。1.17 - “快速乘法”比“乘法”慢？

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) 空间）：

（注意+ a上面第 4 行如何移动到累加器，下面第 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)))))

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

我在这里错过了什么吗？好奇是否有办法实现halve，double所以他们实际上给出了这里建议的 log(n) 结果。必须有，否则这个问题就没有意义了。

请注意，如果 a 和 b 的大小不同，则它们的顺序很重要——比如乘以 2、100 次或 100、2 次，第一个是 100 步，后一个是 2 步。这将是稍后添加到此功能的内容。但好奇halve并double开始。

标签： schemelispmultiplicationsicpmit-scheme

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——重要的是要保持一致，将一个参数的问题减半，另一个参数加倍，加倍的就是我们需要的那个添加到最终结果。