% ==========================================================================
% $Id: gcd.pl,v 1.1 2014/01/16 04:33:39 jlang Exp $
% CSI2120 example Code for lecture 3
% ==========================================================================
% (C)opyright:
%
%   Robert Laganiere
%   EECS, University of Ottawa
%   800 King Edward Ave.
%   Ottawa, On., K1N 6N5
%   Canada. 
%   http://www.eecs.uottawa.ca/~jlang
% 
% Creator: jlang (Jochen Lang)
% Email:   jlang@eecs.uottawa.ca
% ==========================================================================
% $Log: gcd.pl,v $
% Revision 1.1  2014/01/16 04:33:39  jlang
% Added code for lecture 3
%
% ==========================================================================
gcd(U,0,U).
gcd(U,V,W) :- V>0, 
	R is U mod V,
	gcd(V,R,W).

% Alternative implementation
gcdAlt(A,A,A).
gcdAlt(A,B,GCD):- A<B, NB is B-A, gcdAlt(A,NB,GCD).
gcdAlt(A,B,GCD):- A>B, NA is A-B, gcdAlt(NA,B,GCD).