Euclidean algorithm (Prolog)
From LiteratePrograms
- 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.
Contents |
Simple version
Algorithm
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
| Download code |