Exercise 1.16: Design a procedure that evolves
an iterative exponentiation process that uses successive squaring and uses a
logarithmic number of steps, as does fast-expt. (Hint: Using the
observation that (
b
n
/
2
)
2
=
(
b
2
)
n
/
2, keep, along with
the exponent n and the base b, an additional state variable a, and
define the state transformation in such a way that the product a
b
n
is unchanged from state to state. At the beginning of the process
a is taken to be 1, and the answer is given by the value of a at the
end of the process. In general, the technique of defining an
invariant quantity that remains unchanged from state to state is a
powerful way to think about the design of iterative algorithms.)
练习 1.16：请设计一个过程，使其产生一个迭代型幂运算计算过程，该过程采用逐次平方的方式，步骤数与 fast-expt 一样是对数级的。（提示：利用观察 (b^(n/2))² = (b²)^(n/2)，在保存指数 n 和底数 b 的同时，再维护一个附加的状态变量 a，并以如下方式定义状态变换：使得乘积 a·bⁿ 在状态转换过程中保持不变。在计算过程开始时 a 取值为 1，答案由计算过程结束时 a 的值给出。一般而言，定义一个从状态到状态保持不变的不变量 (invariant quantity)，是思考迭代算法设计的一种有力方式。）