Wasting time with the Euclidean Algorithm

The other night, I was very bored so... When I remembered reading about the Euclidean Algorithm on Wikipedia, which is a method of finding the greatest common denominator (gcd). I fed several implementations through ye ol'time(1) to get a rough idea of what differences they made.

At first I did it in Ruby and C for comparison, then I recompiled the *.c files with maximum optimization. Tonight I added a set of Java and Python files to the setup, I'll probably include Bourne Shell and Perl later for fun.


For any one interested,

C // no optimization
./iteration 0.00s user 0.00s system 50% cpu 0.003 total
./recursion 0.00s user 0.00s system 66% cpu 0.002 total
./original 0.00s user 0.00s system 57% cpu 0.003 total
Ruby
./iteration.rb 0.01s user 0.00s system 59% cpu 0.014 total
./recursion.rb 0.00s user 0.00s system 79% cpu 0.010 total
./original.rb 0.00s user 0.01s system 75% cpu 0.010 total
C // optimized, -O3
./iteration-o 0.00s user 0.00s system 48% cpu 0.003 total
./recursion-o 0.00s user 0.00s system 32% cpu 0.005 total
./original-o 0.00s user 0.00s system 37% cpu 0.004 total
Java
java EuclideanIteration 0.39s user 0.38s system 66% cpu 1.165 total
java EuclideanRecursion 0.48s user 0.30s system 72% cpu 1.066 total
java EuclideanOriginal 0.36s user 0.42s system 67% cpu 1.155 total
Python
./iteration.py 0.01s user 0.01s system 59% cpu 0.034 total
./recursion.py 0.01s user 0.01s system 65% cpu 0.032 total
./original.py 0.01s user 0.01s system 65% cpu 0.031 total

done with:

ruby 1.8.6 (2007-03-13 patchlevel 0) [i386-freebsd6]
gcc version 3.4.6 [FreeBSD] 20060305
javac 1.5.0
Python 2.5.1

The C versions were the same sources but compiled with -O3 for the optimized
version.

I've assigned each outcome a score, 3 for what I feel is fastest, 2 for the intermediate (often close) and 1 for the worst and totalled it:

method  C RB C(-O3) Java Python Total
iteration 2 1 3 2 2 10
recursion 3 2 2 1 1 9
original 1 3 1 3 3 11

And the code, which I tried to keep similar. Also the gcd()/mygcd() routines were always implemented as a function because of the recursive version in the tests.

#include <stdio.h>

#define A 1071
#define B 1029

int
mygcd( int a, int b ) {
 int t = 0;
 while ( b != 0 ) {
  t = b;
  b = a % b;
  a = t;
 }
 return a;
}

int
main(void) {
 mygcd(A, B);
 return 0;
}


#include <stdio.h>

#define A 1071
#define B 1029

int
mygcd( int a, int b ) {
 if ( b == 0 ) {
  return a;
 } else {
  return mygcd( b, a%b );
 }
}

int
main(void) {
 mygcd(A, B);
 return 0;
}


#include <stdio.h>
#define A 1071
#define B 1029


int
mygcd( int a, int b ) {
 while ( b != 0 ) {
  if ( a > b ) {
   a = a-b;
  } else {
   b = b-a;
  }
 }
  return a;
}

int
main(void) {
 mygcd(A, B);
 return 0;
}

#!/usr/local/bin/ruby -w

def gcd(a, b)
  while b != 0
    t = b
    b = a % b
    a = t
  end
  return a

gcd( 1071, 1029 )
#!/usr/local/bin/ruby -w

def gcd(a,b)
  if b == 0
    return a
  else
    return gcd(b, a % b )
  end
end

gcd( 1071, 1029 )
#!/usr/local/bin/ruby -w

def gcd( a, b )
  while b != 0
    if a > b
      a = a - b
    else
      b = b - a
    end
  end
  return a
end

gcd( 1071, 1029 )

class EuclideanIteration {
 static final int A = 1071;
 static final int B = 1029;

 public static int
 mygcd( int a, int b ) {
  int t = 0;
  while ( b != 0 ) {
   t = b;
   b = a % b;
   a = t;
  }
  return a;
 }

 public static void
 main( String[] args ) {
  mygcd(A, B);
 }
}



class EuclideanRecursion {
 static final int A = 1071;
 static final int B = 1029;

 public static int
 mygcd( int a, int b ) {
  if ( b == 0 ) {
   return a;
  } else {
   return mygcd( b, a%b );
  }
 }


 public static void
 main( String[] args ) {
  mygcd(A, B);
 }
}


class EuclideanOriginal {
 static final int A = 1071;
 static final int B = 1029;

 public static int
 mygcd( int a, int b ) {
  while ( b != 0 ) {
   if ( a > b ) {
    a = a-b;
   } else {
    b = b-a;
   }
  }
   return a;
 }


 public static void
 main( String[] args ) {
  mygcd(A, B);
 }
}

#!/usr/local/bin/python

def mygcd(a, b):
    while b != 0:
        t = b
        b = a % b
        a = t
    return a


mygcd( 1071, 1029 )
#!/usr/local/bin/python

def mygcd( a, b ):
    if b == 0:
        return a
    else:
        return mygcd( b, a %b )


mygcd( 1071, 1029 )
#!/usr/local/bin/python

def mygcd( a, b ):
    while b != 0:
        if a > b:
            a = a-b
        else:
            b = b-a
    return a


mygcd( 1071, 1029 )