The greatest common divisor (gcd) of two or more numbers is the largest number that divides into all of them, for example the gcd of 72 and 48 is 24.
To find the gcd of two numbers we can do something like this:
96, 120:
120-96=24
96-24=72
72-24=48
48-24=24
24-24=0
In other words, perform repeated subtraction until the result is zero. The gcd is given by the values in the last line. To perform the correct subtraction we could test to see which is the greater of the two numbers:
if a > b then result:= a - b else result:= b - a;
A more compact approach is to use the abs() function, which strips out the sign of a result:
result := abs(a-b)
(abs(120-96)=72 and abs(96-120)=72)
For each iteration we need to switch the variables over, setting the first variable (a) to the value of b and the setting the second variable (b) to the value of the result (a-b):
result := abs(a-b);
a:=b;
b:=result;
We could then place our line of code inside a repeat loop:
a:=strtoint(edit1.text)
b:=strtoint(edit2.text)
begin
repeat
result := abs(a-b);
a:=b;
b:=result;
until result = 0;
if a = 1 then showmessage ('No gcd other apart from 1')
else showmessage('gcd is ' + inttostr(a);
end;
The algorithm is speeded up considerably by using mod in place of subtraction, for instance:
120 mod 96 = 24
96 mod 24 = 0
This is just two cycles instead of five for subtraction, and we don't need abs().
A solution using this approach is given in the notes on Pascal.
We can put this logic into a recursive function as follows:
function gcd (a,b:integer):integer;
var c: integer;
begin
c:= a mod b;
if c = 0 then gcd := a
else gcd:=gcd(b,c)
end;
The function takes two initial values (120,96) and sets a variable c to equal a mod b (24 in this case). Now 24 is not 0 so the else part of the next line is chosen. This line sets the result of the function gcd to the result of another call of the function. In other words, the function calls itself. The additional trick here is that the function is called again with parameters b and c (92 and 24 in this case) so there is no need to assign them as in the previous solution (a:=b; b:=c).
Recursion produces elegant solutions but they may not be very efficient. There is an algorithm for finding Fibonacci numbers that uses recursion but it is not very efficient. On the other hand the QuickSort method uses recursion and is generally thought to be a very quick and efficient sorting method.