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.16 中我们已经设计过一个迭代式的 fast-expt，这里和上一个 fast-expt 极其相似：我们设计一个不变量用来保存结果，当乘数是 2 的倍数的时候，我们对被乘数 double，对乘数 halve；当乘数是奇数的时候，将乘数减一，被乘数加到不变量上。
(define (x a b)
(define (x/iter aa bb ans)
(cond ((= bb 0) ans)
((even? bb) (x/iter (double aa) (halve bb) ans))
(else
(x/iter aa (- bb 1) (+ ans aa)))))
(x/iter a b 0))
我们还可以把这样的过程写为递归过程：
(define (x/rec a b)
(cond ((= b 0) 0)
((even? b) (double (x/rec a (/ b 2))))
(else
(+ a (x/rec a (- b 1))))))
最后对两个过程进行测试
(load "../testframe.scm")
(assert= (x 2 1) 2)
(assert= (x 2 11) 22)
(assert= (x 3 14) 42)
(assert= (x/rec 2 1) 2)
(assert= (x/rec 2 11) 22)
(assert= (x/rec 3 14) 42)