Greatest Common Divisor in Prolog

I am writing this because it's interesting and useful in seeing how Arithmetic can work in Prolog. It's from the Ivan Bratko book, Prolog Programming for Artificial Intelligence.

It's a great book.

Given two positive integers X and Y, their greatest common divisor, D, can be found according to three cases:

1. If X and Y are equal then D is equal to X.
2. If X < Y then D is equal to the greatest common divisor of X and the difference Y - X.
3. If Y < X then do the same as (2.) with X and Y interchanged.

The rules can be expressed as a Prolog program by defining a three argument relation:

gcd( X, Y, D).

The three rules are then expressed as three clauses:

gcd( X,X,X).

gcd( X, Y, D) :-
   X < Y,
  Y1 is Y - X,
  gcd( X, Y1, D).

gcd( X, Y, D) :-
  Y < X,
  gcd( Y, X, D).

To me this was not immediatly apparent and I had not seen it before so I worked through Ivan Bratko's  example just to confirm it worked. Lo-and-behold it does.


scenario 1. X = 20 and Y = 25
So with this example, The greatest common divisor is 5.
We just subtract our way down, something like this:

[trace] 1 ?- gcd(20, 25, D).
   Call: (6) gcd(20, 25, _G1990) ? creep
   Call: (7) 20<25 ? creep
   Exit: (7) 20<25 ? creep
   Call: (7) _G2066 is 25-20 ? creep
   Exit: (7) 5 is 25-20 ? creep
   Call: (7) gcd(20, 5, _G1990) ? creep
   Call: (8) 20<5 ? creep
   Fail: (8) 20<5 ? creep
   Redo: (7) gcd(20, 5, _G1990) ? creep
   Call: (8) 5<20 ? creep
   Exit: (8) 5<20 ? creep
   Call: (8) gcd(5, 20, _G1990) ? creep
   Call: (9) 5<20 ? creep
   Exit: (9) 5<20 ? creep
   Call: (9) _G2069 is 20-5 ? creep
   Exit: (9) 15 is 20-5 ? creep
   Call: (9) gcd(5, 15, _G1990) ? creep
   Call: (10) 5<15 ? creep
   Exit: (10) 5<15 ? creep
   Call: (10) _G2072 is 15-5 ? creep
   Exit: (10) 10 is 15-5 ? creep
   Call: (10) gcd(5, 10, _G1990) ? creep
   Call: (11) 5<10 ? creep
   Exit: (11) 5<10 ? creep
   Call: (11) _G2075 is 10-5 ? creep
   Exit: (11) 5 is 10-5 ? creep
   Call: (11) gcd(5, 5, _G1990) ? creep
   Exit: (11) gcd(5, 5, 5) ? creep
   Exit: (10) gcd(5, 10, 5) ? creep
   Exit: (9) gcd(5, 15, 5) ? creep
   Exit: (8) gcd(5, 20, 5) ? creep
   Exit: (7) gcd(20, 5, 5) ? creep
   Exit: (6) gcd(20, 25, 5) ? creep
D = 5 .

The only maths bit is the
Y1 is Y - X 
but it shows how to use is It's a mathematical equals really.