Just a quick recap first: On Friday's lecture (January 10th) we utilized Euclidean algorithm. As mentioned in the class, the basic principle of said algorithm is that the GCD(Greatest Common Divisor) of two unique positive numbers is the same as the GCD of the greater number minus the lesser and the lesser number. For example, GCD(10,9) = GCD(10 - 9 = 1, 9). This means one can find the GCD of two unique positive numbers by continuously subtracting the lesser number from the greater until they are equal; once they are equal you know the GCD (since the GCD of x and x is x).
For those of you who took Mathematical Proofs(MAT102), you will remember Euclidean's algorithm being slightly different. In MAT102, the main principle was that the GCD of two numbers in the same as the GCD of the remainder (when dividing the greater number by the lesser) and the lesser number. You can thus work it down to when the remainder becomes 0 and thus determine the GCD (the now lesser number).
Interestingly, the method used in MAT102 is more efficient. As proven by Gabriel Lamé in 1844, it will never take more iterations than five times the number of digits. This means it will take a maximum of 15 iterations to determine GCD(100, 1) while the prior method would take 100 iterations.
I'm not entirely sure why Euclidean subtraction seemsto be used more in CS (in the CSC108 textbook and CSC148 lecture), but I thought the difference was rather interesting. If someone wants to shed some light on why the prior algorithm appears dominant, I'd be more than happy to know in the comments. My best guess is the prior one is simpler to understand and that neither CSC108 or 148 are math-oriented courses.
No comments:
Post a Comment