Python

Wasting time with the Euclidean Algorithm

by

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

I’m very tempted to try and put Python + QT to work. A good reference should be able to deal with the diffrences between the C Standard library and what Python offers. I know KPorts is available as a crazy PBI for PC-BSD to give people a gui frontend for ports/packages but. While it gets the job done it’s too darn crashy !

If I could manage to do it (would be learning my first toolkit), a frontend thats got full support for portupgrade and portaduit, strong searching and is reliable + configurable is nice. Functionality, Ease of Use, something thats easy for a newbie but powerful enough to be a professionals tool. Maybe add support for pkgsrc or emerge and stuff in the future. I dunno if I could with how much I know about programming now but there’s always the future.

If I did it I’d want to try and keep things tidy, like so:

Implement code to manage ports

Create a graphical interface using QT

Trim things to allow a great deal of seperation between functional code and user interaction so that it’d be possible to have diffrent GUI’s but not have to rewrite all of or edit most of the code that actually does the job.

Snakes and Rivers

by

Starting to learn about python, I’ve always hated python for as much as I’ve seen of it. I’m the kinda guy that likes C/C++, not because of the syntax and loaths Java because I feel it’s to much typing. C/C++ has a very logical style imho. I’m used to stuff like this:

void someFunction(some, params)
{
      int somevar = 1;
      int comvar = 3;
      char anothervar = "something";
      if (somevar < comvar) {
            cout << anothervar;
      }
}

Python feels more like it’d be some thing like: 

def someFunction(some, params):
      """About this function"""
      somevar = 1;
      comvar = 3;
      anothervar = "something";
      if somevar < comvar:
            printf anothervar

So far it’s interesting, never really done much for Object Oriented Programming ether. Well inless you count reading allot of Java a long time back but never writting much.
While I can’t remember why I got into programming, I remember I chose to start off with C++ because I knew it was common and I could find allot, also I found it interesting. Java I’ve read but not written, plenty of reading both about the language and the syntax but I’ve only written like a hello world app. The way I go by how much typing is involved is the Hello world program most tutorials start with. Example / Opinions: 

/* ANSI C */

#include <stdio.h>

int main()
{
    printf("Hello, World!n");
    return 0;
}

// My very first C++ program
#include <iostream>
using namespace std;

int main ()
{
    cout << "Hello World!";
    cin.get();
    return 0;
}

//Simple Hello World program in Java

class HelloJava {
        public static void main(String[] args) {
                System.out.println("Hello Java!");
        }
}

#!/usr/bin/perl
use warnings;

print "Hello, world.n";

#in python
print "Hello, World!"

As you can see, Python was the least involved to print one line of text to standard output. Perl wasn’t so bad, like a shell script + I always use, use warnings with perl. Java doesn’t look bad but 2,000 lines later I think my fingers would wear out. C++ is ok but a bit of prep work, C on the other hand is slightly less. While I reckon doing things in a language is always typing intensive up to a point, how much nitty-typing you need to do some thing short is the Q. Odds are in my book Java is probably better to learn first but C is easier to have to type out things. I must say I do like to hear of app’s done in Java, I can even read it reasonably like a few other languages but I don’t like to use it. I think I’m going to like Python, basically after I started with C++ I got board and switched to Perl learned enough to be able to grasp a few basics (and read it better) then got board. Whent back to C++ studies and started reading about Java. Got tired of C++ and didn’t care for writting Java. Forgot allot of crap from no use, got back into it and tried to learn more about C. Fell inlove with it the second I saw this guide it’s good for learning basic concepts and this guys got a nice sense of humor. I found it useful if not perfect but it did renew my interest in programming. Since then I’ve been playing with C and generally enjoying it.