Greatest common divisor

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

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

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;

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

C

Iterative Euclid algorithm

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

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

Notes on performance

gcd_iter(40902, 24140) takes us about 2.87 usec

gcd_bin(40902, 24140) takes us about 2.47 usec

Forth

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

Fortran

Iterative Euclid algorithm

      subroutine gcd_iter(value, u, v)
Cf2py integer intent(out) :: value
      integer value, u, v, t
      intrinsic abs, mod
C
      do while( v.NE.0 )
         t = u
         u = v
         v = mod(t, v)
      enddo
      value = abs(u)
      end subroutine gcd_iter

Iterative binary algorithm

      subroutine gcd_bin(value, u, v)
Cf2py integer intent(out) :: value
      integer value, u, v, k, t, abs, mod
      intrinsic abs, mod
      u = abs(u)
      v = abs(v)
      if( u.lt.v ) then
         t = u
         u = v
         v = t
      endif
      if( v.eq.0 ) then
         value = u
         return
      endif
      k = 1
      do while( (mod(u, 2).eq.0).and.(mod(v, 2).eq.0) )
         u = u / 2
         v = v / 2
         k = k * 2
      enddo
      if( (mod(u, 2).eq.0) ) then
         t = u
      else
         t = -v
      endif
      do while( t.ne.0 )
         do while( (mod(t, 2).eq.0) )
            t = t / 2
         enddo
         if( t.gt.0 ) then
            u = t
         else
            v = -t
         endif
         t = u - v
      enddo
      value = u * k
      end subroutine gcd_bin

Notes on performance

gcd_iter(40902, 24140) takes us about 2.8 usec

gcd_bin(40902, 24140) takes us about 2.5 usec

J

x+.y

Java

Iterative

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

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

Python

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 usec

gcd_iter(40902, 24140) takes us about 11 usec

gcd_bin(40902, 24140) takes us about 41 usec