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.

This entry was posted in Math and tagged , , . Bookmark the permalink. Post a comment or leave a trackback: Trackback URL.

4 Comments

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

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

    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.

Post a Comment

Your email is never published nor shared. Required fields are marked *

*
*