Greatest common divisor

From Rosetta Code
Revision as of 14:30, 29 August 2012 by rosettacode>Gerard Schildberger (→‎version 1: changed verbage in the section header explaning argument specifications. -- ~~~~)
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.

ACL2

<lang Lisp>(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)))))</lang>

ActionScript

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

Ada

<lang 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;</lang>

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

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

)</lang> Output: 

 The gcd of        +33 and         +77 is         +11
 The gcd of     +49865 and      +69811 is       +9973


Alore

<lang 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</lang>

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. <lang awk>$ 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</lang>

AutoHotkey

contributed by Laszlo on the ahk forum <lang AutoHotkey>GCD(a,b) { 

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

}</lang>

Batch File

Recursive method <lang dos>:: 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.</lang>

BASIC

Works with: QuickBasic version 4.5

Iterative

<lang qbasic>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</lang>

Recursive

<lang qbasic>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</lang>

BBC BASIC

<lang bbcbasic> DEF FN_GCD_Iterative_Euclid(A%, B%) 

     LOCAL C%
     WHILE B%
       C% = A%
       A% = B%
       B% = C% MOD B%
     ENDWHILE
     = ABS(A%)</lang>

Bc

Works with: GNU bc
Translation of: C

Utility functions: <lang bc>define even(a) { 

 if ( a % 2 == 0 ) {
   return(1);
 } else {
   return(0);
 }

}

define abs(a) { 

 if (a<0) {
   return(-a);
 } else {
   return(a);
 }

}</lang>

Iterative (Euclid) <lang bc>define gcd_iter(u, v) { 

 while(v) {
   t = u;
   u = v;
   v = t % v;
 }
 return(abs(u));

}</lang>

Recursive

<lang bc>define gcd(u, v) { 

 if (v) {
   return ( gcd(v, u%v) );
 } else {
   return (abs(u));
 }

}</lang>

Iterative (Binary)

<lang bc>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);

}</lang>

Befunge

<lang befunge>#v&< @.$<

<\g05%p05:_^#</lang>

Bracmat

Bracmat uses the Euclidean algorithm to simplify fractions. The den function extracts the denominator from a fraction. <lang bracmat>(gcd=a b.!arg:(?a.?b)&!b*den$(!a*!b^-1)^-1);</lang> Example: 

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

C/C++

Iterative Euclid algorithm

<lang c>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) */

}</lang>

Recursive Euclid algorithm

<lang c>int gcd(int u, int v) { 

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

}</lang>

Iterative binary algorithm

<lang c>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;

}</lang>

C#

Translation of: ActionScript

<lang csharp> 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; } </lang>

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

<lang lisp>(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.</lang>

COBOL

<lang 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.</lang>

Cobra

<lang 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)]" </lang>

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 <lang coffeescript> gcd = (x, y) -> 

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

</lang>


Using a simple for loop. <lang coffeescript> 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) </lang>

Common Lisp

Common Lisp provides a gcd function.

<lang lisp>CL-USER> (gcd 2345 5432) 7</lang>

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

<lang lisp>(defun gcd2 (a b) 

 (do () ((zerop b) (abs a))
   (shiftf a b (mod a b))))</lang>

Here is a tail-recursive implementation.

<lang lisp>(defun gcd2 (a b) 

 (if (zerop b) a 
     (gcd2 b (mod a b))))</lang>

The last implementation is based on the loop macro.

<lang lisp>(defun gcd2 (a b) 

 (loop for x = a then y
       and y = b then (mod x y)
       until (zerop y)
       finally (return x)))</lang>

D

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

}</lang>

Output:
5
5

Dc

<lang dc>[dSa%Lard0<G]dsGx+</lang> This code assumes that there are two integers on the stack. 

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

DWScript

<lang delphi>PrintLn(Gcd(231, 210));</lang> Output: 

21

E

Translation of: Python

<lang e>def gcd(var u :int, var v :int) { 

   while (v != 0) {
       def r := u %% v
       u := v
       v := r
   }
   return u.abs()

}</lang>

Emacs Lisp

<lang lisp> (defun gcd (a b) 

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

</lang>

Erlang

Translation of: OCaml

<lang erlang>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).</lang>

Euphoria

Translation of: C/C++

Iterative Euclid algorithm

<lang euphoria>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</lang>

Recursive Euclid algorithm

<lang euphoria>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</lang>

Iterative binary algorithm

<lang euphoria>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</lang>

F#

<lang fsharp> let rec gcd a b = 

 if b = 0 
   then abs a
 else gcd b (a % b)

>gcd 400 600 val it : int = 200</lang>

Factor

<lang factor>: gcd ( a b -- c ) 

   [ abs ] [
       [ nip ] [ mod ] 2bi gcd
   ] if-zero ;</lang>

FALSE

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

Fantom

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

} </lang>

Forth

<lang forth>: gcd ( a b -- n ) 

 begin dup while tuck mod repeat drop ;</lang>

Fortran

Works with: Fortran version 95 and later

Recursive Euclid algorithm

<lang fortran>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</lang>

Iterative Euclid algorithm

<lang fortran>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</lang>

A different version, and implemented as function

<lang fortran>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</lang>

Iterative binary algorithm

<lang fortran>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</lang>

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.) <lang frink> println[gcd[12345,98765]] </lang>

GAP

<lang gap># Built-in GcdInt(35, 42);

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

  1. 7</lang>

Genyris

Recursive

<lang genyris>def gcd (u v) 

   u = (abs u)
   v = (abs v)
   cond
      (equal? v 0) u
      else (gcd v (% u v))</lang>

Iterative

<lang genyris>def gcd (u v) 

   u = (abs u)
   v = (abs v)
   while (not (equal? v 0))
      var tmp (% u v)
      u = v
      v = tmp
   u</lang>

gnuplot

<lang gnuplot>gcd (a, b) = b == 0 ? a : gcd (b, a % b)</lang> Example: <lang gnuplot>print gcd (111111, 1111)</lang> Output: <lang>11</lang>

Go

Iterative

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

} </lang>

Builtin

(This is just a wrapper for big.GCD) <lang go>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))

}</lang>

Output in either case:
11
9973

Groovy

Recursive

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

Iterative

<lang groovy>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 }() }</lang>

Test program: <lang groovy>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)}"</lang>

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:

<lang haskell>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)</lang>

HicEst

<lang 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</lang>

Icon and Unicon

<lang Icon>link numbers # gcd is part of the Icon Programming Library procedure main(args) 

   write(gcd(arg[1], arg[2])) | "Usage: gcd n m")

end</lang>

Library: Icon Programming Library

numbers implements this as:

<lang Icon>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</lang>

J

<lang J>x+.y</lang>

For example:

<lang J> 12 +. 30 6</lang>

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

<lang java>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;

}</lang>

Iterative Euclid's Algorithm

<lang java> 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; } </lang>

Iterative binary algorithm

Translation of: C/C++

<lang java>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;

}</lang>

Recursive

<lang java>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);

}</lang>

Built-in

<lang java>import java.math.BigInteger;

public static long gcd(long a, long b){ 

  return BigInteger.valueOf(a).gcd(BigInteger.valueOf(b)).longValue();

}</lang>

JavaScript

Iterative. <lang javascript>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;
   }

}</lang>

Recursive. <lang javascript>function gcd_rec(a, b) { 

   if (b) {
       return gcd_rec(b, a % b);
   } else {
       return Math.abs(a);
   }

}</lang>

Joy

<lang joy>DEFINE gcd == [0 >] [dup rollup rem] while pop.</lang>

K

<lang K>gcd:{:[~x;y;_f[y;x!y]]}</lang>

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

<lang lb>'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 
</lang>

<lang logo>to gcd :a :b 

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

end</lang>

Lua

Translation of: C

<lang lua>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)</lang>

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

<lang lucid>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</lang>

Mathematica

<lang mathematica>GCD[a, b]</lang>

MATLAB

<lang Matlab>function [gcdValue] = greatestcommondivisor(integer1, integer2) 

  gcdValue = gcd(integer1, integer2);</lang>

Maxima

<lang 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;</lang>

MAXScript

Iterative Euclid algorithm

<lang maxscript>fn gcdIter a b = ( 

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

)</lang>

Recursive Euclid algorithm

<lang maxscript>fn gcdRec a b = ( 

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

)</lang>

MIPS Assembly

<lang mips>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</lang>

МК-61/52

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

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

Modula-2

<lang modula2>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.</lang> Producing the output <lang Modula-2>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</lang>

Modula-3

<lang modula3>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.</lang>

Output: 

GCD of 100, 5 is 5
GCD of 5, 100 is 5
GCD of 7, 23 is 1

MUMPS

<lang 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</lang>

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

<lang NewLISP>(gcd 12 36) 

 → 12</lang>

Nial

Nial provides gcd in the standard lib. <lang nial>|loaddefs 'niallib/gcd.ndf' |gcd 6 4 =2</lang>

defining it for arrays <lang nial># red is the reduction operator for a sorted list

  1. 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 <=</lang>

Using it <lang nial>|gcd 9 6 3 =3</lang>

Objeck

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

} </lang>

OCaml

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

Built-in

<lang ocaml>#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))</lang>

Octave

<lang octave>r = gcd(a, b)</lang>

Order

Translation of: bc

<lang c>#include <order/interpreter.h>

  1. 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</lang>

Oz

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

PARI/GP

<lang parigp>gcd(a,b)</lang>

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

<lang pascal>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;</lang>

Iterative Euclid algorithm

<lang fortran>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;</lang>

Iterative binary algorithm

<lang Pascal>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;</lang>

Demo program:

<lang pascal>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.</lang> Output: 

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

Perl

Iterative Euclid algorithm

<lang perl>sub gcd_iter($$) { 

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

}</lang>

Recursive Euclid algorithm

<lang perl>sub gcd($$) { 

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

}</lang>

Iterative binary algorithm

<lang perl>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;

}</lang>

Notes on performance

<lang perl>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); },

});</lang>

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

<lang perl>use Math::BigInt;

sub gcd($$) { 

 Math::BigInt::bgcd(@_)->numify();

}</lang>

Perl 6

Iterative

<lang perl6>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;

}</lang>

Recursive

<lang perl6>multi gcd (0, 0) { fail } multi gcd (Int $a, 0) { abs $a } multi gcd (Int $a, Int $b) { gcd $b, $a % $b }</lang>

Concise

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

Actually, it's a built-in infix

<lang perl6>my $gcd = $a gcd $b;</lang> Because it's an infix, you can use it with various meta-operators: <lang perl6>[gcd] @list; # reduce with gcd @alist Zgcd @blist; # lazy zip with gcd @alist Xgcd @blist; # lazy cross with gcd @alist »gcd« @blist; # parallel gcd</lang>

PicoLisp

<lang PicoLisp>(de gcd (A B) 

  (until (=0 B)
     (let M (% A B)
        (setq A B B M) ) )
  (abs A) )</lang>

PHP

Iterative

<lang php> function gcdIter($n, $m) { 

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

} </lang>

Recursive

<lang php> function gcdRec($n, $m) { 

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

} </lang>

PL/I

<lang 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; </lang>

Pop11

Built-in gcd

<lang pop11>gcd_n(15, 12, 2) =></lang>

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

Iterative Euclid algorithm

<lang pop11>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;</lang>

PostScript

Library: initlib

<lang postscript> /gcd { { 

   {0 gt} {dup rup mod} {pop exit} ifte

} loop }. </lang>

PowerShell

Recursive Euclid Algorithm

<lang powershell>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

}</lang>

Prolog

Recursive Euclid Algorithm

<lang prolog>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).</lang>

Repeated Subtraction

<lang prolog>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).</lang>


PureBasic

Iterative <lang PureBasic>Procedure GCD(x, y) 

 Protected r
 While y <> 0
   r = x % y
   x = y
   y = r
 Wend
 ProcedureReturn y

EndProcedure</lang>

Recursive <lang PureBasic>Procedure GCD(x, y) 

 Protected r
 r = x % y
 If (r > 0)
   y = GCD(y, r)
 EndIf
 ProcedureReturn y

EndProcedure</lang>

Purity

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

Python

Built-in

Works with: Python version 2.6+

<lang python>from fractions import gcd</lang>

Iterative Euclid algorithm

<lang python>def gcd_iter(u, v): 

   while v:
       u, v = v, u % v
   return abs(u)</lang>

Recursive Euclid algorithm

Interpreter: Python 2.5 <lang python>def gcd(u, v): 

   return gcd(v, u % v) if v else abs(u)</lang>

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) <lang python>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</lang>

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

<lang Qi> (define gcd 

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

</lang>

R

<lang R>"%gcd%" <- function(u, v) { 

 ifelse(u %% v != 0, v %gcd% (u%%v), v)

}</lang>

<lang R>"%gcd%" <- function(v, t) { 

 while ( (c <- v%%t) != 0 ) {
   v <- t
   t <- c
 }

}</lang>

<lang R>print(50 %gcd% 75)</lang>

Rascal

Iterative Euclidean algorithm

<lang rascal> 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; } </lang> An example: <lang rascal> rascal>gcd_iterative(1989, 867) int: 51 </lang>

Recursive Euclidean algorithm

<lang rascal> public int gcd_recursive(int a, b){ return (b == 0) ? a : gcd_recursive(b, a%b); } </lang> An example: <lang rascal> rascal>gcd_recursive(1989, 867) int: 51 </lang>

REBOL

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

]</lang>

Retro

This is from the math extensions library.

<lang Retro>: gcd ( ab-n ) [ tuck mod dup ] while drop ;</lang>

REXX

version 1

The GCD subroutine can handle more than two arguments.
It also can handle any number of integers in any argument, making it easier to use when
computing Frobenius numbers (also known as postage stamp or coin numbers). <lang rexx>/*REXX pgm finds GCD (Greatest Common Divisor) of any number of integers*/ numeric digits 300 /*handle up to 300 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 

                                      /*(above)  two perfect numbers.  */

exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────GCD subroutine──────────────────────*/ gcd: procedure; x=0; parse arg $ /*find Greatest Common Divisor. */ 

 do i=2 to arg();  $=$ arg(i);  end   /*build list of all the integers.*/

$=space($) /*optional: elide extra blanks. */ 

           do j=1 for words($)        /*traipse through all the numbers*/
           y=abs(word($,j))           /*get the "next"   │y│           */
           if y=0 then iterate        /*handle special case of  Y=zero.*/

                 do until _==0        /*keep truckin' until it's zero. */
                 _=x//y;  x=y;  y=_
                 end   /*until*/
           end         /*j*/

say 'GCD (Greatest Common Divisor) of ' translate($,",",' ') " is " x return x</lang> 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

version 2

Recursive function (as in PL/I): <lang REXX> /* 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)</lang> 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

Ruby

That is already available as the gcd method of integers:

<lang ruby>irb(main):001:0> require 'rational' => true irb(main):002:0> 40902.gcd(24140) => 34</lang>

Here's an implementation: <lang ruby>def gcd(u, v) 

 u, v = u.abs, v.abs
 while v > 0
   u, v = v, u % v
 end
 u

end</lang>

Run BASIC

<lang Runbasic>print abs(gcd(-220,160)) function gcd(gcd,b) 

   while b
       c   = gcd
       gcd = b
       b   = c mod b
   wend

end function </lang>

Sather

Translation of: bc

<lang sather>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;</lang>

<lang sather>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;</lang>

Scala

<lang scala>def gcd(a: Int, b: Int): Int = if (b == 0) a.abs else gcd(b, a % b)</lang>

Scheme

<lang scheme>(define (gcd a b) 

 (if (= b 0)
     a
     (gcd b (modulo a b))))</lang>

or using the standard function included with Scheme (takes any number of arguments): <lang scheme>(gcd a b)</lang>

Sed

<lang sed>#! /bin/sed -nf

  1. gcd.sed Copyright (c) 2010 by Paweł Zuzelski <pawelz@pld-linux.org>
  2. dc.sed Copyright (c) 1995 - 1997 by Greg Ubben <gsu@romulus.ncsc.mil>
  1. usage:
  3. echo N M | ./gcd.sed
  5. Computes the greatest common divisor of N and M integers using euclidean
  6. 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*~/~/

  1. a slow, non-stackable array implementation in dc, just for completeness
  2. A fast, stackable, associative array implementation could be done in sed
  3. (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

  1. Print a number in a non-decimal output base. Uses registers a,b,c,d.
  2. Handles fractional output bases (O<-1 or O>=1), unlike other dc's.
  3. Converts the fraction correctly on negative output bases, unlike
  4. 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; }

  1. Just s/.//p would work if we knew we were running under the -n option.
  2. 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

  1. 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
  1. for efficiency, doesn't pad with 0s, so 10k 2 5/ returns just .40
  2. 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/

  1. 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
  1. 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
  1. This decimal method is just a little faster than the binary method done
  2. 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
  1. 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

  1. END OF GSU dc.sed</lang>

Seed7

<lang 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;</lang>

Original source: [1]

SETL

<lang 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;</lang>

Output: <lang setl>the gcd of 33 and 77 is 11 the gcd of 49865 and 69811 is 9973</lang>

Slate

Slate's Integer type has gcd defined:

<lang slate>40902 gcd: 24140</lang>

Iterative Euclid algorithm

<lang slate>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

].</lang>

Recursive Euclid algorithm

<lang slate>x@(Integer traits) gcd: y@(Integer traits) [ 

 y isZero
   ifTrue: [x]
   ifFalse: [y gcd: x \\ y]

].</lang>

Smalltalk

The Integer class has its gcd method.

<lang smalltalk>(40902 gcd: 24140) displayNl</lang>

An implementation of the Iterative Euclid's algorithm

<lang smalltalk>|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.</lang>

SNOBOL4

<lang snobol> 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</lang>

Standard ML

<lang sml>fun gcd a 0 = a 

 | gcd a b = gcd b (a mod b)</lang>

Tcl

Iterative Euclid algorithm

<lang tcl>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

}</lang>

Recursive Euclid algorithm

<lang tcl>proc gcd {p q} { 

   if {$q == 0} {
       return $p
   }
   gcd $q [expr {$p % $q}]

}</lang> With Tcl 8.6, this can be optimized slightly to: <lang tcl>proc gcd {p q} { 

   if {$q == 0} {
       return $p
   }
   tailcall gcd $q [expr {$p % $q}]

}</lang> (Tcl does not perform automatic tail-call optimization introduction because that makes any potential error traces less informative.)

Iterative binary algorithm

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

}</lang>

Notes on performance

<lang tcl>foreach proc {gcd_iter gcd gcd_bin} { 

   puts [format "%-8s - %s" $proc [time {$proc $u $v} 100000]]

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

<lang txr>@(bind g @(gcd (expt 2 123) (expt 6 49)))</lang> 

g="562949953421312"


UNIX Shell

Works with: Bourne Shell

<lang bash>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

  1. => 987</lang>

C Shell

<lang csh>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

  1. => 987</lang>

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. <lang Ursala>#import nat

gcd = ~&B?\~&Y ~&alh^?\~&arh2faltPrXPRNfabt2RCQ @a ~&ar^?\~&al ^|R/~& ^/~&r remainder</lang> test program: <lang Ursala>#cast %nWnAL

test = ^(~&,gcd)* <(25,15),(36,16),(120,45),(30,100)></lang> 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.

<lang VBA> 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 </lang>

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: <lang 8086 Assembly>.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</lang>
Retrieved from "https://rosettacode.org/wiki/Greatest_common_divisor?oldid=51638"