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.