# Greatest Common Factor (divisor)

Actionscript:
1. trace(gcf(75,145));
2.
3. // outputs 5
4.
5. function gcf(a:int, b:int):int{
6.     var remainder:int;
7.     var factor:Number = 0;
8.     while (1){
9.         if (b> a){
10.            var swap:int = a;
11.            a = b;
12.            b = swap;
13.         }
14.         remainder = a % b;
15.         a = b;
16.         b = remainder
17.         if (remainder == 0){
18.             factor = a;
19.             break;
20.         }else if (remainder==1){
21.
22.             break;
23.         }
24.     }
25.     return factor;
26. }

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.

1. Simon Altschuler
Posted November 28, 2009 at 11:41 am | Permalink

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;

2. Zevan
Posted November 28, 2009 at 11:54 pm | Permalink

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).

3. Simon Altschuler
Posted November 29, 2009 at 6:12 am | Permalink

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

And i put the test script up here (correct me if I made errors) http://simon.altschuler.dk/test/swap/Main.txt

Regards,
Simon

4. Zevan
Posted November 29, 2009 at 10:37 am | Permalink