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 )