Wednesday, October 10, 2012

Euclid's Algorithm

I was trying around with some algorithm in order for me to get familiar with it.
First started with Euclid's Algorithm.
Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers, also known as the greatest common factor (GCF) or highest common factor (HCF). (quoted from Wikipedia)
I tried with 2 method to implement it in a function, first with looping and second with recursion.

Loop
 int loopGCD(int big, int small){

    int temp;

    while(small!=0){
        temp = big%small;
        big=small;
        small=temp;
    }
    return big;
}
 Recursion
 int recursionGCD(int big,int small){
    if(small==0){
        return big;
    }
    return recursionGCD(small,big%small);
}
i tested around that both method for 5 times and record down the time used to process.

First test case with GCD for 252 and 105 (repeated 10 million times to record the time)

No loop recursion
1 0.484 0.447
2 0.484 0.475
3 0.48 0.457
4 0.488 0.458
5 0.494 0.452
Average 0.486 0.4578

Second test case with GCD for 163231 and 152057 (repeated 10 million times to record the time)


No loop recursion
1 1.249 1.051
2 1.233 1.246
3 1.227 1.048
4 1.222 1.02
5 1.292 1.041
Average 1.2446 1.0812

Conclusion that i get is recursion way is faster than looping. The coding in recursion also much simpler.
Perhaps there are better way to code both method and this is open to discussion.
I believe there are still many room for me to improve.