User talk:NevilleDNZ/GeSHi sandbox

From Rosetta Code

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

Ada

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

</ada> Output:

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

ALGOL 68

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

</algol-68> The output is:

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

C

Iterative Euclid algorithm

<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) */
}

</c>

Recursive Euclid algorithm

<c>

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

</c>

Iterative binary algorithm

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

} </c>

Notes on performance

gcd_iter(40902, 24140) takes us about 2.87 usec

gcd_bin(40902, 24140) takes us about 2.47 usec

gcd(40902, 24140) takes us about 2.86 usec

Forth

<forth>

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

</forth>

Fortran

Iterative Euclid algorithm

<fortran>

      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

</fortran>

Iterative binary algorithm

<fortran>

      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

</fortran>

Notes on performance

gcd_iter(40902, 24140) takes us about 2.8 usec

gcd_bin(40902, 24140) takes us about 2.5 usec

J

<j>

x+.y

</j>

Java

Iterative

<java>

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

</java>

Recursive

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

</java>

OCaml

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

</OCaml>

Perl

Iterative Euclid algorithm

<perl>

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

</perl>

Recursive Euclid algorithm

<perl>

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

</perl>

Iterative binary algorithm

<perl>

sub 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 ($u & 1 == 0 && $v & 1 == 0) {
    $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;
}

</perl>

Notes on performance

<perl>

use Benchmark qw(cmpthese);

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

</perl> 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%       --

Python

Iterative Euclid algorithm

<python>

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

</python>

Recursive Euclid algorithm

Interpreter: Python 2.5 <python>

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

</python>

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

</python>

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