# 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 Totaliteration 2 1 3 2 2 10recursion 3 2 2 1 1 9original 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 1029intmygcd( int a, int b ) { int t = 0; while ( b != 0 ) {  t = b;  b = a % b;  a = t; } return a;}intmain(void) { mygcd(A, B); return 0;}#include <stdio.h>#define A 1071#define B 1029intmygcd( int a, int b ) { if ( b == 0 ) {  return a; } else {  return mygcd( b, a%b ); }}intmain(void) { mygcd(A, B); return 0;}#include <stdio.h>#define A 1071#define B 1029intmygcd( int a, int b ) { while ( b != 0 ) {  if ( a > b ) {   a = a-b;  } else {   b = b-a;  } }  return a;}intmain(void) { mygcd(A, B); return 0;}#!/usr/local/bin/ruby -wdef gcd(a, b)  while b != 0    t = b    b = a % b    a = t  end  return agcd( 1071, 1029 )#!/usr/local/bin/ruby -wdef gcd(a,b)  if b == 0    return a  else    return gcd(b, a % b )  endendgcd( 1071, 1029 )#!/usr/local/bin/ruby -wdef gcd( a, b )  while b != 0    if a > b      a = a - b    else      b = b - a    end  end  return aendgcd( 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/pythondef mygcd(a, b):    while b != 0:        t = b        b = a % b        a = t    return amygcd( 1071, 1029 )#!/usr/local/bin/pythondef mygcd( a, b ):    if b == 0:        return a    else:        return mygcd( b, a %b )mygcd( 1071, 1029 )#!/usr/local/bin/pythondef mygcd( a, b ):    while b != 0:        if a > b:            a = a-b        else:            b = b-a    return amygcd( 1071, 1029 )`