Highest Common Factor

Another recent creation, this program prompts the user for two positive unequal integers and then determines the highest common factor, or greatest common divisor, of these numbers. If this equals 1, then it displays a message saying the numbers are co-prime.

At the heart of this is just 7 lines of BASIC, comprising a loop and two if IF statements. The code is an implementation of a simple yet rather ingenious and ancient set of instructions, essentially a program for human computers. It is known as Euclid's Algorithm and makes a first appearance in his Elements in about 300 BC, although it may be older than that. In it, a simple operation is repeated until a certain condition is met, at which point the answer is provided. It's something I must have forgotten about and it amazed me when I first saw it (again) recently.

To state it somewhat clumsily in words:

The smaller of the two numbers being considered is repeatedly subtracted from the larger one until a remainder, smaller than the smaller number, is left. At this point, the smaller number becomes the new larger number and the remainder becomes the new smaller number and the whole process is repeated until the remainder becomes zero. The smaller number at this time, is the highest common factor of the original numbers.

There is a verbose mode which shows the algorithm in operation - it can be enabled by un-commenting line 245. An example of the output is shown below.

It was while playing around with this verbose mode, that I realized that the algorithm - at least as stated above - is inefficient when the numbers are co-prime, as the example below shows. Once the difference between the two numbers becomes 1, as in the fourth line of the output, the hcf must be 1 and the routine can be terminated at this point rather than waiting for the remainder to become 0 nine lines later! No doubt, in practice this is what would have been done, even if not explicitly stated in the algorithm.

The code can be tweaked to achieve this by inserting the following line:

255 IF bn=1 THEN LET hcf=1: RETURN

Re-running the above example then produces the following:

This more efficient code will be very useful when run repeatedly as part of a larger program.