Click here to Skip to main content
Click here to Skip to main content
Alternative Tip
Go to top

Fast Greatest Common Divisor (GCD) Algorithm

, 15 Feb 2011
Rate this:
Please Sign up or sign in to vote.
Hi, everybodyAfter thorough consideration, 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 function(see the following - ORIGINAL, RECOMMENDED): // fast Euclid...
Hi, everybody
 
After thorough consideration, 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 function(see the following - ORIGINAL, RECOMMENDED):
          // 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;
 
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):
 
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);
    }
 


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.


 
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
President Infosoft International Inc
United States United States
Dr. A. Bell has 20+ years of Software and Electrical Engineering experience. He is Win/Web veteran, published 200+ articles and authored 37 inventions, currently focused on: Windows 7/8, HTML5, CSS3, jQuery, SQL, .NET, ASP.NET, WPF, C#, Speech Technology and Mobile apps. He's been among recent App submission winners (The Windows 8* & Ultrabook™ App Innovation Contest 2012). Sample pubs:
  1. Edumatter M12: School Math Calculators and Equation Solvers (contest winner)
  2. Engineering Calculator VOLTA-2013 (contest winner)
  3. HTML5 Best Practices: Table formatting via CSS3
  4. Edumatter-M12 for Windows, app overview
  5. Engineering Calculator VOLTA-814D
  6. CoolPhone: phone numbers-to-text converter
  7. SQL generates large data sequence
  8. Aggregate Product function extends SQL
  9. Top-50 Digital Cameras
  10. WebTV Project: Embedded YouTube Player (Goog #1 YouTube API for ASP.NET)
Dr. Bell is personally credited for 10+ Enterprise level projects (Finance/Investment, Engineering, Edu) w/total code base exceeding 250k lines; doing consulting in NYC for 20 yrs.
Follow on   Twitter

Comments and Discussions

 
GeneralThanks, Sandeep! Best regards/wishes, Alex PinmemberDrABELL12-Feb-11 4:12 
GeneralReason for my vote of 5 Deserves a 5 for detailed explanat... PinmvpSandeep Mewara11-Feb-11 20:58 
Reason for my vote of 5
Deserves a 5 for detailed explanation!

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

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

| Advertise | Privacy | Mobile
Web03 | 2.8.140921.1 | Last Updated 15 Feb 2011
Article Copyright 2011 by DrABELL
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid