Greatest common divisor
From Rosetta Code
You are encouraged to solve this task according to the task description, using any language you may know.
This task requires the finding of the greatest common divisor of two integers.
[edit] ActionScript
//Euclidean algorithm
function gcd(a:int,b:int):int
{
var tmp:int;
//Swap the numbers so a >= b
if(a < b)
{
tmp = a;
a = b;
b = tmp;
}
//Find the gcd
while(b != 0)
{
tmp = a % b;
a = b;
b = tmp;
}
return a;
}
[edit] Ada
with Ada.Text_Io; use Ada.Text_Io;
procedure Gcd_Test is
function Gcd (A, B : Integer) return Integer is
begin
if A = 0 then
return B;
end if;
if B = 0 then
return A;
end if;
if A > B then
return Gcd(B, A mod B);
else
return Gcd(A, B mod A);
end if;
end Gcd;
begin
Put_Line("GCD of 100, 5 is" & Integer'Image(Gcd(100, 5)));
Put_Line("GCD of 5, 100 is" & Integer'Image(Gcd(5, 100)));
Put_Line("GCD of 7, 23 is" & Integer'Image(Gcd(7, 23)));
end Gcd_Test;
Output:
GCD of 100, 5 is 5 GCD of 5, 100 is 5 GCD of 7, 23 is 1
[edit] ALGOL 68
Works with: ALGOL 68 version Revision 1 - no extensions to language used
Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny
PROC gcd = (INT a, b) INT: (
IF a = 0 THEN
b
ELIF b = 0 THEN
a
ELIF a > b THEN
gcd(b, a MOD b)
ELSE
gcd(a, b MOD a)
FI
);
test:(
INT a = 33, b = 77;
printf(($x"The gcd of"g" and "g" is "gl$,a,b,gcd(a,b)));
INT c = 49865, d = 69811;
printf(($x"The gcd of"g" and "g" is "gl$,c,d,gcd(c,d)))
)
Output:
The gcd of +33 and +77 is +11 The gcd of +49865 and +69811 is +9973
[edit] APL
Works with: Dyalog APL
33 49865 ∨ 77 69811 11 9973
If you're interested in how you'd write GCD in Dyalog, if Dyalog didn't have a primitive for it, (i.e. using other algorithms mentioned on this page: iterative, recursive, binary recursive), see different ways to write GCD in Dyalog.
Works with: APL2
⌈/(^/0=A∘.|X)/A←⍳⌊/X←49865 69811 9973
[edit] AWK
The following scriptlet defines the gcd() function, then reads pairs of numbers from stdin, and reports their gcd on stdout.
$ awk 'func gcd(p,q){return(q?gcd(q,(p%q)):p)}{print gcd($1,$2)}'
12 16
4
22 33
11
45 67
1
[edit] AutoHotkey
contributed by Laszlo on the ahk forum
GCD(a,b) {
Return b=0 ? Abs(a) : Gcd(b,mod(a,b))
}
[edit] Batch File
Recursive method
:: gcd.cmd
@echo off
:gcd
if "%2" equ "" goto :instructions
if "%1" equ "" goto :instructions
if %2 equ 0 (
set final=%1
goto :done
)
set /a res = %1 %% %2
call :gcd %2 %res%
goto :eof
:done
echo gcd=%final%
goto :eof
:instructions
echo Syntax:
echo GCD {a} {b}
echo.
[edit] BASIC
Works with: QuickBasic version 4.5
[edit] Iterative
FUNCTION gcd(a%, b%)
IF a > b THEN
factor = a
ELSE
factor = b
END IF
FOR l = factor TO 1 STEP -1
IF a MOD l = 0 AND b MOD l = 0 THEN
gcd = l
END IF
NEXT l
gcd = 1
END FUNCTION
[edit] Recursive
FUNCTION gcd(a%, b%)
IF a = 0 gcd = b
IF b = 0 gcd = a
IF a > b gcd = gcd(b, a MOD b)
gcd = gcd(a, b MOD a)
END FUNCTION
[edit] Bc
Works with: GNU bc Translation of: C
Utility functions:
define even(a)
{
if ( a % 2 == 0 ) {
return(1);
} else {
return(0);
}
}
define abs(a)
{
if (a<0) {
return(-a);
} else {
return(a);
}
}
Iterative (Euclid)
define gcd_iter(u, v)
{
while(v) {
t = u;
u = v;
v = t % v;
}
return(abs(u));
}
Recursive
define gcd(u, v)
{
if (v) {
return ( gcd(v, u%v) );
} else {
return (abs(u));
}
}
Iterative (Binary)
define gcd_bin(u, v)
{
u = abs(u);
v = abs(v);
if ( u < v ) {
t = u; u = v; v = t;
}
if ( v == 0 ) { return(u); }
k = 1;
while (even(u) && even(v)) {
u = u / 2; v = v / 2;
k = k * 2;
}
if ( even(u) ) {
t = -v;
} else {
t = u;
}
while (t) {
while (even(t)) {
t = t / 2;
}
if (t > 0) {
u = t;
} else {
v = -t;
}
t = u - v;
}
return (u * k);
}
[edit] Befunge
#v&< @.$<
:<\g05%p05:_^#
[edit] C/C++
[edit] Iterative Euclid algorithm
int
gcd_iter(int u, int v) {
int t;
while (v) {
t = u;
u = v;
v = t % v;
}
return u < 0 ? -u : u; /* abs(u) */
}
[edit] Recursive Euclid algorithm
int
gcd(int u, int v) {
if (v)
return gcd(v, u % v);
else
return u < 0 ? -u : u; /* abs(u) */
}
[edit] Iterative binary algorithm
int
gcd_bin(int u, int v) {
int t, k;
u = u < 0 ? -u : u; /* abs(u) */
v = v < 0 ? -v : v;
if (u < v) {
t = u;
u = v;
v = t;
}
if (v == 0)
return u;
k = 1;
while (u & 1 == 0 && v & 1 == 0) { /* u, v - even */
u >>= 1; v >>= 1;
k <<= 1;
}
t = (u & 1) ? -v : u;
while (t) {
while (t & 1 == 0)
t >>= 1;
if (t > 0)
u = t;
else
v = -t;
t = u - v;
}
return u * k;
}
[edit] Notes on performance
gcd_iter(40902, 24140) takes us about 2.87 µsec
gcd_bin(40902, 24140) takes us about 2.47 µsec
gcd(40902, 24140) takes us about 2.86 µsec
[edit] Clojure
(defn gcd
"(gcd a b) computes the greatest common divisor of a and b."
[a b]
(if (zero? b)
a
(recur b (mod a b)))) ; This is (gcd b (mod a b)), but with explicit tail call optimization.
[edit] C#
This is an Euclidean algorithm, translated from ActionScript.
static void Main(string[] args)
{
Console.WriteLine("GCD of {0} and {1} is {2}", 1, 1, gcd(1, 1));
Console.WriteLine("GCD of {0} and {1} is {2}", 1, 10, gcd(1, 10));
Console.WriteLine("GCD of {0} and {1} is {2}", 10, 100, gcd(10, 100));
Console.WriteLine("GCD of {0} and {1} is {2}", 5, 50, gcd(5, 50));
Console.WriteLine("GCD of {0} and {1} is {2}", 8, 24, gcd(8, 24));
Console.WriteLine("GCD of {0} and {1} is {2}", 36, 17, gcd(36, 17));
Console.WriteLine("GCD of {0} and {1} is {2}", 36, 18, gcd(36, 18));
Console.WriteLine("GCD of {0} and {1} is {2}", 36, 19, gcd(36, 19));
for (int x = 1; x < 36; x++)
{
Console.WriteLine("GCD of {0} and {1} is {2}", 36, x, gcd(36, x));
}
Console.Read();
}
private static int gcd(int a, int b)
{
int t;
// Ensure B > A
if (a > b)
{
t = b;
b = a;
a = t;
}
// Find
while (b != 0)
{
t = a % b;
a = b;
b = t;
}
return a;
}
Example output:
GCD of 1 and 1 is 1 GCD of 1 and 10 is 1 GCD of 10 and 100 is 10 GCD of 5 and 50 is 5 GCD of 8 and 24 is 8 GCD of 36 and 1 is 1 GCD of 36 and 2 is 2 .. GCD of 36 and 16 is 4 GCD of 36 and 17 is 1 GCD of 36 and 18 is 18 .. .. GCD of 36 and 33 is 3 GCD of 36 and 34 is 2 GCD of 36 and 35 is 1
[edit] Common Lisp
We call the function gcd2 so as not to conflict with common-lisp:gcd.
(defun gcd2 (a b)
(do ((n a)) ((zerop b) (abs a))
(shiftf n a b (mod n b))))
[edit] D
bool isEven(int number)
{
return number%2 == 0;
}
int gcd(int a, int b)
{
if(a == 0)
return b;
else if(b == 0)
return a;
else if(isEven(a) && isEven(b))
return gcd(a>>1, b>>1) << 1;
else if(isEven(a) && !isEven(b))
return gcd(a>>1, b);
else if(!isEven(a) && isEven(b))
return gcd(a, b>>1);
else if(a >= b)
return gcd(a-b, b);
return gcd(a, b-a);
}
[edit] E
Translation of: Python
def gcd(var u :int, var v :int) {
while (v != 0) {
def r := u %% v
u := v
v := r
}
return u.abs()
}
[edit] Emacs Lisp
(defun pgdc (a b)
(cond
((< a b) (pgdc a (- b a)))
((> a b) (pgdc (- a b) b))
(t a)))
[edit] Erlang
Translation of: OCaml
gcd(0,B) -> abs(B);
gcd(A,0) -> abs(A);
gcd(A,B) when A > B -> gcd(B, A rem B);
gcd(A,B) -> gcd(A, B rem A).
[edit] F#
Open System
let rec GCD (a:int) (b:int) =
match b with
| 0 -> Math.Abs(a)
| _ -> GCD b (a % b)
[edit] Factor
: gcd ( a b -- c )
[ abs ] [
[ nip ] [ mod ] 2bi gcd
] if-zero ;
[edit] FALSE
[[$][$@$@$@\/*-]#%]g:
10 15 g;!. { 5 }
[edit] Forth
: gcd ( a b -- n )
begin dup while tuck mod repeat drop ;
[edit] Fortran
Works with: Fortran version 95 and later
[edit] Recursive Euclid algorithm
recursive function gcd_rec(u, v) result(gcd)
integer :: gcd
integer, intent(in) :: u, v
if (mod(u, v) /= 0) then
gcd = gcd_rec(v, mod(u, v))
else
gcd = v
end if
end function gcd_rec
[edit] Iterative Euclid algorithm
subroutine gcd_iter(value, u, v)
integer, intent(out) :: value
integer, intent(inout) :: u, v
integer :: t
do while( v /= 0 )
t = u
u = v
v = mod(t, v)
enddo
value = abs(u)
end subroutine gcd_iter
A different version, and implemented as function
function gcd(v, t)
integer :: gcd
integer, intent(in) :: v, t
integer :: c, b, a
b = t
a = v
do
c = mod(a, b)
if ( c == 0) exit
a = b
b = c
end do
gcd = b ! abs(b)
end function gcd
[edit] Iterative binary algorithm
subroutine gcd_bin(value, u, v)
integer, intent(out) :: value
integer, intent(inout) :: u, v
integer :: k, t
u = abs(u)
v = abs(v)
if( u < v ) then
t = u
u = v
v = t
endif
if( v == 0 ) then
value = u
return
endif
k = 1
do while( (mod(u, 2) == 0).and.(mod(v, 2) == 0) )
u = u / 2
v = v / 2
k = k * 2
enddo
if( (mod(u, 2) == 0) ) then
t = u
else
t = -v
endif
do while( t /= 0 )
do while( (mod(t, 2) == 0) )
t = t / 2
enddo
if( t > 0 ) then
u = t
else
v = -t
endif
t = u - v
enddo
value = u * k
end subroutine gcd_bin
[edit] Notes on performance
gcd_iter(40902, 24140) takes us about 2.8 µsec
gcd_bin(40902, 24140) takes us about 2.5 µsec
[edit] Genyris
[edit] Recursive
def gcd (u v)
u = (abs u)
v = (abs v)
cond
(equal? v 0) u
else (gcd v (% u v))
[edit] Iterative
def gcd (u v)
u = (abs u)
v = (abs v)
while (not (equal? v 0))
var tmp (% u v)
u = v
v = tmp
u
[edit] gnuplot
gcd (a, b) = b == 0 ? a : gcd (b, a % b)
Example:
print gcd (111111, 1111)
Output:
11
[edit] Go
this is just a wrapper for big.GcdInt
import "big"
func gcd(x, y int64) int64 {
result := new(big.Int)
big.GcdInt(result, nil, nil, big.NewInt(x), big.NewInt(y))
return result.Int64()
}
[edit] Groovy
[edit] Recursive
def gcdR
gcdR = { m, n -> m = m.abs(); n = n.abs(); n == 0 ? m : m%n == 0 ? n : gcdR(n, m%n) }
[edit] Iterative
def gcdI = { m, n -> m = m.abs(); n = n.abs(); n == 0 ? m : { while(m%n != 0) { t=n; n=m%n; m=t }; n }() }
Test program:
println " R I"
println "gcd(28, 0) = ${gcdR(28, 0)} == ${gcdI(28, 0)}"
println "gcd(0, 28) = ${gcdR(0, 28)} == ${gcdI(0, 28)}"
println "gcd(0, -28) = ${gcdR(0, -28)} == ${gcdI(0, -28)}"
println "gcd(70, -28) = ${gcdR(70, -28)} == ${gcdI(70, -28)}"
println "gcd(70, 28) = ${gcdR(70, 28)} == ${gcdI(70, 28)}"
println "gcd(28, 70) = ${gcdR(28, 70)} == ${gcdI(28, 70)}"
println "gcd(800, 70) = ${gcdR(800, 70)} == ${gcdI(800, 70)}"
println "gcd(27, -70) = ${gcdR(27, -70)} == ${gcdI(27, -70)}"
Output:
R I gcd(28, 0) = 28 == 28 gcd(0, 28) = 28 == 28 gcd(0, -28) = 28 == 28 gcd(70, -28) = 14 == 14 gcd(70, 28) = 14 == 14 gcd(28, 70) = 14 == 14 gcd(800, 70) = 10 == 10 gcd(27, -70) = 1 == 1
[edit] Haskell
That is already available as the function gcd in the Prelude. Here's the implementation:
gcd :: (Integral a) => a -> a -> a
gcd 0 0 = error "Prelude.gcd: gcd 0 0 is undefined"
gcd x y = gcd' (abs x) (abs y) where
gcd' a 0 = a
gcd' a b = gcd' b (a `rem` b)
[edit] HicEst
FUNCTION gcd(a, b)
IF(b == 0) THEN
gcd = ABS(a)
ELSE
aa = a
gcd = b
DO i = 1, 1E100
r = ABS(MOD(aa, gcd))
IF( r == 0 ) RETURN
aa = gcd
gcd = r
ENDDO
ENDIF
END
[edit] Icon and Unicon
[edit] Icon
link numbers # gcd is part of the Icon Programming Library
procedure main(args)
write(gcd(arg[1], arg[2])) | "Usage: gcd n m")
end
Library: Icon Programming Library numbers implements this as:
procedure gcd(i,j) #: greatest common divisor
local r
if (i | j) < 1 then runerr(501)
repeat {
r := i % j
if r = 0 then return j
i := j
j := r
}
end
[edit] Unicon
This Icon solution works in Unicon.
[edit] J
x+.y
For example:
12 +. 30
6
[edit] Java
[edit] Iterative
public static long gcd(long a, long b){
long factor= Math.max(a, b);
for(long loop= factor;loop > 1;loop--){
if(a % loop == 0 && b % loop == 0){
return loop;
}
}
return 1;
}
[edit] Recursive
public static long gcd(long a, long b){
if(a == 0) return b;
if(b == 0) return a;
if(a > b) return gcd(b, a % b);
return gcd(a, b % a);
}
[edit] JavaScript
Iterative.
function gcd(a,b) {
if (a < 0) a = -a;
if (b < 0) b = -b;
if (b > a) {var temp = a; a = b; b = temp;}
while (true) {
a %= b;
if (a == 0) return b;
b %= a;
if (b == 0) return a;
}
}
Recursive.
function gcd_rec(a, b) {
if (b) {
return gcd_rec(b, a % b);
} else {
return Math.abs(a);
}
}
[edit] Joy
DEFINE gcd == [0 >] [dup rollup rem] while pop.
[edit] Logo
to gcd :a :b
if :b = 0 [output :a]
output gcd :b modulo :a :b
end
[edit] Lua
Translation of: C
function gcd(a,b)
if b ~= 0 then
return gcd(b, a % b)
else
return math.abs(a)
end
end
function demo(a,b)
print("GCD of " .. a .. " and " .. b .. " is " .. gcd(a, b))
end
demo(100, 5)
demo(5, 100)
demo(7, 23)
Output:
GCD of 100 and 5 is 5 GCD of 5 and 100 is 5 GCD of 7 and 23 is 1
[edit] Lucid
[edit] dataflow algorithm
gcd(n,m) where
z = [% n, m %] fby if x > y then [% x - y, y %] else [% x, y - x%] fi;
x = hd(z);
y = hd(tl(z));
gcd(n, m) = (x asa x*y eq 0) fby eod;
end
[edit] Mathematica
GCD[a, b]
[edit] MATLAB
function [gcdValue] = greatestcommondivisor(integer1, integer2)
gcdValue = gcd(integer1, integer2);
[edit] MAXScript
[edit] Iterative Euclid algorithm
fn gcdIter a b =
(
while b > 0 do
(
c = mod a b
a = b
b = c
)
abs a
)
[edit] Recursive Euclid algorithm
fn gcdRec a b =
(
if b > 0 then gcdRec b (mod a b) else abs a
)
[edit] Modula-3
MODULE GCD EXPORTS Main;
IMPORT IO, Fmt;
PROCEDURE GCD(a, b: CARDINAL): CARDINAL =
BEGIN
IF a = 0 THEN
RETURN b;
ELSIF b = 0 THEN
RETURN a;
ELSIF a > b THEN
RETURN GCD(b, a MOD b);
ELSE
RETURN GCD(a, b MOD a);
END;
END GCD;
BEGIN
IO.Put("GCD of 100, 5 is " & Fmt.Int(GCD(100, 5)) & "\n");
IO.Put("GCD of 5, 100 is " & Fmt.Int(GCD(5, 100)) & "\n");
IO.Put("GCD of 7, 23 is " & Fmt.Int(GCD(7, 23)) & "\n");
END GCD.
Output:
GCD of 100, 5 is 5 GCD of 5, 100 is 5 GCD of 7, 23 is 1
[edit] MUMPS
GCD(A,B)
QUIT:((A/1)'=(A\1))!((B/1)'=(B\1)) 0
SET:A<0 A=-A
SET:B<0 B=-B
IF B'=0
FOR SET T=A#B,A=B,B=T QUIT:B=0 ;ARGUEMENTLESS FOR NEEDS TWO SPACES
QUIT A
Ouput:
CACHE>S X=$$GCD^ROSETTA(12,24) W X 12 CACHE>S X=$$GCD^ROSETTA(24,-112) W X 8 CACHE>S X=$$GCD^ROSETTA(24,-112.2) W X 0
[edit] Nial
Nial provides gcd in the standard lib.
|loaddefs 'niallib/gcd.ndf'
|gcd 6 4
=2
defining it for arrays
# red is the reduction operator for a sorted list
# one is termination condition
red is cull filter (0 unequal) link [mod [rest, first] , first]
one is or [= [1 first, tally], > [2 first, first]]
gcd is fork [one, first, gcd red] sort <=
Using it
|gcd 9 6 3
=3
[edit] Objeck
bundle Default {
class GDC {
function : Main(args : String[]), Nil {
for(x := 1; x < 36; x += 1;) {
IO.Console->GetInstance()->Print("GCD of ")->Print(36)->Print(" and ")->Print(x)->Print(" is ")->PrintLine(GDC(36, x));
};
}
function : native : GDC(a : Int, b : Int), Int {
t : Int;
if(a > b) {
t := b; b := a; a := t;
};
while (b <> 0) {
t := a % b; a := b; b := t;
};
return a;
}
}
}
[edit] OCaml
let rec gcd a b =
if a = 0 then b
else if b = 0 then a
else if a > b then gcd b (a mod b)
else gcd a (b mod a)
[edit] Octave
r = gcd(a, b)
[edit] Oz
declare
fun {UnsafeGCD A B}
if B == 0 then
A
else
{UnsafeGCD B A mod B}
end
end
fun {GCD A B}
if A == 0 andthen B == 0 then
raise undefined(gcd 0 0) end
else
{UnsafeGCD {Abs A} {Abs B}}
end
end
in
{Show {GCD 456 ~632}}
[edit] Pascal
function gcd(a, b: integer): integer;
var
tmp: integer;
begin
while b <> 0 do
begin
tmp := a mod b;
a := b;
b := tmp
end;
gcd := a
end;
[edit] Perl
[edit] Iterative Euclid algorithm
sub gcd_iter($$) {
my ($u, $v) = @_;
while ($v) {
($u, $v) = ($v, $u % $v);
}
return abs($u);
}
[edit] Recursive Euclid algorithm
sub gcd($$) {
my ($u, $v) = @_;
if ($v) {
return gcd($v, $u % $v);
} else {
return abs($u);
}
}
[edit] Iterative binary algorithm
sub gcd_bin($$) {
my ($u, $v) = @_;
$u = abs($u);
$v = abs($v);
if ($u < $v) {
($u, $v) = ($v, $u);
}
if ($v == 0) {
return $u;
}
my $k = 1;
while ($u & 1 == 0 && $v & 1 == 0) {
$u >>= 1;
$v >>= 1;
$k <<= 1;
}
my $t = ($u & 1) ? -$v : $u;
while ($t) {
while ($t & 1 == 0) {
$t >>= 1;
}
if ($t > 0) {
$u = $t;
} else {
$v = -$t;
}
$t = $u - $v;
}
return $u * $k;
}
[edit] Notes on performance
use Benchmark qw(cmpthese);
my $u = 40902;
my $v = 24140;
cmpthese(-5, {
'gcd' => sub { gcd($u, $v); },
'gcd_iter' => sub { gcd_iter($u, $v); },
'gcd_bin' => sub { gcd_bin($u, $v); },
});
Output on 'Intel(R) Pentium(R) 4 CPU 1.50GHz' / Linux / Perl 5.8.8:
Rate gcd_bin gcd_iter gcd
gcd_bin 321639/s -- -12% -20%
gcd_iter 366890/s 14% -- -9%
gcd 401149/s 25% 9% --
[edit] Perl 6
Works with: Rakudo version #21 "Seattle"
[edit] Iterative
sub gcd (Int $a is copy, Int $b is copy) {
$a & $b == 0 and fail;
($a, $b) = ($b, $a % $b) while $b;
return abs $a;
}
[edit] Recursive
multi gcd (0, 0) { fail }
multi gcd (Int $a, 0) { abs $a }
multi gcd (Int $a, Int $b) { gcd $b, $a % $b }
[edit] PicoLisp
(de gcd (A B)
(until (=0 B)
(let M (% A B)
(setq A B B M) ) )
(abs A) )
[edit] PHP
[edit] Iterative
function gcdIter($n, $m) {
while(true) {
if($n == $m) {
return $m;
}
if($n > $m) {
$n -= $m;
} else {
$m -= $n;
}
}
}
[edit] Recursive
function gcdRec($n, $m) {
if($m > 0) {
return gcdRec($m, $n % $m);
} else {
return abs($n);
}
}
[edit] PL/I
GCD: procedure (a, b) returns (fixed binary (31)) recursive;
declare (a, b) fixed binary (31);
if b = 0 then return (a);
return (GCD (b, mod(a, b)) );
end GCD;
[edit] Pop11
[edit] Built-in gcd
gcd_n(15, 12, 2) =>
Note: the last argument gives the number of other arguments (in this case 2).
[edit] Iterative Euclid algorithm
define gcd(k, l) -> r;
lvars k , l, r = l;
abs(k) -> k;
abs(l) -> l;
if k < l then (k, l) -> (l, k) endif;
while l /= 0 do
(l, k rem l) -> (k, l)
endwhile;
k -> r;
enddefine;
[edit] PowerShell
[edit] Recursive Euclid Algorithm
function Get-GCD ($x, $y)
{
if ($x -eq $y) { return $y }
if ($x -gt $y) {
$a = $x
$b = $y
}
else {
$a = $y
$b = $x
}
while ($a % $b -ne 0) {
$tmp = $a % $b
$a = $b
$b = $tmp
}
return $b
}
[edit] Prolog
[edit] Recursive Euclid Algorithm
gcd(X, 0, X):- !.
gcd(0, X, X):- !.
gcd(X, Y, D):- X > Y, !, Z is X mod Y, gcd(Y, Z, D).
gcd(X, Y, D):- Z is Y mod X, gcd(X, Z, D).
[edit] Repeated Subtraction
gcd(X, 0, X):- !.
gcd(0, X, X):- !.
gcd(X, Y, D):- X =< Y, !, Z is Y - X, gcd(X, Z, D).
gcd(X, Y, D):- gcd(Y, X, D).
[edit] PureBasic
Iterative
Procedure GCD(x, y)
Protected r
While y <> 0
r = x % y
x = y
y = r
Wend
ProcedureReturn y
EndProcedure
Recursive
Procedure GCD(x, y)
Protected r
r = x % y
If (r > 0)
y = GCD(y, r)
EndIf
ProcedureReturn y
EndProcedure
[edit] Python
[edit] Built-in
Works with: Python version 2.6+
from fractions import gcd
[edit] Iterative Euclid algorithm
def gcd_iter(u, v):
while v:
u, v = v, u % v
return abs(u)
[edit] Recursive Euclid algorithm
Interpreter: Python 2.5
def gcd(u, v):
return gcd(v, u % v) if v else abs(u)
[edit] Tests
>>> gcd(0,0) 0 >>> gcd(0, 10) == gcd(10, 0) == gcd(-10, 0) == gcd(0, -10) == 10 True >>> gcd(9, 6) == gcd(6, 9) == gcd(-6, 9) == gcd(9, -6) == gcd(6, -9) == gcd(-9, 6) == 3 True >>> gcd(8, 45) == gcd(45, 8) == gcd(-45, 8) == gcd(8, -45) == gcd(-8, 45) == gcd(45, -8) == 1 True >>> gcd(40902, 24140) # check Knuth :) 34
[edit] Iterative binary algorithm
See The Art of Computer Programming by Knuth (Vol.2)
def gcd_bin(u, v):
u, v = abs(u), abs(v) # u >= 0, v >= 0
if u < v:
u, v = v, u # u >= v >= 0
if v == 0:
return u
# u >= v > 0
k = 1
while u & 1 == 0 and v & 1 == 0: # u, v - even
u >>= 1; v >>= 1
k <<= 1
t = -v if u & 1 else u
while t:
while t & 1 == 0:
t >>= 1
if t > 0:
u = t
else:
v = -t
t = u - v
return u * k
[edit] Notes on performance
gcd(40902, 24140) takes us about 17 µsec (Euclid, not built-in)
gcd_iter(40902, 24140) takes us about 11 µsec
gcd_bin(40902, 24140) takes us about 41 µsec
[edit] R
"%gcd%" <- function(u, v) {
ifelse(u %% v != 0, v %gcd% (u%%v), v)
}
"%gcd%" <- function(v, t) {
while ( (c <- v%%t) != 0 ) {
v <- t
t <- c
}
}
print(50 %gcd% 75)
[edit] REBOL
gcd: func [
{Returns the greatest common denominator of m and n.}
m [integer!]
n [integer!]
][
;Euclid's algorithm
abs either zero? n [0] [either zero? (m // n) [n] [gcd n (m // n)]]
]
[edit] Ruby
That is already available as the gcd method of integers:
irb(main):001:0> require 'rational' => true irb(main):002:0> 40902.gcd(24140) => 34
Here's an implementation:
def gcd(u, v)
u, v = u.abs, v.abs
while v > 0
u, v = v, u % v
end
u
end
[edit] Sather
Translation of: bc
class MATH is
gcd_iter(u, v:INT):INT is
loop while!( v.bool );
t ::= u; u := v; v := t % v;
end;
return u.abs;
end;
gcd(u, v:INT):INT is
if v.bool then return gcd(v, u%v); end;
return u.abs;
end;
private swap(inout a, inout b:INT) is
t ::= a;
a := b;
b := t;
end;
gcd_bin(u, v:INT):INT is
t:INT;
u := u.abs; v := v.abs;
if u < v then swap(inout u, inout v); end;
if v = 0 then return u; end;
k ::= 1;
loop while!( u.is_even and v.is_even );
u := u / 2; v := v / 2;
k := k * 2;
end;
if u.is_even then
t := -v;
else
t := u;
end;
loop while!( t.bool );
loop while!( t.is_even );
t := t / 2;
end;
if t > 0 then
u := t;
else
v := -t;
end;
t := u - v;
end;
return u * k;
end;
end;
class MAIN is
main is
a ::= 40902;
b ::= 24140;
#OUT + MATH::gcd_iter(a, b) + "\n";
#OUT + MATH::gcd(a, b) + "\n";
#OUT + MATH::gcd_bin(a, b) + "\n";
-- built in
#OUT + a.gcd(b) + "\n";
end;
end;
[edit] Scala
def gcd(a: Int, b: Int): Int = if (b == 0) a.abs else gcd(b, a % b)
[edit] Scheme
(define (gcd a b)
(if (= b 0)
a
(gcd b (modulo a b))))
or using the standard function included with Scheme (takes any number of arguments):
(gcd a b)
[edit] Seed7
const func integer: gcd (in var integer: a, in var integer: b) is func
result
var integer: result is 0;
local
var integer: help is 0;
begin
while a <> 0 do
help := b rem a;
b := a;
a := help;
end while;
result := b;
end func;
Original source: [1]
[edit] SETL
a := 33; b := 77;
print(" the gcd of",a," and ",b," is ",gcd(a,b));
c := 49865; d := 69811;
print(" the gcd of",c," and ",d," is ",gcd(c,d));
proc gcd (u, v);
return if v = 0 then abs u else gcd (v, u mod v) end;
end;
Output:
the gcd of 33 and 77 is 11
the gcd of 49865 and 69811 is 9973
[edit] Slate
Slate's Integer type has gcd defined:
40902 gcd: 24140
[edit] Iterative Euclid algorithm
x@(Integer traits) gcd: y@(Integer traits)
"Euclid's algorithm for finding the greatest common divisor."
[| n m temp |
n: x.
m: y.
[n isZero] whileFalse: [temp: n. n: m \\ temp. m: temp].
m abs
].
[edit] Recursive Euclid algorithm
x@(Integer traits) gcd: y@(Integer traits)
[
y isZero
ifTrue: [x]
ifFalse: [y gcd: x \\ y]
].
[edit] Smalltalk
The Integer class has its gcd method.
(40902 gcd: 24140) displayNl
An implementation of the Iterative Euclid's algorithm
|gcd_iter|
gcd_iter := [ :a :b | |u v| u := a. v := b.
[ v > 0 ]
whileTrue: [ |t|
t := u copy.
u := v copy.
v := t rem: v
].
u abs
].
(gcd_iter value: 40902 value: 24140)
printNl.
[edit] SNOBOL4
define('gcd(i,j)') :(gcd_end)
gcd ?eq(i,0) :s(freturn)
?eq(j,0) :s(freturn)
loop gcd = remdr(i,j)
gcd = ?eq(gcd,0) j :s(return)
i = j
j = gcd :(loop)
gcd_end
output = gcd(1071,1029)
end
[edit] Standard ML
fun gcd a 0 = a
| gcd a b = gcd b (a mod b)
[edit] Tcl
[edit] Iterative Euclid algorithm
package require Tcl 8.5
namespace path {::tcl::mathop ::tcl::mathfunc}
proc gcd_iter {p q} {
while {$q != 0} {
lassign [list $q [% $p $q]] p q
}
abs $p
}
[edit] Recursive Euclid algorithm
proc gcd {p q} {
if {$q == 0} {
return $p
}
gcd $q [expr {$p % $q}]
}
With Tcl 8.6, this can be optimized slightly to:
proc gcd {p q} {
if {$q == 0} {
return $p
}
tailcall gcd $q [expr {$p % $q}]
}
(Tcl does not perform automatic tail-call optimization introduction because that makes any potential error traces less informative.)
[edit] Iterative binary algorithm
package require Tcl 8.5
namespace path {::tcl::mathop ::tcl::mathfunc}
proc gcd_bin {p q} {
if {$p == $q} {return [abs $p]}
set p [abs $p]
if {$q == 0} {return $p}
set q [abs $q]
if {$p < $q} {lassign [list $q $p] p q}
set k 1
while {($p & 1) == 0 && ($q & 1) == 0} {
set p [>> $p 1]
set q [>> $q 1]
set k [<< $k 1]
}
set t [expr {$p & 1 ? -$q : $p}]
while {$t} {
while {$t & 1 == 0} {set t [>> $t 1]}
if {$t > 0} {set p $t} {set q [- $t]}
set t [- $p $q]
}
return [* $p $k]
}
[edit] Notes on performance
foreach proc {gcd_iter gcd gcd_bin} {
puts [format "%-8s - %s" $proc [time {$proc $u $v} 100000]]
}
Outputs:
gcd_iter - 4.46712 microseconds per iteration gcd - 5.73969 microseconds per iteration gcd_bin - 9.25613 microseconds per iteration
[edit] TI-83 BASIC, TI-89 BASIC
gcd(A,B)
[edit] Ursala
This doesn't need to be defined because it's a library function, but it can be defined like this based on a recursive implementation of Euclid's algorithm. This isn't the simplest possible solution because it includes a bit shifting optimization that happens when both operands are even.
#import nat
gcd = ~&B?\~&Y ~&alh^?\~&arh2faltPrXPRNfabt2RCQ @a ~&ar^?\~&al ^|R/~& ^/~&r remainder
test program:
#cast %nWnAL
test = ^(~&,gcd)* <(25,15),(36,16),(120,45),(30,100)>
output:
< (25,15): 5, (36,16): 4, (120,45): 15, (30,100): 10>
[edit] V
like joy
[edit] iterative
[gcd [0 >] [dup rollup %] while pop ].
[edit] recursive
like python
[gcd
[zero?] [pop]
[swap [dup] dip swap %]
tailrec].
same with view: (swap [dup] dip swap % is replaced with a destructuring view)
[gcd
[zero?] [pop]
[[a b : [b a b %]] view i]
tailrec].
running it
|1071 1029 gcd =21
Categories: Programming Tasks | Arithmetic operations | Recursion | ActionScript | Ada | ALGOL 68 | APL | AWK | AutoHotkey | Batch File | BASIC | Bc | Befunge | C | C++ | Clojure | C sharp | Common Lisp | D | E | Emacs Lisp | Erlang | F Sharp | Factor | FALSE | Forth | Fortran | Genyris | Gnuplot | Go | Groovy | Haskell | HicEst | Icon | Icon Programming Library | Unicon | J | Java | JavaScript | Joy | Logo | Lua | Lucid | Mathematica | MATLAB | MAXScript | Modula-3 | MUMPS | Nial | Objeck | OCaml | Octave | Oz | Pascal | Perl | Perl 6 | PicoLisp | PHP | PL/I | Pop11 | PowerShell | Prolog | PureBasic | Python | R | REBOL | Ruby | Sather | Scala | Scheme | Seed7 | SETL | Slate | Smalltalk | SNOBOL4 | Standard ML | Tcl | TI-83 BASIC | TI-89 BASIC | Ursala | V
