Exercise 1.17 · 习题

Exercise 1.17: The exponentiation algorithms in
this section are based on performing exponentiation by means of repeated
multiplication. In a similar way, one can perform integer multiplication by
means of repeated addition. The following multiplication procedure (in which
it is assumed that our language can only add, not multiply) is analogous to the
expt procedure:

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

This algorithm takes a number of steps that is linear in b. Now suppose

we include, together with addition, operations double, which doubles an

integer, and halve, which divides an (even) integer by 2. Using these,

design a multiplication procedure analogous to fast-expt that uses a

logarithmic number of steps.

练习 1.17：本节的幂运算算法基于反复相乘来执行求幂。类似地，也可以用反复相加来执行整数乘法。下面的乘法过程（假定我们的语言只能做加法，不能做乘法）与 expt 过程类似：

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

该算法的步骤数与 b 成线性关系。现在假设我们在加法之外，还有操作 double（将一个整数加倍）和 halve（将一个偶数除以 2）可用。利用这两个操作，设计一个类似 fast-expt 的乘法过程，使其步骤数是对数级的。