Greatest common divisor

From Rosetta Code
Revision as of 18:14, 14 November 2009 by Underscore (talk | contribs) (Fixed lang tags (using MediaWiki::API).)
Task
Greatest common divisor
You are encouraged to solve this task according to the task description, using any language you may know.

This task requires the finding of the greatest common divisor of two integers.

Ada

<lang ada>with Ada.Text_Io; use Ada.Text_Io;

procedure Gcd_Test is

  function Gcd (A, B : Integer) return Integer is
  begin
     if A = 0 then
        return B;
     end if;
     if B = 0 then
        return A;
     end if;
     if A > B then
        return Gcd(B, A mod B);
     else
        return Gcd(A, B mod A);
     end if;
  end Gcd;
  

begin

  Put_Line("GCD of 100, 5 is" & Integer'Image(Gcd(100, 5)));
  Put_Line("GCD of 5, 100 is" & Integer'Image(Gcd(5, 100)));
  Put_Line("GCD of 7, 23 is" & Integer'Image(Gcd(7, 23)));

end Gcd_Test;</lang>

Output:

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

ALGOL 68

<lang algol68>PROC gcd = (INT a, b) INT: (

 IF a = 0 THEN
   b
 ELIF b = 0 THEN
   a
 ELIF a > b  THEN
   gcd(b, a MOD b)
 ELSE
   gcd(a, b MOD a)
 FI     

);

main : (

 INT a = 33, b = 77;
 printf(($x"The gcd of"g" and "g" is "gl$,a,b,gcd(a,b)));
 INT c = 49865, d = 69811;
 printf(($x"The gcd of"g" and "g" is "gl$,c,d,gcd(c,d)))

)</lang> The output is: <lang algol68>The gcd of +33 and +77 is +11 The gcd of +49865 and +69811 is +9973</lang>

APL

Works with: Dyalog APL
       33 49865 ∨ 77 69811 
11 9973

If you're interested in how you'd write GCD in Dyalog, if Dyalog didn't have a primitive for it, (i.e. using other algorithms mentioned on this page: iterative, recursive, binary recursive), see different ways to write GCD in Dyalog.

Works with: APL2
       ⌈/(^/0=A∘.|X)/A←⍳⌊/X←49865 69811 
9973

AWK

The following scriptlet defines the gcd() function, then reads pairs of numbers from stdin, and reports their gcd on stdout. <lang awk>$ awk 'func gcd(p,q){return(q?gcd(q,(p%q)):p)}{print gcd($1,$2)}' 12 16 4 22 33 11 45 67 1</lang>

AutoHotkey

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

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

}</lang>

BASIC

Works with: QuickBasic version 4.5

Iterative

<lang qbasic>function gcd(a%, b%)

  if a > b then
     factor = a
  else
     factor = b
  end if
  for l = factor to 1 step -1
     if a mod l = 0 and b mod l = 0 then
        gcd = l
     end if
  next l
  gcd = 1

end function</lang>

Recursive

<lang qbasic>function gcd(a%, b%)

  if a = 0  gcd = b
  if b = 0  gcd = a
  if a > b  gcd = gcd(b, a mod b)
  gcd = gcd(a, b mod a)

end function</lang>

Bc

Works with: GNU bc
Translation of: C

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

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

}

define abs(a) {

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

}</lang>

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

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

}</lang>

Recursive

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

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

}</lang>

Iterative (Binary)

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

 u = abs(u);
 v = abs(v);
 if ( u < v ) {
   t = u; u = v; v = t;
 }
 if ( v == 0 ) { return(u); }
 k = 1;
 while (even(u) && even(v)) {
   u = u / 2; v = v / 2;
   k = k * 2;
 }
 if ( even(u) ) {
   t = -v;
 } else {
   t = u;
 }
 while (t) {
   while (even(t)) { 
     t = t / 2;
   }

   if (t > 0) {
     u = t;
   } else {
     v = -t;
   }
   t = u - v;
 }
 return (u * k);    

}</lang>

Befunge

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

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

C

Iterative Euclid algorithm

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

 int t;
 while (v) {
   t = u; 
   u = v; 
   v = t % v;
 }
 return u < 0 ? -u : u; /* abs(u) */

}</lang>

Recursive Euclid algorithm

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

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

}</lang>

Iterative binary algorithm

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

 int t, k;
 u = u < 0 ? -u : u; /* abs(u) */
 v = v < 0 ? -v : v; 
 if (u < v) {
   t = u;
   u = v;
   v = t;
 }
 if (v == 0)
   return u;
 k = 1;
 while (u & 1 == 0 && v & 1 == 0) { /* u, v - even */
   u >>= 1; v >>= 1;
   k <<= 1;
 }
 t = (u & 1) ? -v : u;
 while (t) {
   while (t & 1 == 0) 
     t >>= 1;
   if (t > 0)
     u = t;
   else
     v = -t;
   t = u - v;
 }
 return u * k;        

}</lang>

Notes on performance

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

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

gcd(40902, 24140) takes us about 2.86 µsec

Common Lisp

We call the function gcd2 so as not to conflict with common-lisp:gcd. <lang lisp>(defun gcd2 (a b)

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

D

<lang d>bool isEven(int number) {

 return number%2 == 0;

}

int gcd(int a, int b) {

 if(a == 0)
   return b;
 else if(b == 0)
   return a;
 else if(isEven(a) && isEven(b))
   return gcd(a>>1, b>>1) << 1;
 else if(isEven(a) && !isEven(b))
   return gcd(a>>1, b);
 else if(!isEven(a) && isEven(b))
   return gcd(a, b>>1);
 else if(a >= b)
   return gcd(a-b, b);
 
 return gcd(a, b-a);

}</lang>

E

Translation of: Python

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

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

}</lang>

Erlang

Translation of: OCaml

<lang erlang>gcd(0,B) -> abs(B); gcd(A,0) -> abs(A); gcd(A,B) when A > B -> gcd(B, A rem B); gcd(A,B) -> gcd(A, B rem A).</lang>

FALSE

<lang false>[[$][$@$@$@\/*-]#%]g: 10 15 g;!. { 5 }</lang>

Forth

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

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

Fortran

Works with: Fortran version 95 and later

Recursive Euclid algorithm

<lang fortran>recursive function gcd_rec(u, v) result(gcd)

   integer             :: gcd
   integer, intent(in) :: u, v
   
   if (mod(u, v) /= 0) then
       gcd = gcd_rec(v, mod(u, v))
   else
       gcd = v
   end if

end function gcd_rec</lang>

Iterative Euclid algorithm

<lang fortran>subroutine gcd_iter(value, u, v)

 integer, intent(out) :: value
 integer, intent(inout) :: u, v
 integer :: t
 do while( v /= 0 )
    t = u
    u = v
    v = mod(t, v)
 enddo
 value = abs(u)

end subroutine gcd_iter</lang>

A different version, and implemented as function

<lang fortran>function gcd(v, t)

 integer :: gcd
 integer, intent(in) :: v, t
 integer :: c, b, a
 b = t
 a = v
 do
    c = mod(a, b)
    if ( c == 0) exit
    a = b
    b = c
 end do
 gcd = b ! abs(b)

end function gcd</lang>

Iterative binary algorithm

<lang fortran>subroutine gcd_bin(value, u, v)

 integer, intent(out) :: value
 integer, intent(inout) :: u, v
 integer :: k, t
 u = abs(u)
 v = abs(v)
 if( u < v ) then
    t = u
    u = v
    v = t
 endif
 if( v == 0 ) then
    value = u
    return
 endif
 k = 1
 do while( (mod(u, 2) == 0).and.(mod(v, 2) == 0) )
    u = u / 2
    v = v / 2
    k = k * 2
 enddo
 if( (mod(u, 2) == 0) ) then
    t = u
 else
    t = -v
 endif
 do while( t /= 0 )
    do while( (mod(t, 2) == 0) )
       t = t / 2
    enddo
    if( t > 0 ) then
       u = t
    else
       v = -t
    endif
    t = u - v
 enddo
 value = u * k

end subroutine gcd_bin</lang>

Notes on performance

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

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

Genyris

Recursive

<lang genyris>def gcd (u v)

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

Iterative

<lang genyris>def gcd (u v)

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

Groovy

Recursive

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

Iterative

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

Test program: <lang groovy>println " R I" println "gcd(28, 0) = ${gcdR(28, 0)} == ${gcdI(28, 0)}" println "gcd(0, 28) = ${gcdR(0, 28)} == ${gcdI(0, 28)}" println "gcd(0, -28) = ${gcdR(0, -28)} == ${gcdI(0, -28)}" println "gcd(70, -28) = ${gcdR(70, -28)} == ${gcdI(70, -28)}" println "gcd(70, 28) = ${gcdR(70, 28)} == ${gcdI(70, 28)}" println "gcd(28, 70) = ${gcdR(28, 70)} == ${gcdI(28, 70)}" println "gcd(800, 70) = ${gcdR(800, 70)} == ${gcdI(800, 70)}" println "gcd(27, -70) = ${gcdR(27, -70)} == ${gcdI(27, -70)}"</lang>

Output:

                R     I
gcd(28, 0)   = 28 == 28
gcd(0, 28)   = 28 == 28
gcd(0, -28)  = 28 == 28
gcd(70, -28) = 14 == 14
gcd(70, 28)  = 14 == 14
gcd(28, 70)  = 14 == 14
gcd(800, 70) = 10 == 10
gcd(27, -70) =  1 ==  1

Haskell

That is already available as the function gcd in the Prelude. Here's the implementation:

<lang haskell>gcd :: (Integral a) => a -> a -> a gcd 0 0 = error "Prelude.gcd: gcd 0 0 is undefined" gcd x y = gcd' (abs x) (abs y) where

 gcd' a 0  =  a
 gcd' a b  =  gcd' b (a `rem` b)</lang>

J

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

Java

Iterative

<lang java>public static long gcd(long a, long b){

  long factor= Math.max(a, b);
  for(long loop= factor;loop > 1;loop--){
     if(a % loop == 0 && b % loop == 0){
        return loop;
     }
  }
  return 1;

}</lang>

Recursive

<lang java>public static long gcd(long a, long b){

  if(a == 0) return b;
  if(b == 0) return a;
  if(a > b) return gcd(b, a % b);
  return gcd(a, b % a);

}</lang>

JavaScript

Iterative. <lang javascript>function gcd(a,b) {

   if (a < 0) a = -a;
   if (b < 0) b = -b;
   if (b > a) {var temp = a; a = b; b = temp;}
   while (true) {
       a %= b;
       if (a == 0) return b;
       b %= a;
       if (b == 0) return a;
   }

}</lang>

Joy

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

<lang logo>to gcd :a :b

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

end</lang>

Lucid

dataflow algorithm

<lang lucid>gcd(n,m) where

  z = [% n, m %] fby if x > y then [% x - y, y %] else [% x, y - x%] fi;
  x = hd(z);
  y = hd(tl(z));
  gcd(n, m) = (x asa x*y eq 0) fby eod;

end</lang>

Mathematica

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

MATLAB

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

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

MAXScript

Iterative Euclid algorithm

<lang maxscript>fn gcdIter a b = (

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

)</lang>

Recursive Euclid algorithm

<lang maxscript>fn gcdRec a b = (

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

)</lang>

Modula-3

<lang modula3>MODULE GCD EXPORTS Main;

IMPORT IO, Fmt;

PROCEDURE GCD(a, b: CARDINAL): CARDINAL =

 BEGIN
   IF a = 0 THEN
     RETURN b;
   ELSIF b = 0 THEN
     RETURN a;
   ELSIF a > b THEN
     RETURN GCD(b, a MOD b);
   ELSE
     RETURN GCD(a, b MOD a);
   END;
 END GCD;

BEGIN

 IO.Put("GCD of 100, 5 is " & Fmt.Int(GCD(100, 5)) & "\n");
 IO.Put("GCD of 5, 100 is " & Fmt.Int(GCD(5, 100)) & "\n");
 IO.Put("GCD of 7, 23 is " & Fmt.Int(GCD(7, 23)) & "\n");

END GCD.</lang>

Output:

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

Nial

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

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

  1. one is termination condition

red is cull filter (0 unequal) link [mod [rest, first] , first] one is or [= [1 first, tally], > [2 first, first]] gcd is fork [one, first, gcd red] sort <=</lang>

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

OCaml

<lang ocaml>let rec gcd a b =

 if      a = 0 then b
 else if b = 0 then a
 else if a > b then gcd b (a mod b)
 else               gcd a (b mod a)</lang>

Octave

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

Pascal

<lang pascal>function gcd(a, b: integer): integer;

var
 tmp: integer;
begin
 while b <> 0 do
  begin
   tmp := a mod b;
   a := b;
   b := tmp
  end;
 gcd := a
end;</lang>

Perl

Iterative Euclid algorithm

<lang perl>sub gcd_iter($$) {

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

}</lang>

Recursive Euclid algorithm

<lang perl>sub gcd($$) {

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

}</lang>

Iterative binary algorithm

<lang perl>sub gcd_bin($$) {

 my ($u, $v) = @_;
 $u = abs($u);
 $v = abs($v);
 if ($u < $v) {
   ($u, $v) = ($v, $u);
 }
 if ($v == 0) {
   return $u;
 }
 my $k = 1;
 while ($u & 1 == 0 && $v & 1 == 0) {
   $u >>= 1;
   $v >>= 1;
   $k <<= 1;
 }
 my $t = ($u & 1) ? -$v : $u;
 while ($t) {
   while ($t & 1 == 0) {
     $t >>= 1;
   }
   if ($t > 0) {
     $u = $t;
   } else {
     $v = -$t;
   }
   $t = $u - $v;
 }
 return $u * $k;

}</lang>

Notes on performance

<lang perl>use Benchmark qw(cmpthese);

my $u = 40902; my $v = 24140; cmpthese(-5, {

 'gcd' => sub { gcd($u, $v); },
 'gcd_iter' => sub { gcd_iter($u, $v); },
 'gcd_bin' => sub { gcd_bin($u, $v); },

});</lang>

Output on 'Intel(R) Pentium(R) 4 CPU 1.50GHz' / Linux / Perl 5.8.8:

             Rate  gcd_bin gcd_iter      gcd
gcd_bin  321639/s       --     -12%     -20%
gcd_iter 366890/s      14%       --      -9%
gcd      401149/s      25%       9%       --

Perl 6

Works with: Rakudo version #21 "Seattle"

Iterative

<lang perl6>sub gcd (Int $a is copy, Int $b is copy) {

  $a & $b == 0 and fail;
  ($a, $b) = ($b, $a % $b) while $b;
  return abs $a;

}</lang>

Recursive

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

Pop11

Built-in gcd

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

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

Iterative Euclid algorithm

<lang pop11>define gcd(k, l) -> r;

   lvars k , l, r = l;
   abs(k) -> k;
   abs(l) -> l;
   if k < l then (k, l) -> (l, k) endif;
   while l /= 0 do
       (l, k rem l) -> (k, l)
   endwhile;
   k -> r;

enddefine;</lang>

PowerShell

Recursive Euclid Algorithm

<lang powershell>function get-gcd ($x, $y) {

 if($x-eq$y){ return $y }
 if($x-gt$y){
   $a=$x
   $b=$y
 }
 else {
   $a=$y
   $b=$x
 }
 while (($a%$b)-ne0){
   $tmp=$a%$b
   $a=$b
   $b=$tmp
 }
 return $b

}</lang>

Prolog

Recursive Euclid Algorithm

<lang prolog>gcd(X, 0, X):- !. gcd(0, X, X):- !. gcd(X, Y, D):- X > Y, !, Z is X mod Y, gcd(Y, Z, D). gcd(X, Y, D):- Z is Y mod X, gcd(X, Z, D).</lang>

Repeated Subtraction

<lang prolog>gcd(X, 0, X):- !. gcd(0, X, X):- !. gcd(X, Y, D):- X =< Y, !, Z is Y - X, gcd(X, Z, D). gcd(X, Y, D):- gcd(Y, X, D).</lang>

Python

Iterative Euclid algorithm

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

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

Recursive Euclid algorithm

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

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

Tests

>>> gcd(0,0)
0
>>> gcd(0, 10) == gcd(10, 0) == gcd(-10, 0) == gcd(0, -10) == 10
True
>>> gcd(9, 6) == gcd(6, 9) == gcd(-6, 9) == gcd(9, -6) == gcd(6, -9) == gcd(-9, 6) == 3
True
>>> gcd(8, 45) == gcd(45, 8) == gcd(-45, 8) == gcd(8, -45) == gcd(-8, 45) == gcd(45, -8) == 1
True
>>> gcd(40902, 24140) # check Knuth :)
34

Iterative binary algorithm

See The Art of Computer Programming by Knuth (Vol.2) <lang python>def gcd_bin(u, v):

   u, v = abs(u), abs(v) # u >= 0, v >= 0
   if u < v:
       u, v = v, u # u >= v >= 0
   if v == 0:
       return u
  
   # u >= v > 0
   k = 1
   while u & 1 == 0 and v & 1 == 0: # u, v - even
       u >>= 1; v >>= 1
       k <<= 1
      
   t = -v if u & 1 else u
   while t:
       while t & 1 == 0:
           t >>= 1
       if t > 0:
           u = t
       else:
           v = -t
       t = u - v
   return u * k</lang>

Notes on performance

gcd(40902, 24140) takes us about 17 µsec

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

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

R

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

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

}</lang>

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

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

}</lang>

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

Ruby

That is already available as the gcd method of integers:

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

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

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

end</lang>

SETL

<lang setl>a := 33; b := 77; print(" the gcd of",a," and ",b," is ",gcd(a,b));

c := 49865; d := 69811; print(" the gcd of",c," and ",d," is ",gcd(c,d));

proc gcd (u, v);

 return if v = 0 then abs u else gcd (v, u mod v) end;

end;</lang>

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

Scheme

<lang scheme>(define (gcd a b)

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

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

Slate

Slate's Integer type has gcd defined:

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

Iterative Euclid algorithm

<lang slate>x@(Integer traits) gcd: y@(Integer traits) "Euclid's algorithm for finding the greatest common divisor." [| n m temp |

 n: x.
 m: y.
 [n isZero] whileFalse: [temp: n. n: m \\ temp. m: temp].
 m abs

].</lang>

Recursive Euclid algorithm

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

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

].</lang>

Smalltalk

The Integer class has its gcd method.

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

An implementation of the Iterative Euclid's algorithm

<lang smalltalk>|gcd_iter|

gcd_iter := [ :a :b | |u v| u := a. v := b.

  [ v > 0 ]
    whileTrue: [ |t|
       t := u copy.
       u := v copy.
       v := t rem: v
    ].
    u abs

].

(gcd_iter value: 40902 value: 24140)

 printNl.</lang>

Standard ML

<lang sml>fun gcd a 0 = a

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

Tcl

Iterative Euclid algorithm

<lang tcl>package require Tcl 8.5 namespace path {::tcl::mathop ::tcl::mathfunc} proc gcd_iter {p q} {

   while {$q != 0} {
       lassign [list $q [% $p $q]] p q
   }
   abs $p

}</lang>

Recursive Euclid algorithm

<lang tcl>proc gcd {p q} {

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

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

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

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

Iterative binary algorithm

<lang tcl>package require Tcl 8.5 namespace path {::tcl::mathop ::tcl::mathfunc} proc gcd_bin {p q} {

   if {$p == $q} {return [abs $p]}
   set p [abs $p]
   if {$q == 0} {return $p}
   set q [abs $q]
   if {$p < $q} {lassign [list $q $p] p q}
   set k 1
   while {($p & 1) == 0 && ($q & 1) == 0} {
       set p [>> $p 1]
       set q [>> $q 1]
       set k [<< $k 1]
   }
   set t [expr {$p & 1 ? -$q : $p}]
   while {$t} {
       while {$t & 1 == 0} {set t [>> $t 1]}
       if {$t > 0} {set p $t} {set q [- $t]}
       set t [- $p $q]
   }
   return [* $p $k]

}</lang>

Notes on performance

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

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

}</lang> Outputs:

gcd_iter - 4.46712 microseconds per iteration
gcd      - 5.73969 microseconds per iteration
gcd_bin  - 9.25613 microseconds per iteration


TI-83 BASIC, TI-89 BASIC

gcd(A,B)

Ursala

This doesn't need to be defined because it's a library function, but it can be defined like this based on a recursive implementation of Euclid's algorithm. This isn't the simplest possible solution because it includes a bit shifting optimization that happens when both operands are even. <lang Ursala>#import nat

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

test = ^(~&,gcd)* <(25,15),(36,16),(120,45),(30,100)></lang> output:

<
   (25,15): 5,
   (36,16): 4,
   (120,45): 15,
   (30,100): 10>

V

like joy

iterative

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

recursive

like python

[gcd
   [zero?] [pop]
      [swap [dup] dip swap %]
   tailrec].

same with view: (swap [dup] dip swap % is replaced with a destructuring view)

[gcd
   [zero?] [pop]
     [[a b : [b a b %]] view i]
   tailrec].

running it

|1071 1029 gcd
=21