Algorithms in a Nutshell

(^34) | Chapter 2: The Mathematics of Algorithms
MODGCD will arrive at a solution more rapidly because it won’t waste time
subtracting really small numbers from large numbers within thewhileloop. This
difference is not simply an implementation detail; it reflects a fundamental shift in
how the algorithm approaches the problem.
The computations shown in Figure 2-7 (and enumerated in Table 2-5) show the
result of generating 142 randomn-digit numbers and computing the greatest
common divisor of all 10,011 pairs of these numbers.
while (!isZero(b)) {
int [] t = copy (b);
divide (a, b, quot, remainder);
assign (b, remainder);
assign (a, t);
}
// value held in a is the computed gcd of (a,b).
assign (gcd, a);
}
Figure 2-7. Comparison of gcd versus modgcd
Table 2-5. Time (in milliseconds) to execute 10,011 gcd computations
n modgcd gcd n^2 /modgcd n^2 /gcd
modgcd 2 n/
modgcdn gcd 2 n/gcdn
2 234 62 0.017 0.065
4 391 250 0.041 0.064 1.67 4.03
8 1,046 1,984 0.061 0.032 2.68 7.94
Example 2-6. ModGCD algorithm for GCD computation (continued)
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use