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:
- the gcd of two numbers x and y is equal to the gcd of x - y and y for y <>
- the gcd of some number and 0 is the number
- 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:
Post a Comment