Problem: Given a number and a non-negative integer exponent, possibly quite large, raise the number to the power expressed by the exponent.
One could of course use iterated multiplication:
(define power
(lambda (base exponent)
(let loop ((rest exponent)
(result 1))
(if (zero? rest)
result
(loop (- rest 1) (* base result))))))
But for large exponents it is possible to reduce the amount of computation
by using squaring to compute just those powers of the base whose exponents
are powers of 2, obtaining the final result by multiplying together
selected powers from this series (powers selected, in effect, by examining
the binary numeral for exponent).
(define power
(lambda (base exponent)
(let loop ((rest exponent)
(result 1)
(squaring base))
(if (zero? rest)
result
(loop (quotient rest 2)
(if (odd? rest)
(* result squaring)
result)
(* squaring squaring))))))
Actually, Scheme provides a built-in expt procedure, which
should make an exponentiation algorithm unnecessary, particularly since the
standard requires that when expt receives exact operands, it
should return an exact value whenever the mathematically expected result is
exactly representable (e.g., when the base is an exact rational and
the exponent an exact integer, provided that the base is non-zero or the
exponent non-negative).
This document is available on the World Wide Web as
http://www.math.grin.edu/~stone/events/scheme-workshop/exponentiation.html