Wednesday 1 May 2013

gcd by subtraction - execution of the program

In a previous post I provided a program for determining the greatest common divisor (gcd) of two positive integers. Trying out this program with 15 and 72, the two numbers that I discussed before, we find that on executing the program the display shows A? Enter 15 and press [EXE]. The display then show B? Enter 72 and press [EXE]. The display then shows 3 and this is the gcd of 15 and 72 as 3 is the largest positive integer that divides these two numbers. Pressing [EXE] again, takes you to the start of the program and this time you can enter 72 first and then 15 and the result is still 3. Note also that if you run the program with two numbers the same, 15 and 15 say, you will get an answer of 15 since obviously 15 is the largest number that divides this same pair of numbers.

This program is quite quick even with larger numbers. For example, running the program with the pair of numbers 8076 and 6378 we find that the gcd is 6. If you were to try and work this out by finding the prime factors of each of the numbers first (8076=22x3x673 and 6378=2x3x1063) it would take quite a bit of time! If the difference between the two numbers is large then the program is a bit slower.

Note also that there aren't any checks in the code to ensure that the numbers entered are positive integers. This can be added if required to make the program more secure. If you do get into an infinite loop (as for example by entering a negative integer) you can just press [AC] to get out of it.