Greatest common divisor

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.

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

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

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

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

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

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

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

AutoHotkey

contributed by Laszlo on the ahk forum

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

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.

BASIC

Works with: QuickBasic version 4.5

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

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

BBC BASIC

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

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

Befunge

#v&<     @.$<
:<\g05%p05:_^#

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

C/C++

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) */
}

Recursive Euclid algorithm

int
gcd(int u, int v) {
  if (v)
    return gcd(v, u % v);
  else 
    return u < 0 ? -u : u; /* abs(u) */
}

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

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

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.

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.

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

CoffeeScript

Simple recursion

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

Using a simple for loop.

 
ggt = (x,y) ->
  max_teiler = Math.min(x,y)
  ggt = 0
  for teiler in [1..max_teiler]
    if x % teiler == 0 and y % teiler == 0
      ggt = teiler
  return ggt
 
alert ggt(40902,24140)
 

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

D

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

Output:

5
5

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'

DWScript

PrintLn(Gcd(231, 210));

Output:

21

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()
}

Emacs Lisp

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

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

Euphoria

Translation of: C/C++

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

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

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

F#

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

Factor

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

FALSE

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

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

Forth

: gcd ( a b -- n )
  begin dup while tuck mod repeat drop ;

Fortran

Works with: Fortran version 95 and later

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

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

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

Notes on performance

gcd_iter(40902, 24140) takes us about 2.8 µsec

gcd_bin(40902, 24140) takes us about 2.5 µsec

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

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

Genyris

Recursive

def gcd (u v)
    u = (abs u)
    v = (abs v)
    cond
       (equal? v 0) u
       else (gcd v (% u v))

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

gnuplot

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

Example:

print gcd (111111, 1111)

Output:

11

Go

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

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

Groovy

Recursive

def gcdR
gcdR = { m, n -> m = m.abs(); n = n.abs(); n == 0 ? m : m%n == 0 ? n : gcdR(n, m%n) }

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

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)

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

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

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

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

Java

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

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

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

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

Built-in

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

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

Joy

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

K

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

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.

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 
 

Logo

to gcd :a :b
  if :b = 0 [output :a]
  output gcd :b  modulo :a :b
end

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

Lucid

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

Mathematica

GCD[a, b]

MATLAB

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

MAXScript

Iterative Euclid algorithm

fn gcdIter a b =
(
    while b > 0 do
    (
        c = mod a b
        a = b
        b = c
    )
    abs a
)

Recursive Euclid algorithm

fn gcdRec a b =
(
    if b > 0 then gcdRec b (mod a b) else abs a
)

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

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

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

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

NewLISP

(gcd 12 36)  
  → 12

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

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

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)

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

Octave

r = gcd(a, b)

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}}

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

Pascal

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;

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;

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)

Perl

Iterative Euclid algorithm

sub gcd_iter($$) {
  my ($u, $v) = @_;
  while ($v) {
    ($u, $v) = ($v, $u % $v);
  }
  return abs($u);
}

Recursive Euclid algorithm

sub gcd($$) {
  my ($u, $v) = @_;
  if ($v) {
    return gcd($v, $u % $v);
  } else {
    return abs($u);
  }
}

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

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%       --

Built-in

use Math::BigInt;
 
sub gcd($$) {
  Math::BigInt::bgcd(@_)->numify();
}

Perl 6

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

Recursive

multi gcd (0,      0)      { fail }
multi gcd (Int $a, 0)      { abs $a }
multi gcd (Int $a, Int $b) { gcd $b, $a % $b }

Concise

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

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

PicoLisp

(de gcd (A B)
   (until (=0 B)
      (let M (% A B)
         (setq A B B M) ) )
   (abs A) )

PHP

Iterative

 
function gcdIter($n, $m) {
    while(true) {
        if($n == $m) {
            return $m;
        }
        if($n > $m) {
            $n -= $m;
        } else {
            $m -= $n;
        }
    }
}
 

Recursive

 
function gcdRec($n, $m) {
    if($m > 0) {
        return gcdRec($m, $n % $m);
    } else {
        return abs($n);
    }
}
 

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;
 

Pop11

Built-in gcd

gcd_n(15, 12, 2) =>

Note: the last argument gives the number of other arguments (in this case 2).

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;

PostScript

Library: initlib

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

PowerShell

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
}

Prolog

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

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

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

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

Python

Built-in

Works with: Python version 2.6+

from fractions import gcd

Iterative Euclid algorithm

def gcd_iter(u, v):
    while v:
        u, v = v, u % v
    return abs(u)

Recursive Euclid algorithm

Interpreter: Python 2.5

def gcd(u, v):
    return gcd(v, u % v) if v else abs(u)

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

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

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

Qi

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

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)

Rascal

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
 

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
 

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
]

Retro

This is from the math extensions library.

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

REXX

The GCD subroutine can handle more than two arguments.

/*REXX program to find GCD (greatest common divisor) of 2 (or more) ints*/
numeric digits 300                     /*handle up to 300 digit numbers.*/
 
say 'the GCD of   7  and  21                     is'  gcd( 7,21)
say 'the GCD of   4  and   7                     is'  gcd( 4,7)
say 'the GCD of  24  and  -8                     is'  gcd(24,-8)
say 'the GCD of  55  and   0                     is'  gcd(55,0)
say 'the GCD of  99  and  51                     is'  gcd(99,15)
say 'the GCD of  15 and 10 and 20 and 30 and 55  is'  gcd(15,10,20,30,55)
say 'the GCD of  496  and  8128                  is'  gcd(496,8128)
exit                                   /*──(above)──two perfect numbers.*/
 
/*─────────────────────────────────────GCD subroutine───any num of args.*/
gcd: procedure; parse arg x,y          /*find  greatest common divisor. */
x=abs(x);  if x=0 then return 0        /*get  |x|,   then test for zero.*/
 
  do j=2 to arg()                      /*traipse through all arguments. */
  y=abs(arg(j)); if y=0 then return x  /*get   |y|,  then test for zero.*/
        do until _==0                  /*keep truckin' until it's zero. */
        _=x//y;  x=y;  y=_
        end   /*until*/
  end         /*j*/
 
return x

Output:

the GCD of   7  and  21                     is 7
the GCD of   4  and   7                     is 1
the GCD of  24  and  -8                     is 8
the GCD of  55  and   0                     is 55
the GCD of  99  and  51                     is 3
the GCD of  15 and 10 and 20 and 30 and 55  is 5
the GCD of  496  and  8128                  is 16

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

Run BASIC

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

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;

Scala

def gcd(a: Int, b: Int): Int = if (b == 0) a.abs else gcd(b, a % b)

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)

Sed

#! /bin/sed -nf
 
# gcd.sed Copyright (c) 2010        by Paweł Zuzelski <pawelz@pld-linux.org>
# dc.sed  Copyright (c) 1995 - 1997 by Greg Ubben <gsu@romulus.ncsc.mil>
 
# 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

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]

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

Slate

Slate's Integer type has gcd defined:

40902 gcd: 24140

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

Recursive Euclid algorithm

x@(Integer traits) gcd: y@(Integer traits)
[
  y isZero
    ifTrue: [x]
    ifFalse: [y gcd: x \\ y]
].

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.

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

Standard ML

fun gcd a 0 = a
  | gcd a b = gcd b (a mod b)

Tcl

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
}

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

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

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

TI-83 BASIC, TI-89 BASIC

gcd(A,B)

TXR

@(bind g @(gcd (expt 2 123) (expt 6 49)))

g="562949953421312"

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

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

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>

V

like joy

iterative

[gcd
   [0 >] [dup rollup %]
   while
   pop
].

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

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

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