Click here to Skip to main content
14,734,150 members
Articles » Languages » C# » General
Alternative
Tip/Trick
Posted 11 Feb 2011

Tagged as

Stats

20K views
2 bookmarked

Fast Greatest Common Divisor (GCD) Algorithm

Rate me:
Please Sign up or sign in to vote.
5.00/5 (2 votes)
15 Feb 2011CPOL
The computational efficiency of the Euclid's algorithm is much higher that the alternatives

I would not recommend the Alternate 2 method for the following reasons:

1. First and foremost, the computational efficiency of the Euclid's algorithm at the core of my solution (see the following - ORIGINAL, RECOMMENDED) is significantly higher than of that simple iterations (essentially looping from the smaller half downward and checking divisibility of both variables) implemented in proposed alternative 1 (see the following):

// fast Euclid GCD algorithm for 2 integers: RECOMMENDED
      if (list.Length == 2)
      {
          Int64 a = list[0];
          Int64 b = list[1];
          while (b != 0)
          {
              GCD = b;
              b = a % b;
              a = GCD;
          }
          return GCD;

FYI: As per general theory, Euclidean algorithm should not take more steps to complete than 5 times the number of digits (base10) of the smallest number. Even more efficient algorithms than this classic, Euclidean one exist, but they are correspondingly, much more complex.
 

Note: FOLLOWING ALGORITHM (RE: Alternate 2) IS NOT RECOMMENDED DUE TO LOW EFFICIENCY

    //Find the larger of the two numbers, the GCD can not be more than half of the smaller number.
    max =  value1 > value2 ? (value2 / 2) : (value1 / 2);
    counter = max + 1;
 
    while ((!gcdFound) && (counter > 1))
    {
        counter--;
        gcdFound = ((value1 % counter) == 0) && ((value2 % counter) == 0);
    }

 

2. Passing array and corresponding array operations, implemented in my original algorithm, are essential for extending it to more than just two input variables. There is no need to re-write my function, because it could be simply overloaded for just 2 variables (just add the second function, taking 2 parameters and calling the original one), or the same result could be achieved by simply passing the 2 variables value1 and value2 like in example shown below:

Int64 _gcd = GCD(new Int64[] {value1, value2 });


Hope I've answered the question.

Kind Regards,
Alexander Bell

 

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

DrABELL
Founder Infosoft International Inc
United States United States
Dr. Alexander Bell is a seasoned full-stack Software Engineer (Win/Web/Mobile). He holds PhD in Electrical and Computer Engineering, authored 37 inventions and published 300+ technical articles. Currently focused on multiple Android/Mobile development projects and Big Data' Machine Learning, AI, IoT. Alex participated in App Innovation Contests (AIC 2102/2013) with multiple winning submissions. Portfolio samples:

  1. Educational Web Portal
  2. NY Payroll Tax Calculator (#1 on Goog)
  3. Android Fraction Calculator "Fractal MK-12"
  4. Android Prime Factorization Calculator 18-digit)
  5. Semafon™ semantic phone num-to-text converter
  6. Real-time NY Bus Tracking Web App (IoT)
  7. WebTV powered by YouTube .NET API (#1 on Goog)
  8. Engineering Calculator VOLTA
  9. Big Data: Facebook and YouTube
  10. NY City Trivia Quiz
  11. Publications by A. Bell

Comments and Discussions

 
GeneralThanks, Sandeep! Best regards/wishes, Alex Pin
DrABELL12-Feb-11 5:12
professionalDrABELL12-Feb-11 5:12 
GeneralReason for my vote of 5 Deserves a 5 for detailed explanat... Pin
Sandeep Mewara11-Feb-11 21:58
mvaSandeep Mewara11-Feb-11 21:58 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.