Discrete Mathematics for Computer Science

Strong Form of Mathematical Induction 73

INPUT: A nonzero real number x and a natural number n

OUTPUT: The value of xn

FastPower(x, n) 1* The initial call */

FastPower (base, expont) 1* The recursive procedure */

if (expont = 0) then

return 1

else

if (expont is odd) then

return base .FastPower(base .base, (expont - 1)/2)

else

return FastPower(base .base, expont/2)

The algorithm presented uses a programming feature called recursion. In this algo-

rithm, a call to the algorithm FastPower is part of its own code. In a programming language

that supports this feature, the compiler will keep track of which version of FastPower is

being executed and which values should be used for the arguments. For more details about

how recursion is implemented in a programming language, the reader should consult a

manual for a language such as Java, C, or C++.

The reader should trace through the algorithm by hand for some sample values of

base and expont. For example, a computer executing this algorithm to compute 25 will go

through the following steps:

FastPower(2, 5) identifies 5 as odd and computes

2 .FastPower(2.2, (5 - 1)/2) = 2 .FastPower(4, 2)

To execute FastPower(4, 2) requires the execution of

FastPower(4.4, 2/2) = FastPower(16, 1)

Now, expont = 1 is odd, so the program computes

16. FastPower(16.16, (1 - 1)/2) = 16. FastPower(256, 0)

When FastPower(256, 0) is executed, the program starts the return process. Fast-
Power(256, 0) returns 1 to FastPower(16, 1). The returning value using FastPower(16, 1)
is 16 .FastPower(16, 1) = 16. This value is FastPower(4, 2), which must be multiplied by
2 before that value is returned to FastPower(2, 5). Thus, FastPower(2, 5) = 32.
The flow of control for this example is shown in Figure 1.19 on page 74.
Even though the example computation for 25 works correctly, it is, however, not quite
obvious that the FastPower algorithm correctly calculates powers for every nonzero base