# Euclidean algorithm (Prolog)

Other implementations: C | Erlang | Forth | Haskell | Java | Java, recursive | OCaml | Prolog | Python | Scala | Standard ML

This page explains how to implement the Euclidean algorithm in Prolog. The Euclidean algorithm determines the greatest common divisor (gcd) of two integers without factoring. Although the Euclidean algorithm can be extended to compute the gcd of any Euclidean domain elements such as polynomials over a field, this article only deals with the case when the input is integer.

## Simple version

### Source code

```<<gcd_simple.pl>>=
gcd(X, Y, G) :- X = Y, G = X.
gcd(X, Y, G) :-
X < Y,
Y1 is Y - X,
gcd(X, Y1, G).
gcd(X, Y, G) :- X > Y, gcd(Y, X, G).
```

### Execution result

The simple version works well. However, it fails to compute `gcd(4, 19827345)` as it takes too many steps to reduce 19827345 to a small number by repeatedly subtracting 4.

```crypto@crypto ~/gcd
\$ prolog
Welcome to SWI-Prolog (Multi-threaded, Version 5.2.6)
Copyright (c) 1990-2003 University of Amsterdam.
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.
For help, use ?- help(Topic). or ?- apropos(Word).
?- ['gcd_simple.pl'].
% gcd_simple.pl compiled 0.00 sec, 1,032 bytes
Yes
?- gcd(4, 8, X).
X = 4
Yes
?- gcd(15, 120, X).
X = 15
Yes
?- gcd(4, 19827345, X).
ERROR: Out of local stack
Exception: (29,873) gcd(4, 19707881, _G19) ? abort
% Execution Aborted
?-
```

## Tricky version

### Algorithm

We employ the modulo operator `mod` rather than the repeated subtraction. Unlike the previous case, we have to test whether -- in this case, x is the gcd.

### Source code

```<<gcd.pl>>=
gcd(X, Y, G) :- X = Y, G = X.
gcd(X, Y, G) :-
X < Y,
Y1 is Y mod X,
(Y1 = 0 -> G = X; gcd(X, Y1, G)).
gcd(X, Y, G) :- X > Y, gcd(Y, X, G).
```

### Execution result

The tricky version can easily compute `gcd(4, 19827345)` because it employs the modulo operator `mod` without resorting to the repeated subtraction.

```crypto@crypto ~/gcd
\$ prolog
Welcome to SWI-Prolog (Multi-threaded, Version 5.2.6)
Copyright (c) 1990-2003 University of Amsterdam.
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.
For help, use ?- help(Topic). or ?- apropos(Word).
?- ['gcd.pl'].
% gcd.pl compiled 0.00 sec, 1,040 bytes
Yes
?- gcd(4, 19827345, X).
X = 1
Yes
```