Tuesday, July 07, 2009

Adventures in Prolog - GCD and Coprime

Today's post follows the tradition of the my last post, i.e. it continues with another problem stated in the list of 99 Prolog problems. Today, we are going to have a look at problem 32 and 33.

Problem 32 concerns the implementation of a greatest common divisor predicate (gcd). In an earlier post, I implemented a gcd routine in Python. We are going to reuse this definition of gcd here, using a ternary predicate/relation.

The Prolog definition of gcd makes use of gcd's recursive definition, which are:
  1. the gcd of two numbers x and y is equal to the gcd of x - y and y for y <>
  2. the gcd of some number and 0 is the number
  3. the gcd of some number and 1 is 1

Now, given the above properties (and some more) a possible gcd predicate might look like this:


gcd(A, 0, A) :- !. %includes gcd(0,0)
gcd(1, _, 1) :- !.
gcd(A, A, A) :- !.

gcd(A, B, GCD) :-
A < B, !,
X is B - A,
gcd(X, A, GCD).

gcd(A, B, GCD) :-
X is A - B,
gcd(X, B, GCD).


Provided the above definition of gcd, the solution to problem P33 is given within the problem statement. For this, a predicate to determine coprimality may be defined as is:

coprime(X, X) :- fail.
coprime(X, Y) :- gcd(X, Y, 1).

Clearly, we could add more clause to avoid a computation of gcd when it is obviously not necessary. However this was omitted here.

No comments: