Algorithms in a Nutshell

Mix of Operations | 35

AlgorithmsThe Math of

Even though the MODGCD implementation outperforms the corresponding GCD

implementation by nearly 60%, the performance of MODGCD isquadratic,or

O(n^2 ), whereas GCD is exponential. That is, the worst-case performance of GCD

(not exhibited in this small input set) is orders of magnitude slower than the

worst-case performance of MODGCD.

More sophisticated algorithms for computing GCD have been designed—though

most are impractical except for extremely large integers—and analysis suggests

that the problem allows for more efficient algorithms.

Mix of Operations

As described earlier in the sidebar “The Effect of Encoding on Performance,” a

designer will have to consider multiple operations simultaneously. Not every

operation can be optimized; in fact, optimizing one operation may degrade the

execution of another operation. As an example, consider a data structure that

contains operationsop1andop2. Assume that there are two different ways by

which the data structure can be implemented,AandB. For the purposes of this

discussion, it is not important to know anything about the data structure or the

individual methods. We construct two scenarios:

Small data sets

On a base size ofn=1,000 elements, mix together 2,000op1operations with

3,000op2 operations.

Large data sets

On a base size ofn=100,000 elements, mix together 200,000op1operations

with 300,000op2 operations.

Table 2-6 contains the expected result of executing implementationsAandBon

these two data sets. The first row of the table shows that the average cost of

performingop1on implementationAwithn=1,000 sized data is assumed to be

0.008 milliseconds; the other values in the second and third columns should be

interpreted similarly. The final column reflects the total expected time of execu-

tion; thus, for optionAonn=1,000 sized data, we expect the time to be

2,000*0.008+3,000*0.001=16+3=19 milliseconds. Although implementationB

initially outperforms theAimplementation for small values ofn, the situation

changes dramatically when the scale of the problem increases by two orders of

magnitude. Note how alternativeAscales well, whereas optionBperforms

horribly.

16 2,953 6,406 0.087 0.040 2.82 3.23

32 8,812 18,609 0.116 0.055 2.98 2.90

64 29,891 83,921 0.137 0.049 3.39 4.51

128 106,516 321,891 0.154 0.051 3.56 3.84

Table 2-5. Time (in milliseconds) to execute 10,011 gcd computations (continued)

n modgcd gcd n^2 /modgcd n^2 /gcd

modgcd 2 n/

modgcdn gcd 2 n/gcdn

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