Java Reference
In-Depth Information
Now, for any value n there exists k and l such that
n = km + l where m > l 0:
From the definition of the mod function, we can derive the fact that
n = bn=mcm + n mod m:
Since the LCF is a factor of both n and m, and since n = km + l, the LCF must
therefore be a factor of both km and l, and also the largest common factor of each
of these terms. As a consequence, LCF(n;m) = LCF(m;l) = LCF(m;n mod
m).
This observation leads to a simple algorithm. We will assume that n m. At
each iteration we replace n with m and m with n mod m until we have driven m
to zero.
intLCF(intn,intm){
if(m==0)returnn;
returnLCF(m,n%m);
}
To determine how expensive this algorithm is, we need to know how much
progress we are making at each step. Note that after two iterations, we have re-
placed n with n mod m.
So the key question becomes: How big is n mod m
relative to n?
n m ) n=m 1
) 2bn=mc > n=m
) mbn=mc > n=2
) nn=2 > nmbn=mc = n mod m
) n=2 > n mod m
Thus, function LCF will halve its first parameter in no more than 2 iterations.
The total cost is then O(log n).
16.3.3 Matrix Multiplication
The standard algorithm for multiplying two nn matrices requires (n
3
) time.
It is possible to do better than this by rearranging and grouping the multiplications
in various ways. One example of this is known as Strassen's matrix multiplication
algorithm.
For simplicity, we will assume that n is a power of two. In the following, A
and B are nn arrays, while A
ij
and B
ij
refer to arrays of size n=2n=2. Using
