You are to run a series of trials. For each trial you will pick a random number between 1 and . Call this number . You will run tests with this number . For each test you will pick a second random number between 1 and ; call this second number . Run each of the two GCD algorithms (Euclid and Consecutive Integer Checking) against and . Keep track of the number of basic operations -- modular divisions -- for each of these runs. Average the number of basic operations for each of these tests and save this result.
For your analysis, you will be trying to estimate the average-case time efficiency of each algorithm, in terms of a count of the number of basic operations. In other words, you will be trying to determine a function C(n) for each algorithm. We will be using , the magnitude of the larger number, as the input size for the algorithms.
To do this analysis, I would suggest you output pairs of numbers. (Each pair will consist of the number and the average number of basic operations you determined for that .) You should sort this list, calculate the ratios C(n)/g(n) for a variety of g(n)'s, where g(n) represents the simplest function in one of the basic efficiency classes. Try to determine an actual function, C(n), for each algorithm, including constant factors. Show your work and justification: you will be graded on this. For example, it would be good to calculate a "percentage error" for your function, and get a sense of whether this error increases or descreases as gets large.
Set up , , and as variables, declared and set in one place at the top of your program, so these parameters are easily changable. At this point, use:
int numTrials = 100;
int numTests = 100;
int maxRand = 100000;
If you have a problem getting good results wth these parameters, try different ones. Post a message and let us know if you were able to get good results.
my code:
driver:
final int NUMTRIALS = 100;
final int NUMTESTS = 100;
double[][] results = new double[100][3];
for (int i=0; iconsecutive integer checking algorithm for computing gcd(m,n)
step 1 assign the value of min{m,n} to t
step 2 divide m by t. if the remainder of this division is 0, go to step 3; otherwise go to step 4
step 3 divide n by t. if the remainder of this divisor is 0, return the value of t as the answer and stop; otherwise proceed to step 4
step 4 decrease the value of t by 1, go to step 2
</DIV></DIV>
