I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

# Greatest common divisor

Greatest common divisor
You are encouraged to solve this task according to the task description, using any language you may know.

Find the greatest common divisor   (GCD)   of two integers.

Greatest common divisor   is also known as   greatest common factor (gcf)   and   greatest common measure.

## 11l

Translation of: Python
`F gcd(=u, =v)   L v != 0      (u, v) = (v, u % v)   R abs(u) print(gcd(0, 0))print(gcd(0, 10))print(gcd(0, -10))print(gcd(9, 6))print(gcd(6, 9))print(gcd(-6, 9))print(gcd(8, 45))print(gcd(40902, 24140))`
Output:
```0
10
10
3
3
3
1
34
```

## 360 Assembly

Translation of: FORTRAN

For maximum compatibility, this program uses only the basic instruction set (S/360) with 2 ASSIST macros (XDECO,XPRNT).

`*        Greatest common divisor   04/05/2016GCD      CSECT         USING  GCD,R15            use calling register         L      R6,A               u=a         L      R7,B               v=bLOOPW    LTR    R7,R7              while v<>0          BZ     ELOOPW               leave while         LR     R8,R6                t=u         LR     R6,R7                u=v         LR     R4,R8                t         SRDA   R4,32                shift to next reg         DR     R4,R7                t/v         LR     R7,R4                v=mod(t,v)         B      LOOPW              end whileELOOPW   LPR    R9,R6              c=abs(u)         L      R1,A               a	         XDECO  R1,XDEC            edit a         MVC    PG+4(5),XDEC+7     move a to buffer         L      R1,B               b         XDECO  R1,XDEC            edit b         MVC    PG+10(5),XDEC+7    move b to buffer         XDECO  R9,XDEC            edit c         MVC    PG+17(5),XDEC+7    move c to buffer         XPRNT  PG,80              print buffer         XR     R15,R15            return code =0         BR     R14                return to callerA        DC     F'1071'            aB        DC     F'1029'            bPG       DC     CL80'gcd(00000,00000)=00000'  bufferXDEC     DS     CL12               temp for edit         YREGS         END    GCD`
Output:
```gcd( 1071, 1029)=   21
```

## 8th

`: gcd \ a b -- gcd	dup 0 n:= if drop ;; then	tuck \ b a b	n:mod \ b a-mod-b	recurse ;  : demo \ a b --	2dup "GCD of " . . " and " . . " = " . gcd . ; 100    5 demo cr  5  100 demo cr  7   23 demo cr bye `
Output:
```GCD of 5 and 100 = 5
GCD of 100 and 5 = 5
GCD of 23 and 7 = 1
```

## AArch64 Assembly

Works with: as version Raspberry Pi 3B version Buster 64 bits
` /* ARM assembly AARCH64 Raspberry PI 3B *//*  program calPgcd64.s  */ /*******************************************//* Constantes file                         *//*******************************************//* for this file see task include a file in language AArch64 assembly*/.include "../includeConstantesARM64.inc" /*********************************//* Initialized data              *//*********************************/.datasMessResult:        .asciz "Number 1 : @ number 2 : @ PGCD  : @ \n"szCarriageReturn:   .asciz "\n"szMessError:        .asciz "Error PGCD !!\n" /*********************************//* UnInitialized data            *//*********************************/.bsssZoneConv:            .skip 24/*********************************//*  code section                 *//*********************************/.text.global main main:                               // entry of program      mov x20,36    mov x21,18    mov x0,x20    mov x1,x21    bl calPGCDmod    bcs   99f                       // error ?    mov x2,x0                       // pgcd    mov x0,x20    mov x1,x21    bl displayResult    mov x20,37    mov x21,15    mov x0,x20    mov x1,x21    bl calPGCDmod    bcs   99f                       // error ?    mov x2,x0                       // pgcd    mov x0,x20    mov x1,x21    bl displayResult      b 100f99:                                 // display error    ldr x0,qAdrszMessError    bl affichageMess100:                                // standard end of the program     mov x0, #0                      // return code    mov x8, #EXIT                   // request to exit program    svc #0                          // perform the system call qAdrszCarriageReturn:     .quad szCarriageReturnqAdrszMessError:          .quad szMessError /***************************************************//*   Compute pgcd  modulo use *//***************************************************//* x0 contains first number *//* x1 contains second number *//* x0 return  PGCD            *//* if error carry set to 1    */calPGCDmod:    stp x1,lr,[sp,-16]!        // save  registres    stp x2,x3,[sp,-16]!        // save  registres    cbz x0,99f                 // if = 0 error    cbz x1,99f    cmp x0,0    bgt 1f    neg x0,x0                  // if negative inversion number 11:    cmp x1,0    bgt 2f    neg x1,x1                  // if negative inversion number 22:    cmp x0,x1                  // compare two numbers    bgt 3f    mov x2,x0                  // inversion    mov x0,x1    mov x1,x23:    udiv x2,x0,x1              // division    msub x0,x2,x1,x0           // compute remainder    cmp x0,0    bgt 2b                     // loop    mov x0,x1    cmn x0,0                   // clear carry    b 100f99:                            // error    mov x0,0    cmp x0,0                   // set carry100:    ldp x2,x3,[sp],16          // restaur des  2 registres    ldp x1,lr,[sp],16          // restaur des  2 registres    ret                        // retour adresse lr x30 /***************************************************//*   display result *//***************************************************//* x0 contains first number *//* x1 contains second number *//* x2 contains  PGCD         */displayResult:    stp x1,lr,[sp,-16]!          // save  registres    mov x3,x1                    // save x1    ldr x1,qAdrsZoneConv    bl conversion10              // décimal conversion     ldr x0,qAdrsMessResult    ldr x1,qAdrsZoneConv         // insert conversion    bl strInsertAtCharInc    mov x4,x0                    // save message address    mov x0,x3                    // conversion second number    ldr x1,qAdrsZoneConv    bl conversion10              // décimal conversion     mov x0,x4                    // move message address    ldr x1,qAdrsZoneConv         // insert conversion    bl strInsertAtCharInc    mov x4,x0                    // save message address    mov x0,x2                    // conversion pgcd    ldr x1,qAdrsZoneConv    bl conversion10              // décimal conversion     mov x0,x4                    // move message address    ldr x1,qAdrsZoneConv         // insert conversion    bl strInsertAtCharInc    bl affichageMess             // display message    ldp x1,lr,[sp],16            // restaur des  2 registres    ret                          // retour adresse lr x30qAdrsMessResult:          .quad sMessResultqAdrsZoneConv:            .quad sZoneConv/********************************************************//*        File Include fonctions                        *//********************************************************//* for this file see task include a file in language AArch64 assembly */.include "../includeARM64.inc" `

## 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 algorithmfunction 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;}`

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

## Aime

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

## ALGOL 60

`begin    comment Greatest common divisor - algol 60;     integer procedure gcd(m,n); 	value m,n;	integer m,n;    begin        integer a,b;        a:=abs(m);        b:=abs(n);        if a=0 then gcd:=b        else begin			integer c,i;		    for i:=a while b notequal 0 do begin                c:=b;                b:=a-(a div b)*b;                a:=c            end;            gcd:=a        end    end gcd;     outinteger(1,gcd(21,35))end  `
Output:
``` 7
```

## 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
```

## ALGOL W

`begin    % iterative Greatest Common Divisor routine                               %    integer procedure gcd ( integer value m, n ) ;    begin        integer a, b, newA;        a := abs( m );        b := abs( n );        if a = 0 then begin            b            end        else begin            while b not = 0 do begin                newA := b;                b    := a rem b;                a    := newA;            end;            a        end    end gcd ;     write( gcd( -21, 35 ) );end.`

## 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`

## AntLang

AntLang has a built-in gcd function.

`gcd[33; 77]`

It is not recommended, but possible to implement it on your own.

`/Unoptimized versiongcd':{a:x;b:y;last[{(0 eq a mod x) min (0 eq b mod x)} hfilter {1 + x} map range[a max b]]}`

## 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
```

## AppleScript

By recursion:

`-- gcd :: Int -> Int -> Inton gcd(a, b)    if b ≠ 0 then        gcd(b, a mod b)    else        if a < 0 then            -a        else            a        end if    end ifend gcd `

And just for the sake of it, the same thing iteratively:

`on hcf(a, b)    repeat until (b = 0)        set x to a        set a to b        set b to x mod b    end repeat     if (a < 0) then return -a    return aend hcf`

## Applesoft BASIC

`0 A = ABS(INT(A))1 B = ABS(INT(B))2 GCD = A * NOT NOT B3 FOR B = B + A * NOT B TO 0 STEP 04     A = GCD5     GCD = B6     B = A - INT (A / GCD) * GCD7 NEXT B`

## Arendelle

```< a , b >

( r , @a )

[ @r != 0 ,

( r , @a % @b )

{ @r != 0 ,

( a , @b )
( b , @r )

}
]

( return , @b )```

## Arturo

`print [gcd #(10 15)]`
Output:
`5`

## AutoHotkey

Contributed by Laszlo on the ahk forum

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

Significantly faster than recursion:

`GCD(a, b) {    while b        b := Mod(a | 0x0, a := b)    return a}`

## AutoIt

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

## AWK

The following scriptlet defines the gcd() function, then reads pairs of numbers from stdin, and reports their gcd on stdout.

`\$ awk 'function gcd(p,q){return(q?gcd(q,(p%q)):p)}{print gcd(\$1,\$2)}'12 16422 331145 671`

## Axe

`Lbl GCDr₁→Ar₂→B!If B A ReturnEndGCD(B,A^B)`

## 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 = 1END 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`

### IS-BASIC

`100 DEF GCD(A,B)110   DO WHILE B>0120     LET T=B130     LET B=MOD(A,B)140     LET A=T150   LOOP 160   LET GCD=A170 END DEF 180 PRINT GCD(12,16)`

### Sinclair ZX81 BASIC

` 10 LET M=119 20 LET N=544 30 LET R=M-N*INT (M/N) 40 IF R=0 THEN GOTO 80 50 LET M=N 60 LET N=R 70 GOTO 30 80 PRINT N`
Output:
`17`

## Batch File

Recursive method

`:: gcd.cmd@echo off:gcdif "%2" equ "" goto :instructionsif "%1" equ "" goto :instructions if %2 equ 0 (	set final=%1	goto :done)set /a res = %1 %% %2call :gcd %2 %res%goto :eof :doneecho gcd=%final%goto :eof :instructionsecho Syntax:echo 	GCD {a} {b}echo.`

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

### Iterative Euclid algorithm

`intgcd_iter(int u, int v) {  if (u < 0) u = -u;  if (v < 0) v = -v;  if (v) while ((u %= v) && (v %= u));  return (u + v);}`

### Recursive Euclid algorithm

`int gcd(int u, int v) {return (v != 0)?gcd(v, u%v):u;}`

### Iterative binary algorithm

`intgcd_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#

### Iterative

` static void Main(){	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();} /// <summary>/// Greatest Common Denominator using Euclidian Algorithm/// </summary>static int gcd(int a, int b){    while (b != 0) b = a % (a = b);    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
```

### Recursive

` 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();} // Greatest Common Denominator using Euclidian Algorithm// Gist: https://gist.github.com/SecretDeveloper/6c426f8993873f1a05f7static int gcd(int a, int b){		return b==0 ? a : gcd(b, a % b);} `

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

## C++

`#include <iostream>#include <numeric> int main() {    std::cout << "The greatest common divisor of 12 and 18 is " << std::gcd(12, 18) << " !\n";}`
Library: Boost
`#include <boost/math/common_factor.hpp>#include <iostream> int main() {   std::cout << "The greatest common divisor of 12 and 18 is " << boost::math::gcd(12, 18) << "!\n";}`
Output:
`The greatest common divisor of 12 and 18 is 6!`

## Clojure

### Euclid's Algorithm

`(defn gcd   "(gcd a b) computes the greatest common divisor of a and b."  [a b]  (if (zero? b)    a    (recur b (mod a b))))`

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

This can be easily extended to work with variadic arguments:

`(defn gcd*  "greatest common divisor of a list of numbers"  [& lst]  (reduce gcd          lst))`

### Stein's Algorithm (Binary GCD)

`(defn stein-gcd [a b]  (cond    (zero? a) b    (zero? b) a    (and (even? a) (even? b)) (* 2 (stein-gcd (unsigned-bit-shift-right a 1) (unsigned-bit-shift-right b 1)))    (and (even? a) (odd? b)) (recur (unsigned-bit-shift-right a 1) b)    (and (odd? a) (even? b)) (recur a (unsigned-bit-shift-right b 1))    (and (odd? a) (odd? b)) (recur (unsigned-bit-shift-right (Math/abs (- a b)) 1) (min a b))))`

## 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) ->  if y == 0 then x else gcd y, x % y `

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

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

## 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 `gcd*` so as not to conflict with `common-lisp:gcd`.

`(defun gcd* (a b)  (do () ((zerop b) (abs a))    (shiftf a b (mod a b))))`

Here is a tail-recursive implementation.

`(defun gcd* (a b)  (if (zerop b)       a       (gcd2 b (mod a b))))`

The last implementation is based on the loop macro.

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

## Component Pascal

BlackBox Component Builder

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

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

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

## D

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

## 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`

## Dyalect

Translation of: Go
`func gcd(a, b) {    func bgcd(a, b, res) {        if a == b {            return res * a        } else if a % 2 == 0 && b % 2 == 0 {            return bgcd(a/2, b/2, 2*res)        } else if a % 2 == 0 {            return bgcd(a/2, b, res)        } else if b % 2 == 0 {            return bgcd(a, b/2, res)        } else if a > b {            return bgcd(a-b, b, res)        } else {            return bgcd(a, b-a, res)        }    }    return bgcd(a, b, 1)} var testdata = [    (a = 33, b = 77),    (a = 49865, b = 69811)] for v in testdata {    print("gcd(\(v:a), \(v:b)) = \(gcd(v:a, v:b))")}`
Output:
```gcd(33, 77) = 11
gcd(49865, 69811) = 9973```

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

## EasyLang

`func gcd a b . res .  while b <> 0    h = b    b = a mod b    a = h  .  res = a.call gcd 120 35 rprint r`

## EDSAC order code

The EDSAC had no division instruction, so the GCD routine below has to include its own code for division.

`  [Greatest common divisor for Rosetta Code.  Program for EDSAC, Initial Orders 2.]  [Library subroutine R2. Reads positive integers during input of orders,    and is then overwritten (so doesn't take up any memory).  Negative numbers can be input by adding 2^35.  Each integer is followed by 'F', except the last is followed by '#TZ'.]            T   45 K [store address in location 45                    values are then accessed by code letter H]            P  220 F [<------ address here]  [email protected]@[email protected]@E13Z            T     #H  [Tell R2 the storage location defined above]  [Integers to be read by R2. First item is count, then pairs for GCD algo.]  4F 1066F 2019F 1815F 1914F 103785682F 167928761F 109876463F 177777648#TZ  [----------------------------------------------------------------------  Library subroutine P7.  Prints long strictly positive integer at 0D.  10 characters, right justified, padded left with spaces.  Closed, even; 35 storage locations; working position 4D.]            T   56 K  [email protected]#@[email protected]@[email protected]@SFLDUFOFFFSFL4F  [email protected]@XFT28#[email protected][email protected]@  [---------------------------------------------------------------  Subroutine to return GCD of two non-negative 35-bit integers.  Input:  Integers at 4D, 6D.  Output: GCD at 4D; changes 6D.  41 locations; working location 0D.]            T  100 K            G      K            A    3 F  [plant link]            T   39 @            S    4 D  [test for 4D = 0]            E   37 @  [if so, quick exit, GCD = 6D]            T   40 @  [clear acc]      [5]   A    4 D  [load divisor]      [6]   T      D  [initialize shifted divisor]            A    6 D  [load dividend]            R      D  [shift 1 right]            S      D  [shifted divisor > dividend/2 yet?]            G   15 @  [yes, start subtraction]            T   40 @  [no, clear acc]            A      D  [shift divisor 1 more]            L      D            E    6 @  [loop back (always, since acc = 0)]     [15]   T   40 @  [clear acc]     [16]   A    6 D  [load remainder (initially = dividend)]            S      D  [trial subtraction]            G   20 @  [skip if can't subtract]            T    6 D  [update remainder]     [20]   T   40 @  [clear acc]            A    4 D  [load original divisor]            S      D  [is shifted divisor back to original?]            E   29 @  [yes, jump out with acc = 0]            T   40 @  [no, clear acc]            A      D  [shift divisor 1 right]            R      D            T      D            E   16 @  [loop back (always, since acc = 0)]         [Here when finished dividing 6D by 4D.          Remainder is at 6D; acc = 0.]     [29]   S    6 D  [test for 6D = 0]            E   39 @  [if so, exit with GCD in 4D]            T      D  [else swap 4D and 6D]            A    4 D            T    6 D            S      D            T    4 D            E    5 @  [loop back]     [37]   A    6 D  [here if 4D = 0 at start; GCD is 6D]            T    4 D  [return in 4D as GCD]     [39]   E      F     [40]   P      F  [junk word, to clear accumulator]  [----------------------------------------------------------------------  Main routine]            T  150 K            G      K  [Variable]      [0]   P      F  [Constants]      [1]   P      D [single-word 1]      [2]   A    2#H [order to load first number of first pair]      [3]   P    2 F [to inc addresses by 2]      [4]   #      F [figure shift]      [5]   K 2048 F [letter shift]      [6]   G      F [letters to print 'GCD']      [7]   C      F      [8]   D      F      [9]   V      F [equals sign (in figures mode)]     [10]   !      F [space]     [11]   @      F [carriage return]     [12]   &      F [line feed]     [13]   K 4096 F [null char]         [Enter here with acc = 0]     [14]   O    4 @ [set teleprinter to figures]            S      H [negative of number of pairs]            T      @ [initialize counter]            A    2 @ [initial load order]     [18]   U   23 @ [plant order to load 1st integer]            U   32 @            A    3 @ [inc address by 2]            U   28 @ [plant order to load 2nd integer]            T   34 @     [23]   A     #H [load 1st integer (order set up at runtime)]            T      D [to 0D for printing]            A   25 @ [for return from print subroutine]            G   56 F [print 1st number]            O   10 @ [followed by space]     [28]   A     #H [load 2nd integer (order set up at runtime)]            T      D [to 0D for printing]            A   30 @ [for return from print subroutine]            G   56 F [print 2nd number]     [32]   A     #H [load 1st integer (order set up at runtime)]            T    4 D [to 4D for GCD subroutine]     [34]   A     #H [load 2nd integer (order set up at runtime)]            T    6 D [to 6D for GCD subroutine]     [36]   A   36 @ [for return from subroutine]            G  100 F [call subroutine for GCD]         [Cosmetic printing, add '  GCD = ']            O   10 @            O   10 @            O    5 @            O    6 @            O    7 @            O    8 @            O    4 @            O   10 @            O    9 @            O   10 @            A    4 D [load GCD]            T      D [to 0D for printing]            A   50 @ [for return from print subroutine]            G   56 F [print GCD]            O   11 @ [followed by new line]            O   12 @          [On to next pair]            A      @ [load negative count of c.f.s]            A    1 @ [add 1]            E   62 @ [exit if count = 0]            T      @ [store back]            A   23 @ [order to load first of pair]            A    3 @ [inc address by 4 for next c.f.]            A    3 @            G   18 @ [loop back (always, since 'A' < 0)]     [62]   O   13 @  [null char to flush teleprinter buffer]            Z      F  [stop]            E   14 Z  [define entry point]            P      F  [acc = 0 on entry] `
Output:
```      1066       2019  GCD =          1
1815       1914  GCD =         33
103785682  167928761  GCD =       1001
109876463  177777648  GCD =    1234567
```

## Eiffel

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

## Elena

Translation of: C#

ELENA 4.x :

`import system'math;import extensions; gcd(a,b){    var i := a;    var j := b;    while(j != 0)    {        var tmp := i;        i := j;        j := tmp.mod(j)    };     ^ i} printGCD(a,b){    console.printLineFormatted("GCD of {0} and {1} is {2}", a, b, gcd(a,b))} public program(){    printGCD(1,1);    printGCD(1,10);    printGCD(10,100);    printGCD(5,50);    printGCD(8,24);    printGCD(36,17);    printGCD(36,18);    printGCD(36,19);    printGCD(36,33);}`
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 17 is 1
GCD of 36 and 18 is 18
GCD of 36 and 19 is 1
GCD of 36 and 33 is 3
```

## Elixir

`defmodule RC do  def gcd(a,0), do: abs(a)  def gcd(a,b), do: gcd(b, rem(a,b))end IO.puts RC.gcd(1071, 1029)IO.puts RC.gcd(3528, 3780)`
Output:
```21
252
```

## Emacs Lisp

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

## Erlang

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

## ERRE

This is a iterative version.

` PROGRAM EUCLIDE! calculate G.C.D. between two integer numbers! using Euclidean algorithm !VAR J%,K%,MCD%,A%,B% BEGIN  PRINT(CHR\$(12);"Input two numbers : ";)  !CHR\$(147) in C-64 version  INPUT(J%,K%)  A%=J% B%=K%  WHILE A%<>B% DO    IF A%>B%       THEN         A%=A%-B%       ELSE         B%=B%-A%    END IF  END WHILE  MCD%=A%  PRINT("G.C.D. between";J%;"and";K%;"is";MCD%)END PROGRAM `
Output:
```Input two numbers : ? 112,44
G.C.D. between 112 and 44 is 4
```

## Euler Math Toolbox

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

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

## 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 ifend 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 ifend 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 * kend function`

## Excel

Excel's GCD can handle multiple values. Type in a cell:

`=GCD(A1:E1)`
Sample Output:

This will get the GCD of the first 5 cells of the first row.

```30	10	500	25	1000
5				```

## Ezhil

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

## F#

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

## Factor

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

## FALSE

`10 15\$ [0=~][[email protected][email protected][email protected]\/*-\$]#%. { 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 ifend 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 * kend 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

## FreeBASIC

### Iterative solution

`' version 17-06-2015' compile with: fbc -s console Function gcd(x As ULongInt, y As ULongInt) As ULongInt     Dim As ULongInt t     While y        t = y        y = x Mod y        x = t    Wend     Return x End Function ' ------=< MAIN >=------ Dim As ULongInt a = 111111111111111Dim As ULongInt b = 11111 Print : Print "GCD(";a;", ";b;") = "; gcd(a, b)Print : Print "GCD(";a;", 111) = "; gcd(a, 111) ' empty keyboard bufferWhile InKey <> "" : WendPrint : Print : Print "hit any key to end program"SleepEnd`
Output:
```GCD(111111111111111, 11111) = 11111
GCD(111111111111111, 111) = 111```

### Recursive solution

`function gcdp( a as uinteger, b as uinteger ) as uinteger    if b = 0 then return a    return gcdp( b, a mod b )end function function gcd(a as integer, b as integer) as uinteger    return gcdp( abs(a), abs(b) )end function`

## Frege

`module gcd.GCD where pure native parseInt java.lang.Integer.parseInt :: String -> Int gcd' a 0 = agcd' a b = gcd' b (a `mod` b) main args = do    (a:b:_) = args    println \$ gcd' (parseInt a) (parseInt b) `

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

## FunL

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

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

## FutureBasic

` local fn gcd( a as long, b as long )dim as long result if ( b != 0 )   result = fn gcd( b, a mod b)else   result = abs(a)end ifend fn = result `

## GAP

`# Built-inGcdInt(35, 42);# 7 # Euclidean algorithmGcdInteger := 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`

## GFA Basic

` '' Greatest Common Divisor'a%=24b%=112PRINT "GCD of ";a%;" and ";b%;" is ";@gcd(a%,b%)'' Function computes gcd'FUNCTION gcd(a%,b%)  LOCAL t%  '  WHILE b%<>0    t%=a%    a%=b%    b%=t% MOD b%  WEND  '  RETURN ABS(a%)ENDFUNC `

## GML

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

## gnuplot

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

Example:

`print gcd (111111, 1111)`

Output:

`11`

## Go

### Binary Euclidian

`package main import "fmt" func gcd(a, b int) int {    var bgcd func(a, b, res int) int     bgcd = func(a, b, res int) int {	switch {	case a == b:	    return res * a	case a % 2 == 0 && b % 2 == 0:	    return bgcd(a/2, b/2, 2*res)	case a % 2 == 0:	    return bgcd(a/2, b, res)	case b % 2 == 0:	    return bgcd(a, b/2, res)	case a > b:	    return bgcd(a-b, b, res)	default:	    return bgcd(a, b-a, res)	}    }     return bgcd(a, b, 1)} func main() {    type pair struct {	a int	b int    }     var testdata []pair = []pair{	pair{33, 77},	pair{49865, 69811},    }     for _, v := range testdata {	fmt.Printf("gcd(%d, %d) = %d\n", v.a, v.b, gcd(v.a, v.b))    }} `
Output for Binary Euclidian algorithm:
```gcd(33, 77) = 11
gcd(49865, 69811) = 9973
```

### 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 gcdRgcdR = { 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```

That is already available as the function gcd in the Prelude. Here's the implementation, with one name adjusted to avoid a Wiki formatting glitch:

`gcd :: (Integral a) => a -> a -> agcd 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 Libraryprocedure main(args)    write(gcd(arg[1], arg[2])) | "Usage: gcd n m")end`
numbers implements this as:
`procedure gcd(i,j)		#: greatest common divisor   local r    if (i | j) < 1 then runerr(501)    repeat {      r := i % j      if r = 0 then return j      i := j      j := r      }end`

## J

`x+.y`

For example:

`   12 +. 306`

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) - more than that, though, GCD corresponds to George Boole's original "Boolean Algebra" (as it was later called). The redefinition of "Boolean algebra" to include logical negation came much later, in the 20th century).

gcd could also be defined recursively, if you do not mind a little inefficiency:

`gcd=: (| gcd [)^:(0<[)&|`

## Java

### Iterative

`public static long gcd(long a, long b){   long factor= Math.min(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;} `

### Optimized Iterative

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

### 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 implementation

`function gcd(a,b) {  a = Math.abs(a);  b = Math.abs(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) {  return b ? gcd_rec(b, a % b) : Math.abs(a);}`

Implementation that works on an array of integers.

`function GCD(arr) {  var i, y,      n = arr.length,      x = Math.abs(arr[0]);   for (i = 1; i < n; i++) {    y = Math.abs(arr[i]);     while (x && y) {      (x > y) ? x %= y : y %= x;    }    x += y;  }  return x;} //For example:GCD([57,0,-45,-18,90,447]); //=> 3 `

## Joy

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

## jq

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

## Julia

Julia includes a built-in `gcd` function:

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

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

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

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

## K

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

## Klong

`gcd::{:[~x;y:|~y;x:|x>y;.f(y;x!y);.f(x;y!x)]}`

## Kotlin

Recursive one line solution:

`fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)`

## LabVIEW

Translation of: AutoHotkey

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.

## Lambdatalk

`  {def gcd {lambda {:a :b}  {if {= :b 0}   then :a   else {gcd :b {% :a :b}}}}}-> gcd {gcd 12 3}-> 3 {gcd 123 122}-> 1 {S.map {gcd 123} {S.serie 1 30}}-> 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 A simpler one if a and b are greater than zero {def GCD {lambda {:a :b}  {if {= :a :b}    then :a   else {if {> :a :b}   then {GCD {- :a :b} :b}   else {GCD :a {- :b :a}}}}}}-> GCD {S.map {GCD 123} {S.serie 1 30}}-> 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 `

## LFE

Translation of: Clojure
` > (defun gcd  "Get the greatest common divisor."  ((a 0) a)  ((a b) (gcd b (rem a b)))) `

Usage:

```> (gcd 12 8)
4
> (gcd 12 -8)
4
> (gcd 96 27)
3
> (gcd 51 34)
17
```

## Liberty BASIC

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

## Limbo

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

## LiveCode

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

## Logo

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

## Lua

Translation of: C
`function gcd(a,b)	if b ~= 0 then		return gcd(b, a % b)	else		return math.abs(a)	endend 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
```

Faster iterative solution of Euclid:

`function gcd(a,b)    while b~=0 do         a,b=b,a%b    end    return math.abs(a)end `

## 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`

## Luck

`function gcd(a: int, b: int): int = (   if a==0 then b   else if b==0 then a   else if a>b then gcd(b, a % b)   else gcd(a, b % a))`

## M2000 Interpreter

` gcd=lambda (u as long, v as long) -> {           =if(v=0&->abs(u), lambda(v, u mod v))}gcd_Iterative= lambda (m as long, n as long) -> {   while m  {       let old_m = m       m = n mod m       n = old_m   }   =abs(n)}Module CheckGCD (f){      Print f(49865, 69811)=9973      Def ExpType\$(x)=Type\$(x)      Print ExpType\$(f(49865, 69811))="Long"}CheckGCD gcdCheckGCD gcd_Iterative `

## Maple

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

`igcd( a, b )`

For example,

` > igcd( 24, 15 );                3 `

## Mathematica / Wolfram Language

`GCD[a, b]`

## MATLAB

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

## 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;`

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

## Mercury

### Recursive Euclid algorithm

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

An example console program to demonstrate the gcd module:

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

Example output:

`gcd(70000000000000000000000, 60000000000000000000000000) = 10000000000000000000000`

## MINIL

`// Greatest common divisor00 0E  GCD:   ENT  R001 1E         ENT  R102 21  Again: R2 = R103 10  Loop:  R1 = R004 02         R0 = R205 2D  Minus: DEC  R206 8A         JZ   Stop07 1D         DEC  R108 C5         JNZ  Minus09 83         JZ   Loop0A 1D  Stop:  DEC  R10B C2         JNZ  Again0C 80         JZ   GCD   // Display GCD in R0`

## MIPS Assembly

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

## МК-61/52

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

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

## ML

### mLite

`fun gcd (a, 0) = a      | (0, b) = b      | (a, b) where (a < b)               = gcd (a, b rem a)      | (a, b) = gcd (b, a rem b)  `

### Standard ML

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

## 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);              WriteLnEND ggTkgV.`

Producing the output

`[email protected]:~/modula/Wirth/PIM\$ ggtkgvx = 12y = 20ggT =     4kgV =    60u =    44v =    76[email protected]:~/modula/Wirth/PIM\$ ggtkgvx = 123y = 255ggT =     3kgV = 10455u = 13773v =  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
```

## MySQL

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

## Nanoquery

Translation of: Java

### Iterative

`def gcd(a, b)	factor = a.min(b) 	for loop in range(factor, 2)		if (a % loop = 0) and (b % loop = 0)			return loop		end	end 	return 1end`

### Iterative Euclid's Method

`def gcd_euclid(a, b)	while b > 0		c = a % b		a = b		b = c	end	return aend`

## NetRexx

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

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

Success: Results of iterative and recursive methods match
```

## 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 conditionred 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`

## Nim

Ported from Pascal example

### Recursive Euclid algorithm

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

### Iterative Euclid algorithm

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

### Iterative binary algorithm

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

## Oberon-2

Works with oo2c version 2

` MODULE GCD;(* Greatest Common Divisor *)IMPORT   Out;   PROCEDURE Gcd(a,b: LONGINT):LONGINT;  VAR    r: LONGINT;  BEGIN    LOOP      r := a MOD b;      IF r = 0 THEN RETURN b END;      a := b;b := r    END  END Gcd;BEGIN  Out.String("GCD of    12 and     8 : ");Out.LongInt(Gcd(12,8),4);Out.Ln;  Out.String("GCD of   100 and     5 : ");Out.LongInt(Gcd(100,5),4);Out.Ln;  Out.String("GCD of     7 and    23 : ");Out.LongInt(Gcd(7,23),4);Out.Ln;  Out.String("GCD of    24 and  -112 : ");Out.LongInt(Gcd(12,8),4);Out.Ln;  Out.String("GCD of 40902 and 24140 : ");Out.LongInt(Gcd(40902,24140),4);Out.LnEND GCD. `

Output:

```GCD of    12 and     8 :    4
GCD of   100 and     5 :    5
GCD of     7 and    23 :    1
GCD of    24 and  -112 :    4
GCD of 40902 and 24140 :   34
```

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

A little more idiomatic version:

`let rec gcd1 a b =  match (a mod b) with    0 -> b  | r -> gcd1 b r`

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

## Oforth

gcd is already defined into Integer class :

`128 96 gcd`

Source of this method is (see Integer.of file) :

`Integer method: gcd  self while ( dup ) [ tuck mod ] drop ;`

## Ol

` (print (gcd 1071 1029)); ==> 21 `

## Order

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

## 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  endin  {Show {GCD 456 ~632}}`

## PARI/GP

`gcd(a,b)`

PASCAL program GCF (INPUT, OUTPUT);

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

By: NG

## Pascal / Delphi / Free 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;}`

### Modules

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

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

### Notes on performance

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

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

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

## Phix

result is always positive, except for gcd(0,0) which is 0
atom parameters allow greater precision, but any fractional parts are immediately and deliberately discarded.
Actually, it is an autoinclude, reproduced below. The first parameter can be a sequence, in which case the second parameter (if provided) is ignored.

`function gcd(object u, atom v=0)atom t    if sequence(u) then        v = u[1]                        -- (for the typecheck)        t = floor(abs(v))        for i=2 to length(u) do            v = u[i]                    -- (for the typecheck)            t = gcd(t,v)        end for        return t    end if    u = floor(abs(u))    v = floor(abs(v))    while v do        t = u        u = v        v = remainder(t, v)    end while    return uend function`

Sample results

```gcd(0,0)            -- 0
gcd(24,-112)        -- 8
gcd(0, 10)          -- 10
gcd(10, 0)          -- 10
gcd(-10, 0)         -- 10
gcd(0, -10)         -- 10
gcd(9, 6)           -- 3
gcd(6, 9)           -- 3
gcd(-6, 9)          -- 3
gcd(9, -6)          -- 3
gcd(6, -9)          -- 3
gcd(-9, 6)          -- 3
gcd(40902, 24140)   -- 34
gcd(70000000000000000000,
60000000000000000000000)
-- 10000000000000000000
gcd({57,0,-45,-18,90,447}) -- 3
```

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

## PicoLisp

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

## 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}. `

With no external lib, recursive

` /gcd {   dup 0 ne {      dup 3 1 roll mod gcd   } { pop } ifelse} def `

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

or shorter (taken from Python implementation)

`function Get-GCD (\$x, \$y) {  if (\$y -eq 0) { \$x } else { Get-GCD \$y (\$x%\$y) }}`

### Iterative Euclid Algorithm

based on Python implementation

` Function Get-GCD( \$x, \$y ) {    while (\$y -ne 0) {        \$x, \$y = \$y, (\$x % \$y)    }    [Math]::abs(\$x)} `

## 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 yEndProcedure`

Recursive

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

## Purity

` data Iterate = f => FoldNat <const id, g => \$g . \$f> data Sub = Iterate Preddata 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`
Works with: Python version 3.7

(Note that fractions.gcd is now deprecated in Python 3)

`from math 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

Recursive:

`"%gcd%" <- function(u, v) {  ifelse(u %% v != 0, v %gcd% (u%%v), v)}`

Iterative:

`"%gcd%" <- function(v, t) {  while ( (c <- v%%t) != 0 ) {    v <- t    t <- c  }  t}`
Output:

Same either way.

```> print(50 %gcd% 75)
[1] 25
```

## Racket

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

`#lang racket (gcd 14 63)`

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

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

## Raku

(formerly 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 = { (\$^a.abs, \$^b.abs, * % * ... 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`

## 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 `

## Raven

### Recursive Euclidean algorithm

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

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

### version 1

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

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

output

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

### version 2

Recursive function (as in PL/I):

` /* REXX **************************************************************** using PL/I code extended to many arguments* 17.08.2012 Walter Pachl* 18.08.2012 gcd(0,0)=0**********************************************************************/numeric digits 300                  /*handle up to 300 digit numbers.*/Call test  7,21     ,'7 'Call test  4,7      ,'1 'Call test 24,-8     ,'8'Call test 55,0      ,'55'Call test 99,15     ,'3 'Call test 15,10,20,30,55,'5'Call test 496,8128  ,'16'Call test 496,8128  ,'8'            /* test wrong expectation        */Call test 0,0       ,'0'            /* by definition                 */Exit test:/*********************************************************************** Test the gcd function**********************************************************************/n=arg()                             /* Number of arguments           */gcde=arg(n)                         /* Expected result               */gcdx=gcd(arg(1),arg(2))             /* gcd of the first 2 numbers    */Do i=2 To n-2                       /* proceed with all the others   */  If arg(i+1)<>0 Then       gcdx=gcd(gcdx,arg(i+1))  EndIf gcdx=arg(arg()) Then             /* result is as expected         */  tag='as expected'Else                                /* result is not correct         */  Tag='*** wrong. expected:' gcdenumbers=arg(1)                      /* build string to show the input*/Do i=2 To n-1  numbers=numbers 'and' arg(i)  Endsay left('the GCD of' numbers 'is',45) right(gcdx,3) tagReturn GCD: procedure/*********************************************************************** Recursive procedure as shown in PL/I**********************************************************************/Parse Arg a,bif b = 0 then return abs(a)return GCD(b,a//b)`

Output:

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

### version 3

Translation of: REXX
using different argument handling-

Use as gcd(a,b,c,---) Considerably faster than version 1 (and version 2)
See http://rosettacode.org/wiki/Least_common_multiple#REXX for reasoning.

`gcd: procedurex=abs(arg(1))do j=2 to arg()  y=abs(arg(j))  If y<>0 Then Do    do until z==0      z=x//y      x=y      y=z      end    end  endreturn x`

## Ring

` see gcd (24, 32)func gcd gcd, b     while b           c   = gcd           gcd = b           b   = c % b     end     return gcd `

## Ruby

That is already available as the gcd method of integers:

` 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  uend`

## Run BASIC

`print abs(gcd(-220,160))function gcd(gcd,b)    while b        c   = gcd        gcd = b        b   = c mod b    wendend function `

## Rust

### num crate

`extern crate num;use num::integer::gcd;`

### Iterative Euclid algorithm

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

### Recursive Euclid algorithm

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

### Stein's Algorithm

Stein's algorithm is very much like Euclid's except that it uses bitwise operators (and consequently slightly more performant) and the integers must be unsigned. The following is a recursive implementation that leverages Rust's pattern matching.

`use std::cmp::{min, max};fn gcd(a: usize, b: usize) -> usize {    match ((a, b), (a & 1, b & 1)) {        ((x, y), _) if x == y               => y,        ((0, x), _) | ((x, 0), _)           => x,        ((x, y), (0, 1)) | ((y, x), (1, 0)) => gcd(x >> 1, y),        ((x, y), (0, 0))                    => gcd(x >> 1, y >> 1) << 1,        ((x, y), (1, 1))                    => { let (x, y) = (min(x, y), max(x, y));                                                  gcd((y - x) >> 1, x)                                                }        _                                   => unreachable!(),    }}`

### Tests

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

## Sass/SCSS

Iterative Euclid's Algorithm

` @function gcd(\$a,\$b) {	@while \$b > 0 {		\$c: \$a % \$b;		\$a: \$b;		\$b: \$c;	}	@return \$a;} `

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

Using pattern matching

`@tailrecdef gcd(a: Int, b: Int): Int = {  b match {    case 0 => a    case _ => 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 <[email protected]># dc.sed  Copyright (c) 1995 - 1997 by Greg Ubben <[email protected]> # usage:##     echo N M | ./gcd.sed## Computes the greatest common divisor of N and M integers using euclidean# algorithm. s/^/|P|K0|I10|O10|?~/ s/\$/ [lalb%sclbsalcsblb0<F]sF sasblFxlap/ :nexts/|?./|?/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 quith/|?[XZz]/b count/|?v/b sqrts/.*|?\([^Y]\).*/\1 is unimplemented/s/\n/\\n/glgb 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/hs/~.*///./{ 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 :pops/[^~]*~//b next :loads/\(.*|?.\)\(.\)/\20~\1/s/^\(.\)0\(.*|r\1\([^~|]*\)~\)/\1\3\2/s/.//b next :Loads/\(.*|?.\)\(.\)/\2\1/s/^\(.\)\(.*|r\1\)\([^~|]*~\)/|\3\2//^|/!i\register emptys/.//b next :saves/\(.*|?.\)\(.\)/\2\1//^\(.\).*|r\1/ !s/\(.\).*|/&r\1|//|?S/ s/\(.\).*|r\1/&~/s/\(.\)\([^~]*~\)\(.*|r\1\)[^~|]*~\{0,1\}/\3\2/b next :quitt quits/|?[^~]*~[^~]*~/|?q/t next#  Really should be using the -n option to avoid printing a final newline.s/.*|P\([^|]*\).*/\1/q :breaks/[0-9]*/&;987654321009;/:break1s/^\([^;]*\)\([1-9]\)\(0*\)\([^1]*\2\(.\)[^;]*\3\(9*\).*|?.\)[^~]*~/\1\5\6\4/t break1b pop :inputNs/|??\(.*\)\(\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 count1G/|?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 trunc1s/[^:]*:\([^,]*\)[^~]*/\1/b normal :numbers/\(.*|?\)\(_\{0,1\}[0-9A-F]*\.\{0,1\}[0-9A-F]*\)/\2~\1~/s/^_/-//^[^A-F~]*~.*|I10|/b normal/^[-0.]*~/b normals:\([^.~]*\)\.*\([^~]*\):[Ilb^lbk/,\1\2~0A1B2C3D4E5F1=11223344556677889900;.\2::digit    s/^\([^,]*\),\(-*\)\([0-F]\)\([^;]*\(.\)\3[^1;]*\(1*\)\)/I*+\1\2\6\5~,\2\4/t digits:...\([^/]*.\)\([^,]*\)[^.]*\(.*|?.\):\2\3KSb[99]k\1]SaSaXSbLalb0<aLakLbktLbk:b next :string/|?[^]]*\$/Ns/\(|?[^]]*\)\[\([^]]*\)]/\1|{\2|}//|?\[/b strings/\(.*|?\)|{\(.*\)|}/\2~\1[/s/|{/[/gs/|}/]/gb 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 right1s/.\([^,]*\),~\(.*\);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 :endbins/.\([^,]*\),\([0-9.]*\).*/\1\2/Gs/\n[^~]*~[^~]*// :normals/^\(-*\)0*\([0-9.]*[0-9]\)[^~]*/\1\2/s/^[^1-9~]*~/0~/b next :muls/\(-*\)\([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 mul2b endbin :div#  CDDET/^[-.0]*[1-9]/ !i\divide by 0//!b pops/\(-*\)\([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 div1s/~\(-*\)\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 :rems,|?%,&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 ignoreds,[^-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 exp1Gs,-*.\{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 nexts/~.*///^\./ s/0\([0-9]\)/\1/g/^\./ !s/[0-9][0-9]/7/gGs/\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: gcd is 0;  local    var integer: help is 0;  begin    while a <> 0 do      help := b rem a;      b := a;      a := help;    end while;    gcd := b;  end func;`

Original source: [1]

## SequenceL

Tail Recursive Greatest Common Denominator using Euclidian Algorithm

`gcd(a, b) :=		a when b = 0	else		gcd(b, a mod b);`

## 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  11the gcd of 49865  and  69811  is  9973`

## Sidef

### Built-in

`var arr = [100, 1_000, 10_000, 20];say Math.gcd(arr...);`

### Recursive Euclid algorithm

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

## Simula

For a recursive variant, see Sum multiples of 3 and 5.

`BEGIN    INTEGER PROCEDURE GCD(a, b); INTEGER a, b;    BEGIN        IF a = 0 THEN a := b        ELSE            WHILE 0 < b DO BEGIN INTEGER i;                i := MOD(a, b); a := b; b := i;            END;        GCD := a    END;     INTEGER a, b;    !outint(SYSOUT.IMAGE.MAIN.LENGTH, 0);!OUTIMAGE;!OUTIMAGE;    !SYSOUT.IMAGE :- BLANKS(132);  ! this may or may not work;    FOR b := 1 STEP 5 UNTIL 37 DO BEGIN        FOR a := 0 STEP 2 UNTIL 21 DO BEGIN            OUTTEXT("  ("); OUTINT(a, 0);            OUTCHAR(','); OUTINT(b, 2);            OUTCHAR(')'); OUTINT(GCD(a, b), 3);        END;        OUTIMAGE    ENDEND`
Output:
```(0, 1)  1  (2, 1)  1  (4, 1)  1  (6, 1)  1  (8, 1)  1  (10, 1)  1  (12, 1)  1  (14, 1)  1  (16, 1)  1  (18, 1)  1  (20, 1)  1
(0, 6)  6  (2, 6)  2  (4, 6)  2  (6, 6)  6  (8, 6)  2  (10, 6)  2  (12, 6)  6  (14, 6)  2  (16, 6)  2  (18, 6)  6  (20, 6)  2
(0,11) 11  (2,11)  1  (4,11)  1  (6,11)  1  (8,11)  1  (10,11)  1  (12,11)  1  (14,11)  1  (16,11)  1  (18,11)  1  (20,11)  1
(0,16) 16  (2,16)  2  (4,16)  4  (6,16)  2  (8,16)  8  (10,16)  2  (12,16)  4  (14,16)  2  (16,16) 16  (18,16)  2  (20,16)  4
(0,21) 21  (2,21)  1  (4,21)  1  (6,21)  3  (8,21)  1  (10,21)  1  (12,21)  3  (14,21)  7  (16,21)  1  (18,21)  3  (20,21)  1
(0,26) 26  (2,26)  2  (4,26)  2  (6,26)  2  (8,26)  2  (10,26)  2  (12,26)  2  (14,26)  2  (16,26)  2  (18,26)  2  (20,26)  2
(0,31) 31  (2,31)  1  (4,31)  1  (6,31)  1  (8,31)  1  (10,31)  1  (12,31)  1  (14,31)  1  (16,31)  1  (18,31)  1  (20,31)  1
(0,36) 36  (2,36)  2  (4,36)  4  (6,36)  6  (8,36)  4  (10,36)  2  (12,36) 12  (14,36)  2  (16,36)  4  (18,36) 18  (20,36)  4
```

## Slate

Slate's Integer type has gcd defined:

`40902 gcd: 24140`

### Iterative Euclid algorithm

`[email protected](Integer traits) gcd: [email protected](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

`[email protected](Integer traits) gcd: [email protected](Integer traits)[  y isZero    ifTrue: [x]    ifFalse: [y gcd: x \\ y]].`

## Smalltalk

The Integer class has its gcd method.

`(40902 gcd: 24140) displayNl`

An reimplementation of the Iterative Euclid's algorithm would be:

`|gcd_iter| gcd_iter := [ :a :b |   |u v|    u := a. v := b.   [ v > 0 ]     whileTrue: [ |t|        t := u.        u := v.        v := t rem: v     ].   u abs]. (gcd_iter value: 40902 value: 24140) printNl.`

## 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`

## Sparkling

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

## SQL

Demonstration of Oracle 12c WITH Clause Enhancements

`DROP TABLE tbl;CREATE TABLE tbl(        u       NUMBER,        v       NUMBER); INSERT INTO tbl ( u, v ) VALUES ( 20, 50 );INSERT INTO tbl ( u, v ) VALUES ( 21, 50 );INSERT INTO tbl ( u, v ) VALUES ( 21, 51 );INSERT INTO tbl ( u, v ) VALUES ( 22, 50 );INSERT INTO tbl ( u, v ) VALUES ( 22, 55 ); commit; WITH        FUNCTION gcd ( ui IN NUMBER, vi IN NUMBER )        RETURN NUMBER        IS                u NUMBER := ui;                v NUMBER := vi;                t NUMBER;        BEGIN                while v > 0                loop                        t := u;                        u := v;                        v:= MOD(t, v );                END loop;                RETURN abs(u);        END gcd;        SELECT u, v, gcd ( u, v )        FROM tbl/ `
Output:
```Table dropped.

Table created.

1 row created.

1 row created.

1 row created.

1 row created.

1 row created.

Commit complete.

U          V   GCD(U,V)
---------- ---------- ----------
20         50         10
21         50          1
21         51          3
22         50          2
22         55         11
```

Demonstration of SQL Server 2008

`CREATE FUNCTION gcd (  @ui INT,  @vi INT) RETURNS INT AS BEGIN    DECLARE @t INT    DECLARE @u INT    DECLARE @v INT     SET @u = @ui    SET @v = @vi     WHILE @v > 0    BEGIN        SET @t = @u;        SET @u = @v;        SET @v = @t % @v;    END;    RETURN abs( @u );END GO CREATE TABLE tbl (  u INT,  v INT); INSERT INTO tbl ( u, v ) VALUES ( 20, 50 );INSERT INTO tbl ( u, v ) VALUES ( 21, 50 );INSERT INTO tbl ( u, v ) VALUES ( 21, 51 );INSERT INTO tbl ( u, v ) VALUES ( 22, 50 );INSERT INTO tbl ( u, v ) VALUES ( 22, 55 ); SELECT u, v, dbo.gcd ( u, v )  FROM tbl; DROP TABLE tbl; DROP FUNCTION gcd; `

PostgreSQL function using a recursive common table expression

`CREATE FUNCTION gcd(INTEGER, INTEGER)RETURNS INTEGERLANGUAGE SQLAS \$function\$WITH RECURSIVE x (u, v) AS (  SELECT ABS(\$1), ABS(\$2)  UNION  SELECT v, u % v FROM x WHERE v > 0)SELECT MIN(u) FROM x;\$function\$ `
Output:
```postgres> select gcd(40902, 24140);
gcd
-----
34
SELECT 1
Time: 0.012s
```

## Stata

`function gcd(a_,b_) {	a = abs(a_)	b = abs(b_)	while (b>0) {		a = mod(a,b)		swap(a,b)	}	return(a)}`

## Swift

`// Iterative func gcd(var a: Int, var b: Int) -> Int {     a = abs(a); b = abs(b)     if (b > a) { swap(&a, &b) }     while (b > 0) { (a, b) = (b, a % b) }     return a} // Recursive func gcdr (var a: Int, var b: Int) -> Int {     a = abs(a); b = abs(b)     if (b > a) { swap(&a, &b) }     return gcd_rec(a,b)}  private func gcd_rec(a: Int, b: Int) -> Int {     return b == 0 ? a : gcd_rec(b, a % b)}  for (a,b) in [(1,1), (100, -10), (10, -100), (-36, -17), (27, 18), (30, -42)] {     println("Iterative: GCD of \(a) and \(b) is \(gcd(a, b))")    println("Recursive: GCD of \(a) and \(b) is \(gcdr(a, b))")}`
Output:
```Iterative: GCD of 1 and 1 is 1
Recursive: GCD of 1 and 1 is 1
Iterative: GCD of 100 and -10 is 10
Recursive: GCD of 100 and -10 is 10
Iterative: GCD of 10 and -100 is 10
Recursive: GCD of 10 and -100 is 10
Iterative: GCD of -36 and -17 is 1
Recursive: GCD of -36 and -17 is 1
Iterative: GCD of 27 and 18 is 9
Recursive: GCD of 27 and 18 is 9
Iterative: GCD of 30 and -42 is 6
Recursive: GCD of 30 and -42 is 6
```

## Tcl

### Iterative Euclid algorithm

`package require Tcl 8.5namespace 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.5namespace 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)
```

The ) can be omitted in TI-83 basic

## TSE SAL

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

## TXR

`\$ txr -p '(gcd (expt 2 123) (expt 6 49))'562949953421312`

## TypeScript

Iterative implementation

`function gcd(a: number, b: number) {  a = Math.abs(a);  b = Math.abs(b);   if (b > a) {    let 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: number, b: number) {  return b ? gcd_rec(b, a % b) : Math.abs(a);}`

## uBasic/4tH

Translation of: BBC BASIC
`Print "GCD of 18 : 12 = "; FUNC(_GCD_Iterative_Euclid(18,12))Print "GCD of 1071 : 1029 = "; FUNC(_GCD_Iterative_Euclid(1071,1029))Print "GCD of 3528 : 3780 = "; FUNC(_GCD_Iterative_Euclid(3528,3780)) End _GCD_Iterative_Euclid Param(2)  Local (1)  Do While [email protected]    [email protected] = [email protected]    [email protected] = [email protected]    [email protected] = [email protected] % [email protected]  LoopReturn (Abs([email protected]))`
Output:
```GCD of 18 : 12 = 6
GCD of 1071 : 1029 = 21
GCD of 3528 : 3780 = 252

0 OK, 0:205```

## 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 87843echo \$result# => 987`

## Ursa

`import "math"out (gcd 40902 24140) endl console`
Output:
`34`

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

`Function gcd(u As Long, v As Long) As Long    Dim t As Long    Do While v        t = u        u = v        v = t Mod v    Loop    gcd = uEnd Function`

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

`Public Function GCD(a As Long, b As Long) As LongWhile a <> b  If a > b Then a = a - b Else b = b - aWendGCD = aEnd Function`
Output:

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

## VBScript

`Function GCD(a,b)	Do		If a Mod b > 0 Then			c = a Mod b			a = b			b = c		Else			GCD = b			Exit Do		End If	LoopEnd Function WScript.Echo "The GCD of 48 and 18 is " & GCD(48,18) & "."WScript.Echo "The GCD of 1280 and 240 is " & GCD(1280,240) & "."WScript.Echo "The GCD of 1280 and 240 is " & GCD(3475689,23566319) & "."WScript.Echo "The GCD of 1280 and 240 is " & GCD(123456789,234736437) & "."`
Output:
```The GCD of 48 and 18 is 6.
The GCD of 1280 and 240 is 80.
The GCD of 1280 and 240 is 7.
The GCD of 1280 and 240 is 3.```

## Verilog

`module gcd  (  input reset_l,  input clk,   input [31:0] initial_u,  input [31:0] initial_v,  input load,   output reg [31:0] result,  output reg busy  ); reg [31:0] u, v; always @(posedge clk or negedge reset_l)  if (!reset_l)    begin      busy <= 0;      u <= 0;      v <= 0;    end  else    begin       result <= u + v; // Result (one of them will be zero)       busy <= u && v; // We're still busy...       // Repeatedly subtract smaller number from larger one      if (v <= u)        u <= u - v;      else if (u < v)        v <= v - u;       if (load) // Load new problem when high        begin          u <= initial_u;          v <= initial_v;          busy <= 1;        end     end endmodule `

## Visual Basic

Works with: Visual Basic version 5
Works with: Visual Basic version 6
Works with: VBA version 6.5
Works with: VBA version 7.1
`Function GCD(ByVal a As Long, ByVal b As Long) As LongDim h As Long     If a Then        If b Then            Do                h = a Mod b                a = b                b = h            Loop While b        End If        GCD = Abs(a)    Else        GCD = Abs(b)    End If End Function Sub Main()' testing the above function  Debug.Assert GCD(12, 18) = 6  Debug.Assert GCD(1280, 240) = 80  Debug.Assert GCD(240, 1280) = 80  Debug.Assert GCD(-240, 1280) = 80  Debug.Assert GCD(240, -1280) = 80  Debug.Assert GCD(0, 0) = 0  Debug.Assert GCD(0, 1) = 1  Debug.Assert GCD(1, 0) = 1  Debug.Assert GCD(3475689, 23566319) = 7  Debug.Assert GCD(123456789, 234736437) = 3  Debug.Assert GCD(3780, 3528) = 252 End Sub`

## Wortel

Operator

`@gcd a b`

Number expression

`!#~kg a b`

Iterative

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

Recursive

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

## Wren

`var gcd = Fn.new { |x, y|    while (y != 0) {        var t = y        y = x % y        x = t    }    return x} System.print("gcd(33, 77) = %(gcd.call(33, 77))")System.print("gcd(49865, 69811) = %(gcd.call(49865, 69811))")`
Output:
```gcd(33, 77) = 11
gcd(49865, 69811) = 9973
```

## 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`

## XBasic

Works with: Windows XBasic
` PROGRAM "gcddemo"VERSION "0.001" DECLARE FUNCTION Entry()DECLARE FUNCTION GcdRecursive(u&, v&)DECLARE FUNCTION GcdIterative(u&, v&)DECLARE FUNCTION GcdBinary(u&, v&) FUNCTION Entry()  m& = 49865  n& = 69811  PRINT "GCD("; LTRIM\$(STR\$(m&)); ","; n&; "):"; GcdIterative(m&, n&); " (iterative)"  PRINT "GCD("; LTRIM\$(STR\$(m&)); ","; n&; "):"; GcdRecursive(m&, n&); " (recursive)"  PRINT "GCD("; LTRIM\$(STR\$(m&)); ","; n&; "):"; GcdBinary (m&, n&); " (binary)"END FUNCTION FUNCTION GcdRecursive(u&, v&)  IF u& MOD v& <> 0 THEN    RETURN GcdRecursive(v&, u& MOD v&)  ELSE    RETURN v&  END IFEND FUNCTION FUNCTION GcdIterative(u&, v&)  DO WHILE v& <> 0    t& = u&    u& = v&    v& = t& MOD v&  LOOP  RETURN ABS(u&)END FUNCTION FUNCTION GcdBinary(u&, v&)  u& = ABS(u&)  v& = ABS(v&)  IF u& < v& THEN    t& = u&    u& = v&    v& = t&  END IF  IF v& = 0 THEN    RETURN u&  ELSE    k& = 1    DO WHILE (u& MOD 2 = 0) && (v& MOD 2 = 0)      u& = u& >> 1      v& = v& >> 1      k& = k& << 1    LOOP    IF u& MOD 2 = 0 THEN      t& = u&    ELSE      t& = -v&    END IF    DO WHILE t& <> 0      DO WHILE t& MOD 2 = 0        t& = t& \ 2      LOOP      IF t& > 0 THEN        u& = t&      ELSE        v& = -t&      END IF      t& = u& - v&    LOOP    RETURN u& * k&  END IFEND FUNCTION END PROGRAM `
Output:
```GCD(49865, 69811): 9973 (iterative)
GCD(49865, 69811): 9973 (recursive)
GCD(49865, 69811): 9973 (binary)
```

## XLISP

`GCD` is a built-in function. If we wanted to reimplement it, one (tail-recursive) way would be like this:

`(defun greatest-common-divisor (x y)	(if (= y 0)		x		(greatest-common-divisor y (mod x y)) ) )`

## XPL0

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

## Yabasic

`sub gcd(u, v)    local t     u = int(abs(u))    v = int(abs(v))    while(v)        t = u        u = v        v = mod(t, v)    wend    return uend sub print "Greatest common divisor: ", gcd(12345, 9876)`

## Z80 Assembly

Uses the iterative subtraction implementation of Euclid's algorithm because the Z80 does not implement modulus or division opcodes.

`; Inputs: a, b; Outputs: a = gcd(a, b); Destroys: c; Assumes: a and b are positive one-byte integersgcd:    cp b    ret z                   ; while a != b     jr c, else              ; if a > b     sub b                   ; a = a - b     jr gcd else:    ld c, a                 ; Save a    ld a, b                 ; Swap b into a so we can do the subtraction    sub c                   ; b = b - a    ld b, a                 ; Put a and b back where they belong    ld a, c     jr gcd`

## zkl

This is a method on integers:

`(123456789).gcd(987654321) //-->9`

Using the gnu big num library (GMP):

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

or

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

## ZX Spectrum Basic

`10 FOR n=1 TO 320 READ a,b30 PRINT "GCD of ";a;" and ";b;" = ";40 GO SUB 7050 NEXT n60 STOP 70 IF b=0 THEN PRINT ABS (a): RETURN 80 LET c=a: LET a=b: LET b=FN m(c,b): GO TO 7090 DEF FN m(a,b)=a-INT (a/b)*b100 DATA 12,16,22,33,45,67`