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){Recursion
int temp;
while(small!=0){
temp = big%small;
big=small;
small=temp;
}
return big;
}
int recursionGCD(int big,int small){i tested around that both method for 5 times and record down the time used to process.
if(small==0){
return big;
}
return recursionGCD(small,big%small);
}
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.
No comments:
Post a Comment