SICP 前。 1.17 - "fast-multiply" 比 "multiply" 慢？
SICP Ex. 1.17 - "fast-multiply" slower than "multiply"?
作为本练习介绍的以下函数说明了根据加法定义的乘法。这是最简单的"easy to write down"，递归定义
(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) 的步骤数（没有，当执行该特定步骤时，做任何事情来更新结果——我们在这一步所做的就是reduce/transform问题定义——这就是'find an invariant'的意思）（见下面第一个代码块的第3行——什么都不是被添加到该步骤的结果中）。
对于快速版本，问题说我们应该使用函数 halve 和 double 并且似乎暗示这些可以作为机器操作使用（恒定时间？）。我已经实现了 "fast" 版本，只是欺骗了这些功能，如下所示：
(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) space）：
（请注意上面第 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)))))
所以这是一个 "what's the point" 问题 - 这些函数比上面给出的前两个函数慢。这四个函数中的第一个会破坏堆栈，因此没有用。但是第二个没有。在我的测试中，那个 比这两个 "fast" 版本中的任何一个都快。
我在这里遗漏了什么吗？好奇是否有实现 halve 和 double 的方法，所以他们实际上给出了此处建议的 log(n) 结果。必须有，否则这个问题就没有意义了。
请注意，如果 a 和 b 的大小不同，它们的顺序很重要 - 例如乘以 2、100 次或 100、2 次，第一个是 100 步，后一个是 2 步。这将是稍后添加到此功能的内容。但是对 halve 和 double 感到好奇。
我认为主要问题是 b 正在递减和加倍，即 b 应该减半而不是 a。目前 2 * 100 将变为 1 * 200 并且需要递减 200 次而不是 100 次。而如果应该变为 4 * 50 然后 8 * 25，...
此外，如果我们减少奇数，结果将是偶数，因此下一步会将 b 的值减半。即，至少一半的迭代会将 b
的值减半
例如如果 b < 1048576 (2^20) 则步数应小于 40。通常迭代次数小于 (* 2 (log b 2)).
您的代码中有一个细微的错误，这就是它运行缓慢的原因。这应该修复它，对于版本 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 - 重要的部分是 一致 ，将一个参数的问题减半，将另一个参数加倍，加倍的那个就是我们需要添加到最终结果的那个。
想法是，而不是使用公式
a*n = a+a*(n-1)
你应该使用公式
a*n = a*(n/2)+a*(n/2)
并注意 n 为 even 且 n 为 odd 的情况。应用这个会给你 O(log n) 复杂性而不是 O(n).
作为本练习介绍的以下函数说明了根据加法定义的乘法。这是最简单的"easy to write down"，递归定义
(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) 的步骤数（没有，当执行该特定步骤时，做任何事情来更新结果——我们在这一步所做的就是reduce/transform问题定义——这就是'find an invariant'的意思）（见下面第一个代码块的第3行——什么都不是被添加到该步骤的结果中）。
对于快速版本，问题说我们应该使用函数 halve 和 double 并且似乎暗示这些可以作为机器操作使用（恒定时间？）。我已经实现了 "fast" 版本，只是欺骗了这些功能，如下所示：
(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) space）：
（请注意上面第 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)))))
所以这是一个 "what's the point" 问题 - 这些函数比上面给出的前两个函数慢。这四个函数中的第一个会破坏堆栈，因此没有用。但是第二个没有。在我的测试中，那个 比这两个 "fast" 版本中的任何一个都快。
我在这里遗漏了什么吗？好奇是否有实现 halve 和 double 的方法，所以他们实际上给出了此处建议的 log(n) 结果。必须有，否则这个问题就没有意义了。
请注意，如果 a 和 b 的大小不同，它们的顺序很重要 - 例如乘以 2、100 次或 100、2 次，第一个是 100 步，后一个是 2 步。这将是稍后添加到此功能的内容。但是对 halve 和 double 感到好奇。
我认为主要问题是 b 正在递减和加倍，即 b 应该减半而不是 a。目前 2 * 100 将变为 1 * 200 并且需要递减 200 次而不是 100 次。而如果应该变为 4 * 50 然后 8 * 25，...
此外，如果我们减少奇数，结果将是偶数，因此下一步会将 b 的值减半。即，至少一半的迭代会将 b
例如如果 b < 1048576 (2^20) 则步数应小于 40。通常迭代次数小于 (* 2 (log b 2)).
您的代码中有一个细微的错误，这就是它运行缓慢的原因。这应该修复它，对于版本 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 - 重要的部分是 一致 ，将一个参数的问题减半，将另一个参数加倍，加倍的那个就是我们需要添加到最终结果的那个。
想法是，而不是使用公式
a*n = a+a*(n-1)
你应该使用公式
a*n = a*(n/2)+a*(n/2)
并注意 n 为 even 且 n 为 odd 的情况。应用这个会给你 O(log n) 复杂性而不是 O(n).