Actionscript:
-
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.
4 Comments
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:
http://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.