Consider the problem of computing the exponential of a given number. We would
like a procedure that takes as arguments a base b and a positive integer
exponent n and computes b
n. One way to do this is via the
recursive definition
考虑计算一个给定数的幂次问题。我们希望设计一个过程，它接受底数 b 和正整数指数 n 作为参数，并计算 b
n。一种方式是借助如下递归定义：
b
n
=
b
⋅
b
n
−
1
,
b
0
=
1
,
which translates readily into the procedure
这可以直接翻译成如下过程：
This is a linear recursive process, which requires Θ
(
n
) steps and
Θ
(
n
) space. Just as with factorial, we can readily formulate an
equivalent linear iteration:
这是一个线性递归型计算过程，需要 Θ
(
n
) 步和 Θ
(
n
) 的空间。与阶乘的情形一样，我们可以很容易地写出一个等价的线性迭代：
This version requires Θ
(
n
) steps and Θ
(
1
) space.
这个版本需要 Θ
(
n
) 步和 Θ
(
1
) 的空间。
We can compute exponentials in fewer steps by using successive squaring. For
instance, rather than computing b
8 as
通过使用逐次平方法 (successive squaring)，我们可以用更少的步骤完成幂运算。例如，计算 b
8 时，与其按照
b
⋅
(
b
⋅
(
b
⋅
(
b
⋅
(
b
⋅
(
b
⋅
(
b
⋅
b
)
)
)
)
)
)
,
we can compute it using three multiplications:
这样计算，不如只用三次乘法来完成：
b
2
=
b
⋅
b
,
b
4
=
b
2
⋅
b
2
,
b
8
=
b
4
⋅
b
4
.
This method works fine for exponents that are powers of 2. We can also take
advantage of successive squaring in computing exponentials in general if we use
the rule
这一方法对于指数为 2 的幂次的情形运作良好。事实上，若采用如下规则，反复平方法同样适用于一般的乘幂计算：
b
n
=
(
b
n
/
2
)
2
if
若
n
is even
,
为偶数
，
b
n
=
b
⋅
b
n
−
1
if
若
n
is odd
.
为奇数
。
We can express this method as a procedure:
我们可以将这一方法表示为如下过程：
where the predicate to test whether an integer is even is defined in terms of
the primitive procedure remainder by
其中，判断一个整数是否为偶数的谓词，借助基本过程 remainder 定义如下：
The process evolved by fast-expt grows logarithmically with n in
both space and number of steps. To see this, observe that computing
b
fast-expt 所展开的计算过程，在空间和步数上均随 n 对数增长。为了理解这一点，注意到用 fast-expt 计算 b
2
n using fast-expt requires only one more multiplication
than computing b
n. The size of the exponent we can compute therefore
doubles (approximately) with every new multiplication we are allowed. Thus,
the number of multiplications required for an exponent of n grows about as
fast as the logarithm of n to the base 2. The process has
Θ
(
log
n
) growth.
2
n 只需比计算 b
n 多做一次乘法。因此，每多允许一次乘法，我们能够计算的指数大小便（近似地）翻倍。于是，计算指数为 n 的乘幂所需的乘法次数，其增长速度约与以 2 为底 n 的对数相当。该计算过程具有 Θ
(
log
n
) 的增长阶。
The difference between Θ
(
log
n
) growth and
Θ
(
n
) growth becomes striking as n becomes large. For
example, fast-expt for n = 1000 requires only 14
multiplications. It is also possible to
use the idea of successive squaring to devise an iterative algorithm that
computes exponentials with a logarithmic number of steps (see Exercise 1.16),
although, as is often the case with iterative algorithms, this is not
written down so straightforwardly as the recursive algorithm.
随着 n 的增大，Θ
(
log
n
) 增长与 Θ
(
n
) 增长之间的差异愈发显著。例如，对于 n = 1000，fast-expt 仅需 14 次乘法。此外，同样可以借助反复平方的思路，设计一个以对数步数计算乘幂的迭代算法（见练习 1.16）；不过，正如迭代算法常见的情形，这一写法不如递归算法那样直截了当。
(define (expt b n)
(if (= n 0)
1
(* b (expt b (- n 1)))))(define (expt b n)
(expt-iter b n 1))
(define (expt-iter b counter product)
(if (= counter 0)
product
(expt-iter b
(- counter 1)
(* b product))))(define (fast-expt b n)
(cond ((= n 0)
1)
((even? n)
(square (fast-expt b (/ n 2))))
(else
(* b (fast-expt b (- n 1))))))(define (even? n)
(= (remainder n 2) 0))