Fast exponentiation

Design a procedure solution 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ⁿ୵²)² = (b²)ⁿ୵², 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 abⁿ 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.)


There are no comments yet.

Authentication required

You must log in to post a comment.

Login
(check-equal? (solution 10 0) 1)
(check-equal? (solution 3 20) (expt 3 20))
(check-equal? (solution 2 10) (expt 2 10))
(check-equal? (solution 0 5) 0)