以下函数作为本练习的引子，说明用加法定义乘法。这是最简单的 "易记"，递归定义。
(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 所以它们实际上给出了这里所建议的对数(n)结果。肯定是有的，否则这个问题就没有意义了。
注意，如果它们的大小不同，a &b的顺序很重要--比如乘2，100次或100，2次，前者是100步，后者是2步。这就需要以后在这个函数中增加一些内容了。但好奇的是 halve 和 double 开始。
你的代码中存在一个微妙的错误，这就是为什么它很慢。这应该可以解决这个问题，对于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 - 重要的是 一致 关于它，把一个参数上的问题减半，另一个参数翻倍，而被翻倍的那个参数就是我们需要添加到最终结果中的那个参数。
我认为主要的问题是 b 既被递减又被加倍，即。b 应该是减半而不是 a. 目前2*100会变成1*200，需要200次递减，而不是100次。 而if应该变成4*50，然后是8*25，...。
另外，如果我们将一个奇数递减，结果将是偶数，所以下一步将把奇数的值减半。b. 即，至少有一半的迭代将使 b
例如：如果 b < 1048576(2^20)，那么步数应该小于40。 一般来说，迭代次数要小于（* 2（log b 2））。
我们的想法是，不使用公式
a*n = a+a*(n-1)
你应该使用的公式
a*n = a*(n/2)+a*(n/2)
并注意在以下情况下 n 是 even 和n是 odd. 应用这个方法，你会得到 O(log n) 复杂性而不是 O(n).