program for finding Gcd in Prolog

Question

I tried to write a code in Prolog for finding GCD (without using modulo) can anyone tell me what's wrong with this program?

gcd(X,Y,Z):- X>=Y, X1=X-Y, gcd(X1,Y,Z).
gcd(X,Y,Z):- X<Y, X1=Y- X, gcd(X1,X,Z).
gcd(0,X,X):- X>0.

Answer 1

As to why the original implementation doesn't work, there are two reasons:

The predicate =/2 is for unification, not arithmetic assignment

The expression X1 = X - Y doesn't subtract Y from X and store the result in X1. Rather, it unifies X1 with the term, -(X,Y). If, for example, X=5 and Y=3, then the result would be, X1=5-3, not X1=2. The solution is to use is/2 which assigns evaluated arithmetic expressions: X1 is X - Y.

Other predicates, besides the base case predicate, successfully match the base case

The clause, gcd(0,X,X) :- X > 0. is a reasonable base case, but it is never attempted because the second clause (gcd(X,Y,Z):- X<Y,...) will always successfully match the same conditions first, leading to infinite recursion and a stack overflow.

One way to fix this is to move the base case to the first clause, and use a cut to avoid backtracking after it successfully executes:

gcd(0, X, X):- X > 0, !.
gcd(X, Y, Z):- X >= Y, X1 is X-Y, gcd(X1,Y,Z).
gcd(X, Y, Z):- X < Y, X1 is Y-X, gcd(X1,X,Z).

This will work now:

| ?- gcd(10,6,X).

X = 2 ? ;

(1 ms) no
| ?- gcd(10,5,X).

X = 5 ? ;

no

(NOTE: the "no" here means no more solutions found after finding the first one)

---

ADDENDUM

There are still a couple of remaining "gaps" in the above implementation. One is that it doesn't handle gcd(0, 0, R) gracefully (it overflows). Secondly, it doesn't handle negative values. One possible solution would be to elaborate these cases:

gcd(X, Y, Z) :-
    X < 0, !,
    gcd(-X, Y, Z).
gcd(X, Y, Z) :-
    Y < 0, !,
    gcd(X, -Y, Z).
gcd(X, 0, X) :- X > 0.
gcd(0, Y, Y) :- Y > 0.
gcd(X, Y, Z) :-
    X > Y, Y > 0,
    X1 is X - Y,
    gcd(Y, X1, Z).
gcd(X, Y, Z) :-
    X =< Y, X > 0,
    Y1 is Y - X,
    gcd(X, Y1, Z).