防爆。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(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)))))

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

我在这里有遗漏什么吗？奇怪的是，是否有一种实现halve和double的方法，因此它们实际上给出了这里建议的日志(N)结果。否则，这个问题就没有意义了。

注意，如果a&b的顺序是不同的，那么它们的顺序非常重要--例如乘以2,100或100，2倍，第一步是100步，后2步。这将是以后添加到此函数中的内容。但一开始对halve和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 --重要的是要保持一致，将一个参数的问题减半，将另一个参数的问题加倍，其中一个是我们需要在最终结果中添加的。

Answer 2

我认为主要的问题是b正在减少并翻一番，也就是说，b应该减半，而不是a。目前，2* 100将变成1* 200，需要减少200次而不是100次。如果应该变成4* 50然后是8* 25 .

另外，如果我们减少一个奇数，结果将是偶数，所以下一步将把b的值减半。也就是说，至少一半的迭代将使b的值减半

如果b < 1048576 (2^20)，则数步应小于40。通常，迭代次数小于(* 2(Logb2))。

Answer 3

我们的想法是，与其使用公式

a*n = a+a*(n-1)

你应该用这个公式

a*n = a*(n/2)+a*(n/2)

并注意n为even而n为odd的情况。应用这一点将给您带来O(log n)复杂性，而不是O(n)。