Greatest common divisor

From Rosetta Code
Jump to: navigation, search
Task
Greatest common divisor
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.

Contents

[edit] ACL2

(include-book "arithmetic-3/floor-mod/floor-mod" :dir :system)
 
(defun gcd$ (x y)
(declare (xargs :guard (and (natp x) (natp y))))
(cond ((or (not (natp x)) (< y 0))
nil)
((zp y) x)
(t (gcd$ y (mod x y)))))

[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
M : Integer := A;
N : Integer := B;
T : Integer;
begin
while N /= 0 loop
T := M;
M := N;
N := T mod N;
end loop;
return M;
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] Aime

o_integer(gcd(33, 77));
o_byte('\n');
o_integer(gcd(49865, 69811));
o_byte('\n');

[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] Alore

def gcd(a as Int, b as Int) as Int
while b != 0
a,b = b, a mod b
end
return Abs(a)
end

[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] AutoHotkey

Contributed by Laszlo on the ahk forum

GCD(a,b) {
Return b=0 ? Abs(a) : Gcd(b,mod(a,b))
}

Significantly faster than the recursive version above:

gcd(a, b) {
while b
t := b, b := Mod(a, b), a := t
return, a
}

[edit] AutoIt

 
_GCD(18, 12)
_GCD(1071, 1029)
_GCD(3528, 3780)
 
Func _GCD($ia, $ib)
Local $ret = "GCD of " & $ia & " : " & $ib & " = "
Local $imod
While True
$imod = Mod($ia, $ib)
If $imod = 0 Then Return ConsoleWrite($ret & $ib & @CRLF)
$ia = $ib
$ib = $imod
WEnd
EndFunc ;==>_GCD
 
Output:
GCD of 18 : 12 = 6
GCD of 1071 : 1029 = 21
GCD of 3528 : 3780 = 252

[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] 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] BBC BASIC

      DEF FN_GCD_Iterative_Euclid(A%, B%)
LOCAL C%
WHILE B%
C% = A%
A% = B%
B% = C% MOD B%
ENDWHILE
= ABS(A%)

[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] Bracmat

Bracmat uses the Euclidean algorithm to simplify fractions. The den function extracts the denominator from a fraction.

(gcd=a b.!arg:(?a.?b)&!b*den$(!a*!b^-1)^-1);

Example:

{?} gcd$(49865.69811)
{!} 9973

[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) {
return (v != 0)?gcd(v, u%v):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] C#

Translation of: 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] 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))))

That recur call is the same as (gcd b (mod a b)), but makes use of Clojure's explicit tail call optimization.

[edit] COBOL

       IDENTIFICATION DIVISION.
PROGRAM-ID. GCD.
 
DATA DIVISION.
WORKING-STORAGE SECTION.
01 A PIC 9(10) VALUE ZEROES.
01 B PIC 9(10) VALUE ZEROES.
01 TEMP PIC 9(10) VALUE ZEROES.
 
PROCEDURE DIVISION.
Begin.
DISPLAY "Enter first number, max 10 digits."
ACCEPT A
DISPLAY "Enter second number, max 10 digits."
ACCEPT B
IF A < B
MOVE B TO TEMP
MOVE A TO B
MOVE TEMP TO B
END-IF
 
PERFORM UNTIL B = 0
MOVE A TO TEMP
MOVE B TO A
DIVIDE TEMP BY B GIVING TEMP REMAINDER B
END-PERFORM
DISPLAY "The gcd is " A
STOP RUN.

[edit] Cobra

 
class Rosetta
def gcd(u as number, v as number) as number
u, v = u.abs, v.abs
while v > 0
u, v = v, u % v
return u
 
def main
print "gcd of [12] and [8] is [.gcd(12, 8)]"
print "gcd of [12] and [-8] is [.gcd(12, -8)]"
print "gcd of [96] and [27] is [.gcd(27, 96)]"
print "gcd of [51] and [34] is [.gcd(34, 51)]"
 

Output:

gcd of 12 and 8 is 4
gcd of 12 and -8 is 4
gcd of 96 and 27 is 3
gcd of 51 and 34 is 17

[edit] CoffeeScript

Simple recursion

 
gcd = (x, y) ->
if y == 0 then x else gcd y, x % y
 

Since JS has no TCO, here's a version with no recursion

 
gcd = (x, y) ->
[1..(Math.min x, y)].reduce (acc, v) ->
if x % v == 0 and y % v == 0 then v else acc
 

[edit] Common Lisp

Common Lisp provides a gcd function.

CL-USER> (gcd 2345 5432)
7

Here is an implementation using the do macro. We call the function gcd2 so as not to conflict with common-lisp:gcd.

(defun gcd2 (a b)
(do () ((zerop b) (abs a))
(shiftf a b (mod a b))))

Here is a tail-recursive implementation.

(defun gcd2 (a b)
(if (zerop b) a
(gcd2 b (mod a b))))

The last implementation is based on the loop macro.

(defun gcd2 (a b)
(loop for x = a then y
and y = b then (mod x y)
until (zerop y)
finally (return x)))

[edit] Component Pascal

BlackBox Component Builder

 
MODULE Operations;
IMPORT StdLog,Args,Strings;
 
PROCEDURE Gcd(a,b: LONGINT):LONGINT;
VAR
r: LONGINT;
BEGIN
LOOP
r := a MOD b;
IF r = 0 THEN RETURN b END;
a := b;b := r
END
END Gcd;
 
PROCEDURE DoGcd*;
VAR
x,y,done: INTEGER;
p: Args.Params;
BEGIN
Args.Get(p);
IF p.argc >= 2 THEN
Strings.StringToInt(p.args[0],x,done);
Strings.StringToInt(p.args[1],y,done);
StdLog.String("gcd("+p.args[0]+","+p.args[1]+")=");StdLog.Int(Gcd(x,y));StdLog.Ln
END
END DoGcd;
 
END Operations.
 

Execute:
^Q Operations.DoGcd 12 8 ~
^Q Operations.DoGcd 100 5 ~
^Q Operations.DoGcd 7 23 ~
^Q Operations.DoGcd 24 -112 ~
Output:

gcd(12 ,8 )= 4
gcd(100 ,5 )= 5
gcd(7 ,23 )= 1
gcd(24 ,-112 )= -8

[edit] D

import std.stdio, std.numeric;
 
long myGCD(in long x, in long y) pure nothrow @nogc {
if (y == 0)
return x;
return myGCD(y, x % y);
}
 
void main() {
gcd(15, 10).writeln; // From Phobos.
myGCD(15, 10).writeln;
}
Output:
5
5

[edit] Dc

[dSa%Lard0<G]dsGx+

This code assumes that there are two integers on the stack.

dc -e'28 24 [dSa%Lard0<G]dsGx+ p'

[edit] DWScript

PrintLn(Gcd(231, 210));

Output:

21

[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] Eiffel

Translation of: D
 
class
APPLICATION
 
create
make
 
feature -- Implementation
 
gcd (x: INTEGER y: INTEGER): INTEGER
do
if y = 0 then
Result := x
else
Result := gcd (y, x \\ y);
end
end
 
feature {NONE} -- Initialization
 
make
-- Run application.
do
print (gcd (15, 10))
print ("%N")
end
 
end
 

[edit] Emacs Lisp

 
(defun gcd (a b)
(cond
((< a b) (gcd a (- b a)))
((> a b) (gcd (- a b) b))
(t a)))
 

[edit] Erlang

% Implemented by Arjun Sunel
-module(gcd).
-export([main/0]).
 
main() ->gcd(-36,4).
 
gcd(A, 0) -> A;
 
gcd(A, B) -> gcd(B, A rem B).
Output:
4

[edit] Euler Math Toolbox

Non-recursive version in Euler Math Toolbox. Note, that there is a built-in command.

 
>ggt(123456795,1234567851)
33
>function myggt (n:index, m:index) ...
$ if n<m then {n,m}={m,n}; endif;
$ repeat
$ k=mod(n,m);
$ if k==0 then return m; endif;
$ if k==1 then return 1; endif;
$ {n,m}={m,k};
$ end;
$ endfunction
>myggt(123456795,1234567851)
33
 

[edit] Euphoria

Translation of: C/C++

[edit] Iterative Euclid algorithm

function gcd_iter(integer u, integer v)
integer t
while v do
t = u
u = v
v = remainder(t, v)
end while
if u < 0 then
return -u
else
return u
end if
end function

[edit] Recursive Euclid algorithm

function gcd(integer u, integer v)
if v then
return gcd(v, remainder(u, v))
elsif u < 0 then
return -u
else
return u
end if
end function

[edit] Iterative binary algorithm

function gcd_bin(integer u, integer v)
integer t, k
if u < 0 then -- abs(u)
u = -u
end if
if v < 0 then -- abs(v)
v = -v
end if
if u < v then
t = u
u = v
v = t
end if
if v = 0 then
return u
end if
k = 1
while and_bits(u,1) = 0 and and_bits(v,1) = 0 do
u = floor(u/2) -- u >>= 1
v = floor(v/2) -- v >>= 1
k *= 2 -- k <<= 1
end while
if and_bits(u,1) then
t = -v
else
t = u
end if
while t do
while and_bits(t, 1) = 0 do
t = floor(t/2)
end while
if t > 0 then
u = t
else
v = -t
end if
t = u - v
end while
return u * k
end function

[edit] Ezhil

 
## இந்த நிரல் இரு எண்களுக்கு இடையிலான மீச்சிறு பொது மடங்கு (LCM), மீப்பெரு பொது வகுத்தி (GCD) என்ன என்று கணக்கிடும்
 
நிரல்பாகம் மீபொவ(எண்1, எண்2)
 
@(எண்1 == எண்2) ஆனால்
 
## இரு எண்களும் சமம் என்பதால், அந்த எண்ணேதான் அதன் மீபொவ
 
பின்கொடு எண்1
 
@(எண்1 > எண்2) இல்லைஆனால்
 
சிறியது = எண்2
பெரியது = எண்1
 
இல்லை
 
சிறியது = எண்1
பெரியது = எண்2
 
முடி
 
மீதம் = பெரியது % சிறியது
 
@(மீதம் == 0) ஆனால்
 
## பெரிய எண்ணில் சிறிய எண் மீதமின்றி வகுபடுவதால், சிறிய எண்தான் மீப்பெரு பொதுவகுத்தியாக இருக்கமுடியும்
 
பின்கொடு சிறியது
 
இல்லை
 
தொடக்கம் = சிறியது - 1
 
நிறைவு = 1
 
@(எண் = தொடக்கம், எண் >= நிறைவு, எண் = எண் - 1) ஆக
 
மீதம்1 = சிறியது % எண்
 
மீதம்2 = பெரியது % எண்
 
## இரு எண்களையும் மீதமின்றி வகுக்கக்கூடிய பெரிய எண்ணைக் கண்டறிகிறோம்
 
@((மீதம்1 == 0) && (மீதம்2 == 0)) ஆனால்
 
பின்கொடு எண்
 
முடி
 
முடி
 
முடி
 
முடி
 
அ = int(உள்ளீடு("ஓர் எண்ணைத் தாருங்கள் "))
ஆ = int(உள்ளீடு("இன்னோர் எண்ணைத் தாருங்கள் "))
 
பதிப்பி "நீங்கள் தந்த இரு எண்களின் மீபொவ (மீப்பெரு பொது வகுத்தி, GCD) = ", மீபொவ(அ, ஆ)
 

[edit] F#

 
let rec gcd a b =
if b = 0
then abs a
else gcd b (a % b)
 
>gcd 400 600
val it : int = 200

[edit] Factor

: gcd ( a b -- c )
[ abs ] [
[ nip ] [ mod ] 2bi gcd
] if-zero ;

[edit] FALSE

10 15$ [0=~][$@$@$@\/*-$]#%. { gcd(10,15)=5 }

[edit] Fantom

 
class Main
{
static Int gcd (Int a, Int b)
{
a = a.abs
b = b.abs
while (b > 0)
{
t := a
a = b
b = t % b
}
return a
}
 
public static Void main()
{
echo ("GCD of 51, 34 is: " + gcd(51, 34))
}
}
 

[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] Frink

Frink has a builtin gcd[x,y] function that returns the GCD of two integers (which can be arbitrarily large.)

 
println[gcd[12345,98765]]
 

[edit] FunL

FunL has pre-defined function gcd in module integers defined as:

def
gcd( 0, 0 ) = error( 'integers.gcd: gcd( 0, 0 ) is undefined' )
gcd( a, b ) =
def
_gcd( a, 0 ) = a
_gcd( a, b ) = _gcd( b, a%b )
 
_gcd( abs(a), abs(b) )

[edit] GAP

# Built-in
GcdInt(35, 42);
# 7
 
# Euclidean algorithm
GcdInteger := function(a, b)
local c;
a := AbsInt(a);
b := AbsInt(b);
while b > 0 do
c := a;
a := b;
b := RemInt(c, b);
od;
return a;
end;
 
GcdInteger(35, 42);
# 7

[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] GML

 
var n,m,r;
n = max(argument0,argument1);
m = min(argument0,argument1);
while (m != 0)
{
r = n mod m;
n = m;
m = r;
}
return a;
 

[edit] gnuplot

gcd (a, b) = b == 0 ? a : gcd (b, a % b)

Example:

print gcd (111111, 1111)

Output:

11

[edit] Go

[edit] Iterative

package main
 
import "fmt"
 
func gcd(x, y int) int {
for y != 0 {
x, y = y, x%y
}
return x
}
 
func main() {
fmt.Println(gcd(33, 77))
fmt.Println(gcd(49865, 69811))
}
 

[edit] Builtin

(This is just a wrapper for big.GCD)

package main
 
import (
"fmt"
"math/big"
)
 
func gcd(x, y int64) int64 {
return new(big.Int).GCD(nil, nil, big.NewInt(x), big.NewInt(y)).Int64()
}
 
func main() {
fmt.Println(gcd(33, 77))
fmt.Println(gcd(49865, 69811))
}
Output in either case:
11
9973

[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

link numbers   # gcd is part of the Icon Programming Library
procedure main(args)
write(gcd(arg[1], arg[2])) | "Usage: gcd n m")
end
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] J

x+.y

For example:

   12 +. 30
6

Note that +. is a single, two character token. GCD is a primitive in J (and anyone that has studied the right kind of mathematics should instantly recognize why the same operation is used for both GCD and OR -- among other things, GCD and boolean OR both have the same identity element: 0, and of course they produce the same numeric results on the same arguments (when we are allowed to use the usual 1 bit implementation of 0 and 1 for false and true)).

[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] Iterative Euclid's Algorithm

 
public static int gcd(int a, int b) //valid for positive integers.
{
while(b > 0)
{
int c = a % b;
a = b;
b = c;
}
return a;
}
 

[edit] Optimized Iterative

 
static int gcd(int a,int b)
{
int min=a>b?b:a,max=a+b-min, div=min;
for(int i=1;i<min;div=min/++i)
if(max%div==0)
return div;
return 1;
}
 

[edit] Iterative binary algorithm

Translation of: C/C++
public static long gcd(long u, long v){
long t, k;
 
if (v == 0) return u;
 
u = Math.abs(u);
v = Math.abs(v);
if (u < v){
t = u;
u = v;
v = t;
}
 
for(k = 1; (u & 1) == 0 && (v & 1) == 0; k <<= 1){
u >>= 1; v >>= 1;
}
 
t = (u & 1) != 0 ? -v : u;
while (t != 0){
while ((t & 1) == 0) t >>= 1;
 
if (t > 0)
u = t;
else
v = -t;
 
t = u - v;
}
return u * k;
}

[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] Built-in

import java.math.BigInteger;
 
public static long gcd(long a, long b){
return BigInteger.valueOf(a).gcd(BigInteger.valueOf(b)).longValue();
}

[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);
}
}

For an array of integers

function GCD(A)   // A is an integer array (e.g. [57,0,-45,-18,90,447])
{
var n = A.length, x = A[0] < 0 ? -A[0] : A[0];
for (var i = 1; i < n; i++)
{ var y = A[i] < 0 ? -A[i] : A[i];
while (x && y){ x > y ? x %= y : y %= x; }
x += y;
}
return x;
}
 
/* For example:
GCD([57,0,-45,-18,90,447]) -> 3
*/

[edit] Joy

DEFINE gcd == [0 >] [dup rollup rem] while pop.

[edit] jq

def recursive_gcd(a; b):
if b == 0 then a
else recursive_gcd(b; a % b)
end ;
Recent versions of jq include support for tail recursion optimization for arity-0 filters (which can be thought of as arity-1 functions), so here is an implementation that takes advantage of that optimization. Notice that the subfunction, rgcd, can be easily derived from recursive_gcd above by moving the arguments to the input:
def gcd(a; b):
# The subfunction expects [a,b] as input
# i.e. a ~ .[0] and b ~ .[1]
def rgcd: if .[1] == 0 then .[0]
else [.[1], .[0] % .[1]] | rgcd
end;
[a,b] | rgcd ;

[edit] Julia

Julia includes a built-in gcd function:

julia> gcd(4,12)
4
julia> gcd(6,12)
6
julia> gcd(7,12)
1

The actual implementation of this function in Julia 0.2's standard library is reproduced here:

function gcd{T<:Integer}(a::T, b::T)
neg = a < 0
while b != 0
t = b
b = rem(a, b)
a = t
end
g = abs(a)
neg ? -g : g
end

(For arbitrary-precision integers, Julia calls a different implementation from the GMP library.)

[edit] K

gcd:{:[~x;y;_f[y;x!y]]}

[edit] LabVIEW

Translation of: AutoHotkey

It may be helpful to read about Recursion in LabVIEW.
This image is a VI Snippet, an executable image of LabVIEW code. The LabVIEW version is shown on the top-right hand corner. You can download it, then drag-and-drop it onto the LabVIEW block diagram from a file browser, and it will appear as runnable, editable code.
LabVIEW Greatest common divisor.png

[edit] Liberty BASIC

'iterative Euclid algorithm
print GCD(-2,16)
end
 
function GCD(a,b)
while b
c = a
a = b
b = c mod b
wend
GCD = abs(a)
end function
 

[edit] Limbo

gcd(x: int, y: int): int
{
if(y == 0)
return x;
return gcd(y, x % y);
}
 

[edit] LiveCode

function gcd x,y
repeat until y = 0
put x mod y into z
put y into x
put z into y
end repeat
return x
end gcd


[edit]

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] Maple

To compute the greatest common divisor of two integers in Maple, use the procedure igcd.

igcd( a, b )

For example,

 
> igcd( 24, 15 );
3
 


[edit] Mathematica

GCD[a, b]

[edit] MATLAB

function [gcdValue] = greatestcommondivisor(integer1, integer2)
gcdValue = gcd(integer1, integer2);

[edit] Maxima

/* There is a function gcd(a, b) in Maxima, but one can rewrite it */
gcd2(a, b) := block([a: abs(a), b: abs(b)], while b # 0 do [a, b]: [b, mod(a, b)], a)$
 
/* both will return 2^97 * 3^48 */
gcd(100!, 6^100), factor;
gcd2(100!, 6^100), factor;

[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] Mercury

[edit] Recursive Euclid algorithm

:- module gcd.
 
:- interface.
:- import_module integer.
 
:- func gcd(integer, integer) = integer.
 
:- implementation.
 
:- pragma memo(gcd/2).
gcd(A, B) = (if B = integer(0) then A else gcd(B, A mod B)).

An example console program to demonstrate the gcd module:

:- module test_gcd.
 
:- interface.
 
:- import_module io.
 
:- pred main(io::di, io::uo) is det.
 
:- implementation.
 
:- import_module char.
:- import_module gcd.
:- import_module integer.
:- import_module list.
:- import_module string.
 
main(!IO) :-
command_line_arguments(Args, !IO),
filter(is_all_digits, Args, CleanArgs),
 
Arg1 = list.det_index0(CleanArgs, 0),
Arg2 = list.det_index0(CleanArgs, 1),
A = integer.det_from_string(Arg1),
B = integer.det_from_string(Arg2),
 
Fmt = integer.to_string,
GCD = gcd(A, B),
io.format("gcd(%s, %s) = %s\n", [s(Fmt(A)), s(Fmt(B)), s(Fmt(GCD))], !IO).

Example output:

gcd(70000000000000000000000, 60000000000000000000000000) = 10000000000000000000000

[edit] MIPS Assembly

gcd:
# a0 and a1 are the two integer parameters
# return value is in v0
move $t0, $a0
move $t1, $a1
loop:
beq $t1, $0, done
div $t0, $t1
move $t0, $t1
mfhi $t1
j loop
done:
move $v0, $t0
jr $ra

[edit] МК-61/52

ИПA	ИПB	/	П9	КИП9	ИПA	ИПB	ПA	ИП9	*
-	ПB	x=0	00	ИПA	С/П

Enter: n = РA, m = РB (n > m).

[edit] Modula-2

MODULE ggTkgV;
 
FROM InOut IMPORT ReadCard, WriteCard, WriteLn, WriteString, WriteBf;
 
VAR x, y, u, v : CARDINAL;
 
BEGIN
WriteString ("x = "); WriteBf; ReadCard (x);
WriteString ("y = "); WriteBf; ReadCard (y);
u := x;
v := y;
WHILE x # y DO
(* ggT (x, y) = ggT (x0, y0), x * v + y * u = 2 * x0 * y0 *)
IF x > y THEN
x := x - y;
u := u + v
ELSE
y := y - x;
v := v + u
END
END;
WriteString ("ggT ="); WriteCard (x, 6); WriteLn;
WriteString ("kgV ="); WriteCard ((u+v) DIV 2, 6); WriteLn;
WriteString ("u ="); WriteCard (u, 6); WriteLn;
WriteString ("v ="); WriteCard (v , 6); WriteLn
END ggTkgV.

Producing the output

jan@Beryllium:~/modula/Wirth/PIM$ ggtkgv
x = 12
y = 20
ggT = 4
kgV = 60
u = 44
v = 76
jan@Beryllium:~/modula/Wirth/PIM$ ggtkgv
x = 123
y = 255
ggT = 3
kgV = 10455
u = 13773
v = 7137

[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] MySQL

 
DROP FUNCTION IF EXISTS gcd;
DELIMITER |
 
CREATE FUNCTION gcd(x INT, y INT)
RETURNS INT
BEGIN
SET @dividend=GREATEST(ABS(x),ABS(y));
SET @divisor=LEAST(ABS(x),ABS(y));
IF @divisor=0 THEN
RETURN @dividend;
END IF;
SET @gcd=NULL;
SELECT gcd INTO @gcd FROM
(SELECT @tmp:=@dividend,
@dividend:=@divisor AS gcd,
@divisor:=@tmp % @divisor AS remainder
FROM mysql.help_relation WHERE @divisor>0) AS x
WHERE remainder=0;
RETURN @gcd;
END;|
 
DELIMITER ;
 
SELECT gcd(12345, 9876);
 
+------------------+
| gcd(12345, 9876) |
+------------------+
|             2469 |
+------------------+
1 row in set (0.00 sec)

[edit] NetRexx

/* NetRexx */
options replace format comments java crossref symbols nobinary
 
numeric digits 2000
runSample(arg)
return
 
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-- Euclid's algorithm - iterative implementation
method gcdEucidI(a_, b_) public static
loop while b_ > 0
c_ = a_ // b_
a_ = b_
b_ = c_
end
return a_
 
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-- Euclid's algorithm - recursive implementation
method gcdEucidR(a_, b_) public static
if b_ \= 0 then a_ = gcdEucidR(b_, a_ // b_)
return a_
 
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method runSample(arg) private static
-- pairs of numbers, each number in the pair separated by a colon, each pair separated by a comma
parse arg tests
if tests = '' then
tests = '0:0, 6:4, 7:21, 12:36, 33:77, 41:47, 99:51, 100:5, 7:23, 1989:867, 12345:9876, 40902:24140, 49865:69811, 137438691328:2305843008139952128'
 
-- most of what follows is for formatting
xiterate = 0
xrecurse = 0
ll_ = 0
lr_ = 0
lgi = 0
lgr = 0
loop i_ = 1 until tests = ''
xiterate[0] = i_
xrecurse[0] = i_
parse tests pair ',' tests
parse pair l_ ':' r_ .
 
-- get the GCDs
gcdi = gcdEucidI(l_, r_)
gcdr = gcdEucidR(l_, r_)
 
xiterate[i_] = l_ r_ gcdi
xrecurse[i_] = l_ r_ gcdr
ll_ = ll_.max(l_.strip.length)
lr_ = lr_.max(r_.strip.length)
lgi = lgi.max(gcdi.strip.length)
lgr = lgr.max(gcdr.strip.length)
end i_
-- save formatter sizes in stems
xiterate[-1] = ll_ lr_ lgi
xrecurse[-1] = ll_ lr_ lgr
 
-- present results
showResults(xiterate, 'Euclid''s algorithm - iterative')
showResults(xrecurse, 'Euclid''s algorithm - recursive')
say
if verifyResults(xiterate, xrecurse) then
say 'Success: Results of iterative and recursive methods match'
else
say 'Error: Results of iterative and recursive methods do not match'
say
return
 
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method showResults(stem, title) public static
say
say title
parse stem[-1] ll lr lg
loop v_ = 1 to stem[0]
parse stem[v_] lv rv gcd .
say lv.right(ll)',' rv.right(lr) ':' gcd.right(lg)
end v_
return
 
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method verifyResults(stem1, stem2) public static returns boolean
if stem1[0] \= stem2[0] then signal BadArgumentException
T = (1 == 1)
F = \T
verified = T
loop i_ = 1 to stem1[0]
if stem1[i_] \= stem2[i_] then do
verified = F
leave i_
end
end i_
return verified
 
Output:
Euclid's algorithm - iterative
           0,                   0 :      0
           6,                   4 :      2
           7,                  21 :      7
          12,                  36 :     12
          33,                  77 :     11
          41,                  47 :      1
          99,                  51 :      3
         100,                   5 :      5
           7,                  23 :      1
        1989,                 867 :     51
       12345,                9876 :   2469
       40902,               24140 :     34
       49865,               69811 :   9973
137438691328, 2305843008139952128 : 262144

Euclid's algorithm - recursive
           0,                   0 :      0
           6,                   4 :      2
           7,                  21 :      7
          12,                  36 :     12
          33,                  77 :     11
          41,                  47 :      1
          99,                  51 :      3
         100,                   5 :      5
           7,                  23 :      1
        1989,                 867 :     51
       12345,                9876 :   2469
       40902,               24140 :     34
       49865,               69811 :   9973
137438691328, 2305843008139952128 : 262144

Success: Results of iterative and recursive methods match

[edit] NewLISP

(gcd 12 36)  
12

[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] Nimrod

Ported from Pascal example

[edit] Recursive Euclid algorithm

proc gcd_recursive(u, v: int64): int64 =
if u %% v != 0:
result = gcd_recursive(v, u %% v)
else:
result = v

[edit] Iterative Euclid algorithm

proc gcd_iterative(u1, v1: int64): int64 =
var t: int64 = 0
var u = u1
var v = v1
while v != 0:
t = u
u = v
v = t %% v
result = abs(u)

[edit] Iterative binary algorithm

proc gcd_binary(u1, v1: int64): int64 =
var t, k: int64
var u = u1
var v = v1
u = abs(u)
v = abs(v)
if u < v:
t = u
u = v
v = t
if v == 0:
result = u
else:
k = 1
while (u %% 2 == 0) and (v %% 2 == 0):
u = u shl 1
v = v shl 1
k = k shr 1
if (u %% 2) == 0:
t = u
else:
t = -v
while t != 0:
while (t %% 2) == 0:
t = t div 2
if t > 0:
u = t
else:
v = -t
t = u - v
result = u * k
 
echo ("GCD(", 49865, ", ", 69811, "): ", gcd_iterative(49865, 69811), " (iterative)")
echo ("GCD(", 49865, ", ", 69811, "): ", gcd_recursive(49865, 69811), " (recursive)")
echo ("GCD(", 49865, ", ", 69811, "): ", gcd_binary (49865, 69811), " (binary)")
Output:
GCD(49865, 69811): 9973 (iterative)
GCD(49865, 69811): 9973 (recursive)
GCD(49865, 69811): 9973 (binary)

[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] Built-in

#load "nums.cma";;
open Big_int;;
let gcd a b =
int_of_big_int (gcd_big_int (big_int_of_int a) (big_int_of_int b))

[edit] Octave

r = gcd(a, b)

[edit] Order

Translation of: bc
#include <order/interpreter.h>
 
#define ORDER_PP_DEF_8gcd ORDER_PP_FN( \
8fn(8U, 8V, \
8if(8isnt_0(8V), 8gcd(8V, 8remainder(8U, 8V)), 8U)))

// No support for negative numbers

[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] PARI/GP

gcd(a,b)

PASCAL program GCF (INPUT, OUTPUT);

 var
   a,b,c:integer;
 begin
   writeln('Enter 1st number');
   read(a);
   writeln('Enter 2nd number');
   read(b);
   while (a*b<>0)
     do
     begin
       c:=a;
       a:=b mod a;
       b:=c;
     end;
   writeln('GCF :=', a+b );
 end.

By: NG

[edit] Pascal

[edit] Recursive Euclid algorithm

function gcd_recursive(u, v: longint): longint;
begin
if u mod v <> 0 then
gcd_recursive := gcd_recursive(v, u mod v)
else
gcd_recursive := v;
end;

[edit] Iterative Euclid algorithm

function gcd_iterative(u, v: longint): longint;
var
t: longint;
begin
while v <> 0 do
begin
t := u;
u := v;
v := t mod v;
end;
gcd_iterative := abs(u);
end;

[edit] Iterative binary algorithm

function gcd_binary(u, v: longint): longint;
var
t, k: longint;
begin
u := abs(u);
v := abs(v);
if u < v then
begin
t := u;
u := v;
v := t;
end;
if v = 0 then
gcd_binary := u
else
begin
k := 1;
while (u mod 2 = 0) and (v mod 2 = 0) do
begin
u := u >> 1;
v := v >> 1;
k := k << 1;
end;
if u mod 2 = 0 then
t := u
else
t := -v;
while t <> 0 do
begin
while t mod 2 = 0 do
t := t div 2;
if t > 0 then
u := t
else
v := -t;
t := u - v;
end;
gcd_binary := u * k;
end;
end;

Demo program:

Program GreatestCommonDivisorDemo(output);
begin
writeln ('GCD(', 49865, ', ', 69811, '): ', gcd_iterative(49865, 69811), ' (iterative)');
writeln ('GCD(', 49865, ', ', 69811, '): ', gcd_recursive(49865, 69811), ' (recursive)');
writeln ('GCD(', 49865, ', ', 69811, '): ', gcd_binary (49865, 69811), ' (binary)');
end.

Output:

GCD(49865, 69811): 9973 (iterative)
GCD(49865, 69811): 9973 (recursive)
GCD(49865, 69811): 9973 (binary)

[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] Modules

All three modules will take large integers as input, e.g. gcd("68095260063025322303723429387", "51306142182612010300800963053"). Other possibilities are Math::Cephes euclid, Math::GMPz gcd and gcd_ui.

# Fastest, takes multiple inputs
use Math::Prime::Util "gcd";
$gcd = gcd(49865, 69811);
 
# In CORE. Slowest, takes multiple inputs, result is a Math::BigInt unless converted
use Math::BigInt;
$gcd = Math::BigInt::bgcd(49865, 69811)->numify;
 
# Result is a Math::Pari object unless converted
use Math::Pari "gcd";
$gcd = gcd(49865, 69811)->pari2iv
 

[edit] Notes on performance

use Benchmark qw(cmpthese);
use Math::BigInt;
use Math::Pari;
use Math::Prime::Util;
 
my $u = 40902;
my $v = 24140;
cmpthese(-5, {
'gcd_rec' => sub { gcd($u, $v); },
'gcd_iter' => sub { gcd_iter($u, $v); },
'gcd_bin' => sub { gcd_bin($u, $v); },
'gcd_bigint' => sub { Math::BigInt::bgcd($u,$v)->numify(); },
'gcd_pari' => sub { Math::Pari::gcd($u,$v)->pari2iv(); },
'gcd_mpu' => sub { Math::Prime::Util::gcd($u,$v); },
});

Output on 'Intel i3930k 4.2GHz' / Linux / Perl 5.20:

                Rate gcd_bigint   gcd_bin   gcd_rec  gcd_iter gcd_pari   gcd_mpu
gcd_bigint   39939/s         --      -83%      -94%      -95%     -98%      -99%
gcd_bin     234790/s       488%        --      -62%      -70%     -88%      -97%
gcd_rec     614750/s      1439%      162%        --      -23%     -68%      -91%
gcd_iter    793422/s      1887%      238%       29%        --     -58%      -89%
gcd_pari   1896544/s      4649%      708%      209%      139%       --      -73%
gcd_mpu    7114798/s     17714%     2930%     1057%      797%     275%        --

[edit] Perl 6

[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] Concise

my &gcd = { (abs $^a, abs $^b, * % * ... 0)[*-2] }

[edit] Actually, it's a built-in infix

my $gcd = $a gcd $b;

Because it's an infix, you can use it with various meta-operators:

[gcd] @list;         # reduce with gcd
@alist Zgcd @blist; # lazy zip with gcd
@alist Xgcd @blist; # lazy cross with gcd
@alist »gcd« @blist; # parallel gcd

[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] PostScript

Library: initlib
 
/gcd {
{
{0 gt} {dup rup mod} {pop exit} ifte
} loop
}.
 

[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] Purity

 
data Iterate = f => FoldNat <const id, g => $g . $f>
 
data Sub = Iterate Pred
data IsZero = <const True, const False> . UnNat
 
data Eq = FoldNat
<
const IsZero,
eq => n => IfThenElse (IsZero $n)
False
($eq (Pred $n))
>
 
data step = gcd => n => m =>
IfThenElse (Eq $m $n)
(Pair $m $n)
(IfThenElse (Compare Leq $n $m)
($gcd (Sub $m $n) $m)
($gcd (Sub $n $m) $n))
 
data gcd = Iterate (gcd => uncurry (step (curry $gcd)))
 

[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] Qi

 
(define gcd
A 0 -> A
A B -> (gcd B (MOD A B)))
 

[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] Racket

Racket provides a built-in gcd function. Here's a program that computes the gcd of 14 and 63:

#lang racket
 
(gcd 14 63)

Here's an explicit implementation. Note that since Racket is tail-calling, the memory behavior of this program is "loop-like", in the sense that this program will consume no more memory than a loop-based implementation.

#lang racket
 
;; given two nonnegative integers, produces their greatest
;; common divisor using Euclid's algorithm
(define (gcd a b)
(if (= b 0)
a
(gcd b (modulo a b))))
 
;; some test cases!
(module+ test
(require rackunit)
(check-equal? (gcd (* 2 3 3 7 7)
(* 3 3 7 11))
(* 3 3 7))
(check-equal? (gcd 0 14) 14)
(check-equal? (gcd 13 0) 13))

[edit] Rascal

[edit] Iterative Euclidean algorithm

 
public int gcd_iterative(int a, b){
if(a == 0) return b;
while(b != 0){
if(a > b) a -= b;
else b -= a;}
return a;
}
 

An example:

 
rascal>gcd_iterative(1989, 867)
int: 51
 

[edit] Recursive Euclidean algorithm

 
public int gcd_recursive(int a, b){
return (b == 0) ? a : gcd_recursive(b, a%b);
}
 

An example:

 
rascal>gcd_recursive(1989, 867)
int: 51
 

[edit] Raven

[edit] Recursive Euclidean algorithm

define gcd use $u, $v
$v 0 > if
$u $v % $v gcd
else
$u abs
 
24140 40902 gcd
Output:
34

[edit] REBOL

gcd: func [
{Returns the greatest common divisor of m and n.}
m [integer!]
n [integer!]
/local k
] [
; Euclid's algorithm
while [n > 0] [
k: m
m: n
n: k // m
]
m
]

[edit] Retro

This is from the math extensions library.

: gcd ( ab-n ) [ tuck mod dup ] while drop ;

[edit] REXX

[edit] version 1

The GCD subroutine can handle more than two arguments.
It also can handle any number of integers within any argument(s), making it easier to use when
computing Frobenius numbers (also known as postage stamp or coin numbers).

/*REXX pgm finds GCD (Greatest Common Divisor) of any number of integers*/
numeric digits 2000 /*handle up to 2K digit numbers.*/
call gcd 0 0  ; call gcd 55 0  ; call gcd 0 66
call gcd 7,21  ; call gcd 41,47  ; call gcd 99 , 51
call gcd 24, -8  ; call gcd -36, 9  ; call gcd -54, -6
call gcd 14 0 7  ; call gcd 14 7 0  ; call gcd 0 14 7
call gcd 15 10 20 30 55 ; call gcd 137438691328 2305843008139952128 /*◄──two perfect numbers.*/
exit /*stick a fork in it, we're done.*/
/*──────────────────────────────────GCD subroutine──────────────────────*/
gcd: procedure; $=; do i=1 for arg(); $=$ arg(i); end /*arg list.*/
parse var $ x z .; if x=0 then x=z; x=abs(x) /*handle special 0 case.*/
 
do j=2 to words($); y=abs(word($,j)); if y=0 then iterate
do until _==0; _=x//y; x=y; y=_; end /*◄── the heavy lifting.*/
end /*j*/
 
say 'GCD (Greatest Common Divisor) of ' translate(space($),",",' ') " is " x
return x

output

GCD (Greatest Common Divisor) of  0,0   is   0
GCD (Greatest Common Divisor) of  55,0   is   55
GCD (Greatest Common Divisor) of  0,66   is   66
GCD (Greatest Common Divisor) of  7,21   is   7
GCD (Greatest Common Divisor) of  41,47   is   1
GCD (Greatest Common Divisor) of  99,51   is   3
GCD (Greatest Common Divisor) of  24,-8   is   8
GCD (Greatest Common Divisor) of  -36,9   is   9
GCD (Greatest Common Divisor) of  -54,-6   is   6
GCD (Greatest Common Divisor) of  14,0,7   is   7
GCD (Greatest Common Divisor) of  14,7,0   is   7
GCD (Greatest Common Divisor) of  0,14,7   is   7
GCD (Greatest Common Divisor) of  15,10,20,30,55   is   5
GCD (Greatest Common Divisor) of  137438691328,2305843008139952128   is   262144

[edit] version 2

Recursive function (as in PL/I):

 
/* REXX ***************************************************************
* using PL/I code extended to many arguments
* 17.08.2012 Walter Pachl
* 18.08.2012 gcd(0,0)=0
**********************************************************************/

numeric digits 300 /*handle up to 300 digit numbers.*/
Call test 7,21 ,'7 '
Call test 4,7 ,'1 '
Call test 24,-8 ,'8'
Call test 55,0 ,'55'
Call test 99,15 ,'3 '
Call test 15,10,20,30,55,'5'
Call test 496,8128 ,'16'
Call test 496,8128 ,'8' /* test wrong expectation */
Call test 0,0 ,'0' /* by definition */
Exit
 
test:
/**********************************************************************
* Test the gcd function
**********************************************************************/

n=arg() /* Number of arguments */
gcde=arg(n) /* Expected result */
gcdx=gcd(arg(1),arg(2)) /* gcd of the first 2 numbers */
Do i=2 To n-2 /* proceed with all te others */
If arg(i+1)<>0 Then
gcdx=gcd(gcdx,arg(i+1))
End
If gcdx=arg(arg()) Then /* result is as expected */
tag='as expected'
Else /* result is not correct */
Tag='*** wrong. expected:' gcde
numbers=arg(1) /* build sting to show the input */
Do i=2 To n-1
numbers=numbers 'and' arg(i)
End
say left('the GCD of' numbers 'is',45) right(gcdx,3) tag
Return
 
GCD: procedure
/**********************************************************************
* Recursive procedure as shown in PL/I
**********************************************************************/

Parse Arg a,b
if b = 0 then return abs(a)
return GCD(b,a//b)

Output:

the GCD of 7 and 21 is                          7 as expected              
the GCD of 4 and 7 is                           1 as expected              
the GCD of 24 and -8 is                         8 as expected              
the GCD of 55 and 0 is                         55 as expected              
the GCD of 99 and 15 is                         3 as expected              
the GCD of 15 and 10 and 20 and 30 and 55 is    5 as expected              
the GCD of 496 and 8128 is                     16 as expected              
the GCD of 496 and 8128 is                     16 *** wrong. expected: 8  
the GCD of 0 and 0 is                           0 as expected   

[edit] Ruby

That is already available as the gcd method of integers:

irb(main):001:0> require 'rational'#Not necessary in Ruby 1.9+
=> 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] Run BASIC

print abs(gcd(-220,160))
function gcd(gcd,b)
while b
c = gcd
gcd = b
b = c mod b
wend
end function


[edit] Rust

[edit] Built-in

use std::num::gcd;

[edit] Iterative Euclid algorithm

fn gcd(mut m: int, mut n: int) -> int {
while m != 0 {
let temp = m;
m = n % temp;
n = temp;
}
n.abs()
}

[edit] Recursive Euclid algorithm

fn gcd(m: int, n: int) -> int {
if m == 0
{ n.abs() }
else
{ gcd(n % m, m) }
}

[edit] Tests

 
println!("{}",gcd(399,-3999));
println!("{}",gcd(0,3999));
println!("{}",gcd(13*13,13*29));
 
3
3999
13

[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)

Using pattern matching

@tailrec
def gcd(a: Int, b: Int): Int = {
b match {
case 0 => a
case _ => 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] Sed

#! /bin/sed -nf
 
# gcd.sed Copyright (c) 2010 by Paweł Zuzelski <[email protected]>
# dc.sed Copyright (c) 1995 - 1997 by Greg Ubben <[email protected]>
 
# usage:
#
# echo N M | ./gcd.sed
#
# Computes the greatest common divisor of N and M integers using euclidean
# algorithm.
 
s/^/|P|K0|I10|O10|?~/
 
s/$/ [lalb%sclbsalcsblb0<F]sF sasblFxlap/
 
:next
s/|?./|?/
s/|?#[ -}]*/|?/
/|?!*[lLsS;:<>=]\{0,1\}$/N
/|?!*[-+*/%^<>=]/b binop
/^|.*|?[dpPfQXZvxkiosStT;:]/b binop
/|?[_0-9A-F.]/b number
/|?\[/b string
/|?l/b load
/|?L/b Load
/|?[sS]/b save
/|?c/ s/[^|]*//
/|?d/ s/[^~]*~/&&/
/|?f/ s//&[pSbz0<aLb]dSaxsaLa/
/|?x/ s/\([^~]*~\)\(.*|?x\)~*/\2\1/
/|?[KIO]/ s/.*|\([KIO]\)\([^|]*\).*|?\1/\2~&/
/|?T/ s/\.*0*~/~/
# a slow, non-stackable array implementation in dc, just for completeness
# A fast, stackable, associative array implementation could be done in sed
# (format: {key}value{key}value...), but would be longer, like load & save.
/|?;/ s/|?;\([^{}]\)/|?~[s}s{L{s}q]S}[S}l\1L}1-d0>}s\1L\1l{xS\1]dS{xL}/
/|?:/ s/|?:\([^{}]\)/|?~[s}L{s}L{s}L}s\1q]S}S}S{[L}1-d0>}S}l\1s\1L\1l{xS\1]dS{x/
/|?[ ~ cdfxKIOT]/b next
/|?\n/b next
/|?[pP]/b print
/|?k/ s/^\([0-9]\{1,3\}\)\([.~].*|K\)[^|]*/\2\1/
/|?i/ s/^\(-\{0,1\}[0-9]*\.\{0,1\}[0-9]\{1,\}\)\(~.*|I\)[^|]*/\2\1/
/|?o/ s/^\(-\{0,1\}[1-9][0-9]*\.\{0,1\}[0-9]*\)\(~.*|O\)[^|]*/\2\1/
/|?[kio]/b pop
/|?t/b trunc
/|??/b input
/|?Q/b break
/|?q/b quit
h
/|?[XZz]/b count
/|?v/b sqrt
s/.*|?\([^Y]\).*/\1 is unimplemented/
s/\n/\\n/g
l
g
b next
 
:print
/^-\{0,1\}[0-9]*\.\{0,1\}[0-9]\{1,\}~.*|?p/!b Print
/|O10|/b Print
 
# Print a number in a non-decimal output base. Uses registers a,b,c,d.
# Handles fractional output bases (O<-1 or O>=1), unlike other dc's.
# Converts the fraction correctly on negative output bases, unlike
# UNIX dc. Also scales the fraction more accurately than UNIX dc.
#
s,|?p,&KSa0kd[[-]Psa0la-]Sad0>a[0P]sad0=a[A*2+]saOtd0>a1-ZSd[[[[ ]P]sclb1\
!=cSbLdlbtZ[[[-]P0lb-sb]sclb0>c1+]sclb0!<c[0P1+dld>c]scdld>cscSdLbP]q]Sb\
[t[1P1-d0<c]scd0<c]ScO_1>bO1!<cO[16]<bOX0<b[[q]sc[dSbdA>c[A]sbdA=c[B]sbd\
B=c[C]sbdC=c[D]sbdD=c[E]sbdE=c[F]sb]xscLbP]~Sd[dtdZOZ+k1O/Tdsb[.5]*[.1]O\
X^*dZkdXK-1+ktsc0kdSb-[Lbdlb*lc+tdSbO*-lb0!=aldx]dsaxLbsb]sad1!>a[[.]POX\
+sb1[SbO*dtdldx-LbO*dZlb!<a]dsax]sadXd0<asbsasaLasbLbscLcsdLdsdLdLak[]pP,
b next
 
:Print
/|?p/s/[^~]*/&\
~&/
s/\(.*|P\)\([^|]*\)/\
\2\1/
s/\([^~]*\)\n\([^~]*\)\(.*|P\)/\1\3\2/
h
s/~.*//
/./{ s/.//; p; }
# Just s/.//p would work if we knew we were running under the -n option.
# Using l vs p would kind of do \ continuations, but would break strings.
g
 
:pop
s/[^~]*~//
b next
 
:load
s/\(.*|?.\)\(.\)/\20~\1/
s/^\(.\)0\(.*|r\1\([^~|]*\)~\)/\1\3\2/
s/.//
b next
 
:Load
s/\(.*|?.\)\(.\)/\2\1/
s/^\(.\)\(.*|r\1\)\([^~|]*~\)/|\3\2/
/^|/!i\
register empty
s/.//
b next
 
:save
s/\(.*|?.\)\(.\)/\2\1/
/^\(.\).*|r\1/ !s/\(.\).*|/&r\1|/
/|?S/ s/\(.\).*|r\1/&~/
s/\(.\)\([^~]*~\)\(.*|r\1\)[^~|]*~\{0,1\}/\3\2/
b next
 
:quit
t quit
s/|?[^~]*~[^~]*~/|?q/
t next
# Really should be using the -n option to avoid printing a final newline.
s/.*|P\([^|]*\).*/\1/
q
 
:break
s/[0-9]*/&;987654321009;/
:break1
s/^\([^;]*\)\([1-9]\)\(0*\)\([^1]*\2\(.\)[^;]*\3\(9*\).*|?.\)[^~]*~/\1\5\6\4/
t break1
b pop
 
:input
N
s/|??\(.*\)\(\n.*\)/|?\2~\1/
b next
 
:count
/|?Z/ s/~.*//
/^-\{0,1\}[0-9]*\.\{0,1\}[0-9]\{1,\}$/ s/[-.0]*\([^.]*\)\.*/\1/
/|?X/ s/-*[0-9A-F]*\.*\([0-9A-F]*\).*/\1/
s/|.*//
/~/ s/[^~]//g
 
s/./a/g
:count1
s/a\{10\}/b/g
s/b*a*/&a9876543210;/
s/a.\{9\}\(.\).*;/\1/
y/b/a/
/a/b count1
G
/|?z/ s/\n/&~/
s/\n[^~]*//
b next
 
:trunc
# for efficiency, doesn't pad with 0s, so 10k 2 5/ returns just .40
# The X* here and in a couple other places works around a SunOS 4.x sed bug.
s/\([^.~]*\.*\)\(.*|K\([^|]*\)\)/\3;9876543210009909:\1,\2/
:trunc1
s/^\([^;]*\)\([1-9]\)\(0*\)\([^1]*\2\(.\)[^:]*X*\3\(9*\)[^,]*\),\([0-9]\)/\1\5\6\4\7,/
t trunc1
s/[^:]*:\([^,]*\)[^~]*/\1/
b normal
 
:number
s/\(.*|?\)\(_\{0,1\}[0-9A-F]*\.\{0,1\}[0-9A-F]*\)/\2~\1~/
s/^_/-/
/^[^A-F~]*~.*|I10|/b normal
/^[-0.]*~/b normal
s:\([^.~]*\)\.*\([^~]*\):[Ilb^lbk/,\1\2~0A1B2C3D4E5F1=11223344556677889900;.\2:
:digit
s/^\([^,]*\),\(-*\)\([0-F]\)\([^;]*\(.\)\3[^1;]*\(1*\)\)/I*+\1\2\6\5~,\2\4/
t digit
s:...\([^/]*.\)\([^,]*\)[^.]*\(.*|?.\):\2\3KSb[99]k\1]SaSaXSbLalb0<aLakLbktLbk:
b next
 
:string
/|?[^]]*$/N
s/\(|?[^]]*\)\[\([^]]*\)]/\1|{\2|}/
/|?\[/b string
s/\(.*|?\)|{\(.*\)|}/\2~\1[/
s/|{/[/g
s/|}/]/g
b next
 
:binop
/^[^~|]*~[^|]/ !i\
stack empty
//!b next
/^-\{0,1\}[0-9]*\.\{0,1\}[0-9]\{1,\}~/ !s/[^~]*\(.*|?!*[^!=<>]\)/0\1/
/^[^~]*~-\{0,1\}[0-9]*\.\{0,1\}[0-9]\{1,\}~/ !s/~[^~]*\(.*|?!*[^!=<>]\)/~0\1/
h
/|?\*/b mul
/|?\//b div
/|?%/b rem
/|?^/b exp
 
/|?[+-]/ s/^\(-*\)\([^~]*~\)\(-*\)\([^~]*~\).*|?\(-\{0,1\}\).*/\2\4s\3o\1\3\5/
s/\([^.~]*\)\([^~]*~[^.~]*\)\(.*\)/<\1,\2,\3|=-~.0,123456789<></
/^<\([^,]*,[^~]*\)\.*0*~\1\.*0*~/ s/</=/
:cmp1
s/^\(<[^,]*\)\([0-9]\),\([^,]*\)\([0-9]\),/\1,\2\3,\4/
t cmp1
/^<\([^~]*\)\([^~]\)[^~]*~\1\(.\).*|=.*\3.*\2/ s/</>/
/|?/{
s/^\([<>]\)\(-[^~]*~-.*\1\)\(.\)/\3\2/
s/^\(.\)\(.*|?!*\)\1/\2!\1/
s/|?![^!]\(.\)/&l\1x/
s/[^~]*~[^~]*~\(.*|?\)!*.\(.*\)|=.*/\1\2/
b next
}
s/\(-*\)\1|=.*/;9876543210;9876543210/
/o-/ s/;9876543210/;0123456789/
s/^>\([^~]*~\)\([^~]*~\)s\(-*\)\(-*o\3\(-*\)\)/>\2\1s\5\4/
 
s/,\([0-9]*\)\.*\([^,]*\),\([0-9]*\)\.*\([0-9]*\)/\1,\2\3.,\4;0/
:right1
s/,\([0-9]\)\([^,]*\),;*\([0-9]\)\([0-9]*\);*0*/\1,\2\3,\4;0/
t right1
s/.\([^,]*\),~\(.*\);0~s\(-*\)o-*/\1~\30\2~/
 
:addsub1
s/\(.\{0,1\}\)\(~[^,]*\)\([0-9]\)\(\.*\),\([^;]*\)\(;\([^;]*\(\3[^;]*\)\).*X*\1\(.*\)\)/\2,\4\5\9\8\7\6/
s/,\([^~]*~\).\{10\}\(.\)[^;]\{0,9\}\([^;]\{0,1\}\)[^;]*/,\2\1\3/
# could be done in one s/// if we could have >9 back-refs...
/^~.*~;/!b addsub1
 
:endbin
s/.\([^,]*\),\([0-9.]*\).*/\1\2/
G
s/\n[^~]*~[^~]*//
 
:normal
s/^\(-*\)0*\([0-9.]*[0-9]\)[^~]*/\1\2/
s/^[^1-9~]*~/0~/
b next
 
:mul
s/\(-*\)\([0-9]*\)\.*\([0-9]*\)~\(-*\)\([0-9]*\)\.*\([0-9]*\).*|K\([^|]*\).*/\1\4\2\5.!\3\6,|\2<\3~\5>\6:\7;9876543210009909/
 
:mul1
s/![0-9]\([^<]*\)<\([0-9]\{0,1\}\)\([^>]*\)>\([0-9]\{0,1\}\)/0!\1\2<\3\4>/
/![0-9]/ s/\(:[^;]*\)\([1-9]\)\(0*\)\([^0]*\2\(.\).*X*\3\(9*\)\)/\1\5\6\4/
/<~[^>]*>:0*;/!t mul1
 
s/\(-*\)\1\([^>]*\).*/;\2^>:9876543210aaaaaaaaa/
 
:mul2
s/\([0-9]~*\)^/^\1/
s/<\([0-9]*\)\(.*[~^]\)\([0-9]*\)>/\1<\2>\3/
 
 :mul3
s/>\([0-9]\)\(.*\1.\{9\}\(a*\)\)/\1>\2;9\38\37\36\35\34\33\32\31\30/
s/\(;[^<]*\)\([0-9]\)<\([^;]*\).*\2[0-9]*\(.*\)/\4\1<\2\3/
s/a[0-9]/a/g
s/a\{10\}/b/g
s/b\{10\}/c/g
/|0*[1-9][^>]*>0*[1-9]/b mul3
 
s/;/a9876543210;/
s/a.\{9\}\(.\)[^;]*\([^,]*\)[0-9]\([.!]*\),/\2,\1\3/
y/cb/ba/
/|<^/!b mul2
b endbin
 
:div
# CDDET
/^[-.0]*[1-9]/ !i\
divide by 0
//!b pop
s/\(-*\)\([0-9]*\)\.*\([^~]*~-*\)\([0-9]*\)\.*\([^~]*\)/\2.\3\1;0\4.\5;0/
:div1
s/^\.0\([^.]*\)\.;*\([0-9]\)\([0-9]*\);*0*/.\1\2.\3;0/
s/^\([^.]*\)\([0-9]\)\.\([^;]*;\)0*\([0-9]*\)\([0-9]\)\./\1.\2\30\4.\5/
t div1
s/~\(-*\)\1\(-*\);0*\([^;]*[0-9]\)[^~]*/~123456789743222111~\2\3/
s/\(.\(.\)[^~]*\)[^9]*\2.\{8\}\(.\)[^~]*/\3~\1/
s,|?.,&SaSadSaKdlaZ+LaX-1+[sb1]Sbd1>bkLatsbLa[dSa2lbla*-*dLa!=a]dSaxsakLasbLb*t,
b next
 
:rem
s,|?%,&Sadla/LaKSa[999]k*Lak-,
b next
 
:exp
# This decimal method is just a little faster than the binary method done
# totally in dc: 1LaKLb [kdSb*LbK]Sb [[.5]*d0ktdSa<bkd*KLad1<a]Sa d1<a kk*
/^[^~]*\./i\
fraction in exponent ignored
s,[^-0-9].*,;9d**dd*8*d*d7dd**d*6d**d5d*d*4*d3d*2lbd**1lb*0,
:exp1
s/\([0-9]\);\(.*\1\([d*]*\)[^l]*\([^*]*\)\(\**\)\)/;dd*d**d*\4\3\5\2/
t exp1
G
s,-*.\{9\}\([^9]*\)[^0]*0.\(.*|?.\),\2~saSaKdsaLb0kLbkK*+k1\1LaktsbkLax,
s,|?.,&SadSbdXSaZla-SbKLaLadSb[0Lb-d1lb-*d+K+0kkSb[1Lb/]q]Sa0>a[dk]sadK<a[Lb],
b next
 
:sqrt
# first square root using sed: 8k2v at 1:30am Dec 17, 1996
/^-/i\
square root of negative number
/^[-0]/b next
s/~.*//
/^\./ s/0\([0-9]\)/\1/g
/^\./ !s/[0-9][0-9]/7/g
G
s/\n/~/
s,|?.,&K1+k KSbSb[dk]SadXdK<asadlb/lb+[.5]*[sbdlb/lb+[.5]*dlb>a]dsaxsasaLbsaLatLbk K1-kt,
b next
 
# END OF GSU dc.sed

[edit] Seed7

const func integer: gcd (in var integer: a, in var integer: b) is func
result
var integer: gcd is 0;
local
var integer: help is 0;
begin
while a <> 0 do
help := b rem a;
b := a;
a := help;
end while;
gcd := 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] Sidef

[edit] Built-in

var arr = [100, 1_000, 10_000, 20];
var gcd = Math.gcd(arr->asList);

[edit] Recursive Euclid algorithm

func gcd(a, b) {
b.isZero ?: (a.abs; gcd(b, a % b));
}

[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 reimplementation of the Iterative Euclid's algorithm would be:

|gcd_iter|
 
gcd_iter := [ :a :b |
|u v|
u := a. v := b.
[ v > 0 ]
whileTrue: [ |t|
t := u.
u := v.
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] Sparkling

function factors(n) {
var f = {};
 
for var i = 2; n > 1; i++ {
while n % i == 0 {
n /= i;
f[i] = f[i] != nil ? f[i] + 1 : 1;
}
}
 
return f;
}
 
function GCD(n, k) {
let f1 = factors(n);
let f2 = factors(k);
 
let fs = map(f1, function(factor, multiplicity) {
let m = f2[factor];
return m == nil ? 0 : min(m, multiplicity);
});
 
let rfs = {};
foreach(fs, function(k, v) {
rfs[sizeof rfs] = pow(k, v);
});
 
return reduce(rfs, 1, function(x, y) { return x * y; });
}
 
function LCM(n, k) {
return n * k / GCD(n, k);
}

[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] TSE SAL

 
 
// library: math: get: greatest: common: divisor <description>greatest common divisor whole numbers. Euclid's algorithm. Recursive version</description> <version control></version control> <version>1.0.0.0.3</version> <version control></version control> (filenamemacro=getmacdi.s) [<Program>] [<Research>] [kn, ri, su, 20-01-2013 14:22:41]
INTEGER PROC FNMathGetGreatestCommonDivisorI( INTEGER x1I, INTEGER x2I )
//
IF ( x2I == 0 )
//
RETURN( x1I )
//
ENDIF
//
RETURN( FNMathGetGreatestCommonDivisorI( x2I, x1I MOD x2I ) )
//
END
 
PROC Main()
STRING s1[255] = "353"
STRING s2[255] = "46"
REPEAT
IF ( NOT ( Ask( " = ", s1, _EDIT_HISTORY_ ) ) AND ( Length( s1 ) > 0 ) ) RETURN() ENDIF
IF ( NOT ( Ask( " = ", s2, _EDIT_HISTORY_ ) ) AND ( Length( s2 ) > 0 ) ) RETURN() ENDIF
Warn( FNMathGetGreatestCommonDivisorI( Val( s1 ), Val( s2 ) ) ) // gives e.g. 1
UNTIL FALSE
END
 
 


[edit] TXR

$ txr -c @(bind g @(gcd (expt 2 123) (expt 6 49)))
g="562949953421312"

[edit] UNIX Shell

Works with: Bourne Shell
gcd() {
# Calculate $1 % $2 until $2 becomes zero.
until test 0 -eq "$2"; do
# Parallel assignment: set -- 1 2
set -- "$2" "`expr "$1" % "$2"`"
done
 
# Echo absolute value of $1.
test 0 -gt "$1" && set -- "`expr 0 - "$1"`"
echo "$1"
}
 
gcd -47376 87843
# => 987

[edit] C Shell

alias gcd eval \''set gcd_args=( \!*:q )	\\
@ gcd_u=$gcd_args[2] \\
@ gcd_v=$gcd_args[3] \\
while ( $gcd_v != 0 ) \\
@ gcd_t = $gcd_u % $gcd_v \\
@ gcd_u = $gcd_v \\
@ gcd_v = $gcd_t \\
end \\
if ( $gcd_u < 0 ) @ gcd_u = - $gcd_u \\
@ $gcd_args[1]=$gcd_u \\
'\'
 
gcd result -47376 87843
echo $result
# => 987

[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

[edit] VBA

This function uses repeated subtractions. Simple but not very efficient.

 
Public Function GCD(a As Long, b As Long) As Long
While a <> b
If a > b Then a = a - b Else b = b - a
Wend
GCD = a
End Function
 

Example:

print GCD(1280, 240)
 80 
print GCD(3475689, 23566319)
 7
a=123456789
b=234736437
print GCD((a),(b))
 3 

A note on the last example: using brackets forces a and b to be evaluated before GCD is called. Not doing this will cause a compile error because a and b are not the same type as in the function declaration (they are Variant, not Long). Alternatively you can use the conversion function CLng as in print GCD(CLng(a),CLng(b))

[edit] Wortel

Operator

@gcd a b

Number expression

!#~kg a b

Iterative

&[a b] [@vars[t] @while b @:{t b b %a b a t} a]

Recursive

&{gcd a b} ?{b !!gcd b %a b @abs a}

[edit] x86 Assembly

Using GNU Assembler syntax:

.text
.global pgcd
 
pgcd:
push  %ebp
mov  %esp, %ebp
 
mov 8(%ebp), %eax
mov 12(%ebp), %ecx
push  %edx
 
.loop:
cmp $0, %ecx
je .end
xor  %edx, %edx
div  %ecx
mov  %ecx, %eax
mov  %edx, %ecx
jmp .loop
 
.end:
pop  %edx
leave
ret

[edit] XPL0

include c:\cxpl\codes;
 
func GCD(U, V); \Return the greatest common divisor of U and V
int U, V;
int T;
[while V do \Euclid's method
[T:= U; U:= V; V:= rem(T/V)];
return abs(U);
];
 
\Display the GCD of two integers entered on command line
IntOut(0, GCD(IntIn(8), IntIn(8)))

[edit] zkl

Use the gnu big num library:

var BN=Import("zklBigNum");
BN(123456789).gcd(987654321) //-->9

or

fcn gcd(a,b){while(b){t:=a; a=b; b=t%b} a.abs()}
Personal tools
Namespaces

Variants
Actions
Community
Explore
Misc
Toolbox