Java Reference
In-Depth Information
i--;
}
}
// Now r equals a to the nth power
Consider the case
n
= 100. The method performs the steps shown in the table
below.
Amazingly enough, the algorithm yields exactly
a
100
. Do you understand why?
Are you convinced it will work for all values of
n
? Here is a clever argument to
show that the method always computes the correct result. It demonstrates that
whenever the program reaches the top of the
while
loop, it is true that
b
i
a
n
r
=
Certainly, it is true the first time around, because
b = a
and
i = n
. Suppose
that (I) holds at the beginning of the loop. Label the values of
r
,
b
, and
i
as Ȓoldȓ
when entering the loop, and as Ȓnewȓ when exiting the loop. Assume that upon
entry
i
old
a
n
r
old
b
old
=
261
262
Computing a
100
b
i
r
a
100
1
a
2
50
a
4
25
24
a
4
a
8
12
a
16
6
a
32
3
2
a
36
a
64
1
0
a
100
In the loop you must distinguish two cases:
i
old
even and
i
old
odd. If
i
old
is even,
the loop performs the following transformations:
