trace(gcf(75,145));
// outputs 5
function gcf(a:int, b:int):int{
var remainder:int;
var factor:Number = 0;
while (1){
if (b > a){
var swap:int = a;
a = b;
b = swap;
}
remainder = a % b;
a = b;
b = remainder
if (remainder == 0){
factor = a;
break;
}else if (remainder==1){
break;
}
}
return factor;
}
I was messing around with Egyptian Fractions and found myself in need of some interesting functions. The first function I realized I would be needing was for a greatest common factor (GCF or GCD).
The above snippet is a quick implementation of Euclid’s algorithm. It will return 0 if no GCF is found…
I wrote a few helper functions while working with Egyptian fractions… will post them over the next few days.
cool. just a tip for swapping variables without the temporary one (i suppose it’s faster aswell):
a ^= b;
b ^= a;
a ^= b;
or
a = a + b;
b = a – b;
a = a – b;
thanks for the comment simon… yeah… I’m aware of those, posted about them awhile back:
https://actionsnippet.com/?p=619
I’m pretty sure most compilers are optimized to be fastest with the simple variable swap method (used in this snippet)… I know that’s the case with C++ gcc… I did a test awhile back in actionscript and found that the normal variable swap is actually fastest method (at least in the scenarios I was using it in).
I had to know for sure, so wrote this little test to see which is fastest. The conclusion is that there’s just about no difference. Add/subtract and bitwise swaps seem slightly (very slightly) faster than the variable method. But the difference is so small that it would be of no importance in a real life situation, and could probably change (to variable swap bein the fastest) based on different systems and players.
Anyway, heres the results i got for 10 million iterations:
Variable swap: 2141
Bitwise swap: 2065
Add/subtract swap: 2083
And i put the test script up here (correct me if I made errors) 🙂
http://simon.altschuler.dk/test/swap/Main.txt
Regards,
Simon
Have a look at this article about the topic: http://en.wikipedia.org/wiki/XOR_swap_algorithm
I think the xor thing is cool, but as mentioned in my previous post… i like the simple readable code of the standard variable swap.