Java Reference
In-Depth Information
• There are 2
k
instances of length k or less.
• The size (length) of value n is log n.
• The cost of a particular algorithm can decrease when n increases in value
(say when going from a value of 2
k
1 to 2
k
to 2
k
+ 1), but generally
increases when n increases in length.
16.3.1
Exponentiation
We will start our examination of standard numerical algorithms by considering how
to perform exponentiation. That is, how do we compute m
n
? We could multiply
by m a total of n 1 times.
Can we do better?
Yes, there is a simple divide
and conquer approach that we can use.
We can recognize that, when n is even,
m
n
= m
n=2
m
n=2
.
If n is odd, then m
n
= m
bn=2c
m
bn=2c
m.
This leads to the
following recursive algorithm
intPower(base,exp){
ifexp=0return1;
inthalf=Power(base,exp/2);//integerdivisionofexp
half=half
*
half;
if(odd(exp))thenhalf=half
*
base;
returnhalf;
}
Function
Power
has recurrence relation
0 n = 1
f(bn=2c) + 1 + n mod 2 n > 1
f(n) =
whose solution is
f(n) = blog nc + (n) 1
where is the number of 1's in the binary representation of n.
How does this cost compare with the problem size? The original problem size
is log m + log n, and the number of multiplications required is log n. This is far
better (in fact, exponentially better) than performing n 1 multiplications.
16.3.2
Largest Common Factor
We will next present Euclid's algorithm for finding the largest common factor
(LCF) for two integers.
The LCF is the largest integer that divides both inputs
evenly.
First we make this observation: If k divides n and m, then k divides nm. We
know this is true because if k divides n then n = ak for some integer a, and if k
divides m then m = bk for some integer b. So, LCF(n;m) = LCF(nm;n) =
LCF(m;nm) = LCF(m;n).
