

Algorithm: a process or set of rules
used for calculation or problemsolving, esp. with a computer. ExampleProblem:
Find the greatest common divisor (GCD) of two integers, m and n. while m is greater than zero: If n is greater than m, swap m & n. Subtract n from m. n is the GCDProgram (in C): int gcd(int m, int n) /* precondition: m>0 & n>0. Let g=gcd(m,n). */ { while( m > 0 ) { /* invariant: gcd(m,n)=g */ if( n > m ) /* swap */ { int t=m; m=n; n=t; } /* m >= n > 0 */ m = n; } return n; } CorrectnessWhy do we believe that this algorithm devised thousands of years ago, is correct? Given m>0 and n>0, let g = gcd(m,n). So the algorithm is correct, provided that it terminates. TerminationAt the start of each iteration of the loop,
either n>m or m≥n. So the algorithm does terminate. TestingHaving proved the algorithm to be correct, one might argue that there is no need to test it. But there might be an error in the proof or maybe the program has been coded wrongly. Good test values would include:
Debugging code be inserted to print the values of m and n at the end of each iteration to confirm that they behave as expected. ComplexityWe are interested in how much time and space (computer memory)
a computer algorithm uses; TimeThe time to execute one iteration of the loop depends on whether m>n or not, but both cases take constant time: one test, a subtraction and 4 assignments v. one test, a subtraction and one assignment. So the time taken for one iteration of the loop is bounded by a constant. The real question then is, how many iterations take place? The answer depends on m and n. If m=n, there is just one iteration; this is the bestcase. SpaceThe spacecomplexity of Euclid's algorithm is a constant,
just space for three integers: m, n Exercises


↑ © L. Allison, www.allisons.org/ll/ (or as otherwise indicated). Created with "vi (Linux)", charset=iso88591, fetched Tuesday, 28May2024 22:43:25 UTC. Free: Linux, Ubuntu operatingsys, OpenOffice officesuite, The GIMP ~photoshop, Firefox webbrowser, FlashBlock flash on/off. 