Greatest Common Divisor

check_determ
domains
  int  = integer
  ints = int*
predicates
  gcd(int,int,int)
  gcd_1(int,int,int)
  lcm(int,int,int)
  gcd_extended(int,int,int,int,int)
  gcd_extended_1(int,int,int,int,int,int,int,int,int)
  are_relatively_prime(ints)
  are_relatively_prime_1(ints,int)
clauses
  
/* gcd(X, Y, Z) is true if Z is the greatest common divisor of X and Y.    */
/*   e.g. gcd(24140, 16762, 34).                                           */
gcd(X, 0, X):-!.
gcd(X, Y, Z):-X1 = abs(X), Y1 = abs(Y), gcd_1(X1, Y1, Z).

gcd_1(X, 0, X):-!.
gcd_1(X, Y, Z):-R = X mod Y, gcd_1(Y, R, Z).

/* lcm(X, Y, Z) is true if Z is the lowest common multiple of X and Y.     */
/*   e.g. lcm(35, 45, 315).                                                */
lcm(X, Y, Z):-gcd(X, Y, T), Z = (X * Y) div T.

/* gcd_extended(X, Y, U1, U2, Z) is true if X*U1 + Y*U2 = Z = gcd(X, Y).   */
/*   e.g. gcd_extended(24140, 16762, -234, 337, 34).                       */
gcd_extended(X, Y, U1, U2, Z):-
  gcd_extended_1(Y, 1, 0,  X, 0, 1,  Z, U2, U1).

gcd_extended_1(0, _, _,  U3, U2, U1,  U3, U2, U1):-!.
gcd_extended_1(V3, V2, V1,  U3, U2, U1,  U3P, U2P, U1P):-
  Q  = U3 div V3,
  W3 = U3 mod V3,
  W2 = U2 - V2 * Q,
  W1 = U1 - V1 * Q,
  gcd_extended_1(W3, W2, W1,  V3, V2, V1,  U3P, U2P, U1P).

/* are_relatively_prime(Xs) is true if the elements of Xs are relatively   */
/*   prime to each other in pairs.                                         */
/* e.g. are_relatively_prime([6, 35, 143]) is true.                        */
are_relatively_prime([]).
are_relatively_prime([X|Xs]):-
  are_relatively_prime_1(Xs, X),
  are_relatively_prime(Xs).

are_relatively_prime_1([], _).
are_relatively_prime_1([X2|Xs], X1):-
  gcd(X1, X2, 1),
  are_relatively_prime_1(Xs, X1).

Turbo Prolog Index     Home Page