Greatest Common Divisor

/* 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 is abs(X), Y1 is abs(Y), gcd_1(X1, Y1, Z).

gcd_1(X, 0, Z):-!, Z = X.
gcd_1(X, Y, Z):-R is 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 is (X * Y) // 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  is U3 // V3,
  W3 is U3 mod V3,
  W2 is U2 - V2 * Q,
  W1 is 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).

LPA Index     Home Page

Valid HTML 4.0!