Greatest common divisor

From Rosetta Code

Jump to: navigation, search
Greatest common divisor is a programming task. Visitors like you are encouraged to solve it according to the task description, using any language they may happen to know.
Add to BlogMarksAdd to del.icio.usAdd to diggAdd to NewsvineAdd to redditAdd to Slashdot

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

Contents

[edit] 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;

Output: 

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

[edit] ALGOL 68

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

The output is: 

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

[edit] APL

Works with: Dyalog APL 

       33 49865 ∨ 77 69811 
11 9973

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

Works with: APL2 

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

[edit] AWK

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

$ awk 'func gcd(p,q){return(q?gcd(q,(p%q)):p)}{print gcd($1,$2)}'
12 16
4
22 33
11
45 67
1

[edit] AutoHotkey

contributed by Laszlo on the ahk forum 

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

[edit] BASIC

Works with: QuickBasic version 4.5

[edit] Iterative

FUNCTION gcd(a%, b%)
   IF a > b THEN
      factor = a
   ELSE
      factor = b
   END IF
   FOR l = factor TO 1 STEP -1
      IF a MOD l = 0 AND b MOD l = 0 THEN
         gcd = l
      END IF
   NEXT l
   gcd = 1
END FUNCTION

[edit] Recursive

FUNCTION gcd(a%, b%)
   IF a = 0  gcd = b
   IF b = 0  gcd = a
   IF a > b  gcd = gcd(b, a MOD b)
   gcd = gcd(a, b MOD a)
END FUNCTION


[edit] Bc

Works with: GNU bc Translation of: C

Utility functions: 

define even(a)
{
  if ( a % 2 == 0 ) {
    return(1);
  } else {
    return(0);
  }
}
 
define abs(a)
{ 
  if (a<0) {
    return(-a);
  } else {
    return(a);
  }
}

Iterative (Euclid) 

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

Recursive 

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

Iterative (Binary) 

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

[edit] Befunge

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

[edit] C

[edit] Iterative Euclid algorithm

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

[edit] Recursive Euclid algorithm

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

[edit] Iterative binary algorithm

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

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

[edit] Clojure

(defn gcd 
    "(gcd a b) computes the greatest common divisor of a and b."
    [a b]
    (if (zero? b)
        a
        (recur b (mod a b)) ; This is (gcd b (mod a b)), but with explicit tail call optimization.
    )
)


[edit] Common Lisp

We call the function gcd2 so as not to conflict with common-lisp:gcd. 

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

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

[edit] E

Translation of: Python 

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

[edit] Erlang

Translation of: OCaml 

gcd(0,B) -> abs(B);
gcd(A,0) -> abs(A);
gcd(A,B) when A > B -> gcd(B, A rem B);
gcd(A,B) -> gcd(A, B rem A).

[edit] Factor

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

[edit] FALSE

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

[edit] Forth

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

[edit] Fortran

Works with: Fortran version 95 and later

[edit] Recursive Euclid algorithm

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

[edit] Iterative Euclid algorithm

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

A different version, and implemented as function 

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

[edit] Iterative binary algorithm

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

[edit] Notes on performance

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

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

[edit] Genyris

[edit] Recursive

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

[edit] Iterative

def gcd (u v)
    u = (abs u)
    v = (abs v)
    while (not (equal? v 0))
       var tmp (% u v)
       u = v
       v = tmp
    u

[edit] gnuplot

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

Example: 

print gcd (111111, 1111)

Output: 

11

[edit] Groovy

[edit] Recursive

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

[edit] Iterative

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

Test program: 

println "                R     I"
println "gcd(28, 0)   = ${gcdR(28, 0)} == ${gcdI(28, 0)}"
println "gcd(0, 28)   = ${gcdR(0, 28)} == ${gcdI(0, 28)}"
println "gcd(0, -28)  = ${gcdR(0, -28)} == ${gcdI(0, -28)}"
println "gcd(70, -28) = ${gcdR(70, -28)} == ${gcdI(70, -28)}"
println "gcd(70, 28)  = ${gcdR(70, 28)} == ${gcdI(70, 28)}"
println "gcd(28, 70)  = ${gcdR(28, 70)} == ${gcdI(28, 70)}"
println "gcd(800, 70) = ${gcdR(800, 70)} == ${gcdI(800, 70)}"
println "gcd(27, -70) =  ${gcdR(27, -70)} ==  ${gcdI(27, -70)}"

Output: 

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

[edit] Haskell

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

gcd :: (Integral a) => a -> a -> a
gcd 0 0 =  error "Prelude.gcd: gcd 0 0 is undefined"
gcd x y =  gcd' (abs x) (abs y) where
  gcd' a 0  =  a
  gcd' a b  =  gcd' b (a `rem` b)

[edit] J

x+.y

[edit] Java

[edit] Iterative

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

[edit] Recursive

public static long gcd(long a, long b){
   if(a == 0) return b;
   if(b == 0) return a;
   if(a > b) return gcd(b, a % b);
   return gcd(a, b % a);
}

[edit] JavaScript

Iterative. 

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

Recursive. 

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

[edit] Joy

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

[edit] Logo

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

[edit] Lua

Translation of: C 

function gcd(a,b)
	if b ~= 0 then
		return gcd(b, a % b)
	else
		return math.abs(a)
	end
end
 
function demo(a,b)
	print("GCD of " .. a .. " and " .. b .. " is " .. gcd(a, b))
end
 
demo(100, 5)
demo(5, 100)
demo(7, 23)

Output: 

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

[edit] Lucid

[edit] dataflow algorithm

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

[edit] Mathematica

GCD[a, b]

[edit] MATLAB

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

[edit] MAXScript

[edit] Iterative Euclid algorithm

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

[edit] Recursive Euclid algorithm

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

[edit] Modula-3

MODULE GCD EXPORTS Main;
 
IMPORT IO, Fmt;
 
PROCEDURE GCD(a, b: CARDINAL): CARDINAL =
  BEGIN
    IF a = 0 THEN
      RETURN b;
    ELSIF b = 0 THEN
      RETURN a;
    ELSIF a > b THEN
      RETURN GCD(b, a MOD b);
    ELSE
      RETURN GCD(a, b MOD a);
    END;
  END GCD;
 
BEGIN
  IO.Put("GCD of 100, 5 is " & Fmt.Int(GCD(100, 5)) & "\n");
  IO.Put("GCD of 5, 100 is " & Fmt.Int(GCD(5, 100)) & "\n");
  IO.Put("GCD of 7, 23 is " & Fmt.Int(GCD(7, 23)) & "\n");
END GCD.

Output: 

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

[edit] Nial

Nial provides gcd in the standard lib. 

|loaddefs 'niallib/gcd.ndf'
|gcd 6 4
=2

defining it for arrays 

# red is the reduction operator for a sorted list
# one is termination condition
red is cull filter (0 unequal) link [mod [rest, first] , first]
one is or [= [1 first, tally], > [2 first,  first]]
gcd is fork [one, first, gcd red] sort <=

Using it 

|gcd 9 6 3
=3

[edit] OCaml

let rec gcd a b =
  if      a = 0 then b
  else if b = 0 then a
  else if a > b then gcd b (a mod b)
  else               gcd a (b mod a)

[edit] Octave

r = gcd(a, b)

[edit] Oz

declare
  fun {UnsafeGCD A B}
     if B == 0 then
        A
     else
        {UnsafeGCD B A mod B}
     end
  end
 
  fun {GCD A B}
     if A == 0 andthen B == 0 then
        raise undefined(gcd 0 0) end
     else
        {UnsafeGCD {Abs A} {Abs B}}
     end
  end
in
  {Show {GCD 456 ~632}}

[edit] 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;

[edit] Perl

[edit] Iterative Euclid algorithm

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

[edit] Recursive Euclid algorithm

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

[edit] Iterative binary algorithm

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

[edit] Notes on performance

use Benchmark qw(cmpthese);
 
my $u = 40902;
my $v = 24140;
cmpthese(-5, {
  'gcd' => sub { gcd($u, $v); },
  'gcd_iter' => sub { gcd_iter($u, $v); },
  'gcd_bin' => sub { gcd_bin($u, $v); },
});

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

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

[edit] Perl 6

Works with: Rakudo version #21 "Seattle"

[edit] Iterative

sub gcd (Int $a is copy, Int $b is copy) {
   $a & $b == 0 and fail;
   ($a, $b) = ($b, $a % $b) while $b;
   return abs $a;
}

[edit] Recursive

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

[edit] PicoLisp

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

[edit] PL/I

 
GCD: procedure (a, b) returns (fixed binary (31)) recursive;
   declare (a, b) fixed binary (31);
 
   if b = 0 then return (a);
 
   return (GCD (b, mod(a, b)) );
 
end GCD;
 

[edit] Pop11

[edit] Built-in gcd

gcd_n(15, 12, 2) =>

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

[edit] Iterative Euclid algorithm

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

[edit] PowerShell

[edit] Recursive Euclid Algorithm

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

[edit] Prolog

[edit] Recursive Euclid Algorithm

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

[edit] Repeated Subtraction

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


[edit] PureBasic

Iterative 

Procedure GCD(x, y)
  Protected r
  While y <> 0
    r = x % y
    x = y
    y = r
  Wend
  ProcedureReturn y
EndProcedure

Recursive 

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

[edit] Python

[edit] Built-in

Works with: Python version 2.6+ 

from fractions import gcd

[edit] Iterative Euclid algorithm

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

[edit] Recursive Euclid algorithm

Interpreter: Python 2.5 

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

[edit] Tests

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

[edit] Iterative binary algorithm

See The Art of Computer Programming by Knuth (Vol.2) 

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

[edit] Notes on performance

gcd(40902, 24140) takes us about 17 µsec (Euclid, not built-in)

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

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

[edit] R

"%gcd%" <- function(u, v) {
  ifelse(u %% v != 0, v %gcd% (u%%v), v)
}
"%gcd%" <- function(v, t) {
  while ( (c <- v%%t) != 0 ) {
    v <- t
    t <- c
  }
}
print(50 %gcd% 75)


[edit] REBOL

 
gcd: func [
    {Returns the greatest common denominator of m and n.}
    m [integer!]
    n [integer!]
][
    ;Euclid's algorithm
    abs either zero? n [0] [either zero? (m // n) [n] [gcd n (m // n)]]
]
 

[edit] Ruby

That is already available as the gcd method of integers: 

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

Here's an implementation: 

def gcd(u, v)
  u, v = u.abs, v.abs
  while v > 0
    u, v = v, u % v
  end
  u
end

[edit] Scala

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

[edit] Scheme

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (modulo a b))))

or using the standard function included with Scheme (takes any number of arguments): 

(gcd a b)

[edit] Seed7

const func integer: gcd (in var integer: a, in var integer: b) is func
  result
    var integer: result is 0;
  local
    var integer: help is 0;
  begin
    while a <> 0 do
      help := b rem a;
      b := a;
      a := help;
    end while;
    result := b;
  end func;

Original source: [1]

[edit] SETL

a := 33; b := 77;
print(" the gcd of",a," and ",b," is ",gcd(a,b));
 
c := 49865; d := 69811;
print(" the gcd of",c," and ",d," is ",gcd(c,d));
 
proc gcd (u, v);
  return if v = 0 then abs u else gcd (v, u mod v) end;
end;

Output: 

the gcd of 33  and  77  is  11
the gcd of 49865  and  69811  is  9973

[edit] Slate

Slate's Integer type has gcd defined: 

40902 gcd: 24140

[edit] Iterative Euclid algorithm

x@(Integer traits) gcd: y@(Integer traits)
"Euclid's algorithm for finding the greatest common divisor."
[| n m temp |
  n: x.
  m: y.
  [n isZero] whileFalse: [temp: n. n: m \\ temp. m: temp].
  m abs
].

[edit] Recursive Euclid algorithm

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

[edit] Smalltalk

The Integer class has its gcd method. 

(40902 gcd: 24140) displayNl

An implementation of the Iterative Euclid's algorithm 

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

[edit] Standard ML

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

[edit] Tcl

[edit] Iterative Euclid algorithm

package require Tcl 8.5
namespace path {::tcl::mathop ::tcl::mathfunc}
proc gcd_iter {p q} {
    while {$q != 0} {
        lassign [list $q [% $p $q]] p q
    }
    abs $p
}

[edit] Recursive Euclid algorithm

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

With Tcl 8.6, this can be optimized slightly to: 

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

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

[edit] Iterative binary algorithm

package require Tcl 8.5
namespace path {::tcl::mathop ::tcl::mathfunc}
proc gcd_bin {p q} {
    if {$p == $q} {return [abs $p]}
    set p [abs $p]
    if {$q == 0} {return $p}
    set q [abs $q]
    if {$p < $q} {lassign [list $q $p] p q}
    set k 1
    while {($p & 1) == 0 && ($q & 1) == 0} {
        set p [>> $p 1]
        set q [>> $q 1]
        set k [<< $k 1]
    }
    set t [expr {$p & 1 ? -$q : $p}]
    while {$t} {
        while {$t & 1 == 0} {set t [>> $t 1]}
        if {$t > 0} {set p $t} {set q [- $t]}
        set t [- $p $q]
    }
    return [* $p $k]
}

[edit] Notes on performance

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

Outputs: 

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


[edit] TI-83 BASIC, TI-89 BASIC

gcd(A,B)

[edit] Ursala

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

#import nat
 
gcd = ~&B?\~&Y ~&alh^?\~&arh2faltPrXPRNfabt2RCQ @a ~&ar^?\~&al ^|R/~& ^/~&r remainder

test program: 

#cast %nWnAL
 
test = ^(~&,gcd)* <(25,15),(36,16),(120,45),(30,100)>

output: 

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

[edit] V

like joy

[edit] iterative

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

[edit] recursive

like python 

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

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

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

running it 

|1071 1029 gcd
=21
Retrieved from "http://rosettacode.org/wiki/Greatest_common_divisor"
Personal tools
Google AdSense