Click here to Skip to main content
Click here to Skip to main content
Alternative Tip/Trick

Fast Greatest Common Divisor (GCD) Algorithm

, 11 Feb 2011 CPOL
Rate this:
Please Sign up or sign in to vote.
Can we simplify it by: (This essentially passes only two numbers). public int GCD(int value1, int value2){ int max = 0; bool gcdFound = false; int counter = 1; //Make sure both numbers are atleast 2 or above if (( value1 <= 1 ) || (value2 <= 1)) return...
Can we simplify it by: (This essentially passes only two numbers).
 
public int GCD(int value1, int value2)
{
 
    int max = 0;
    bool gcdFound = false;
    int counter = 1;
 
    //Make sure both numbers are atleast 2 or above
    if (( value1 <= 1 ) || (value2 <= 1))
        return (value1 < value2 ? value1 : value2);
 
    //If one of the two numbers is the exact divisor of then other or are equal to each other then we return that number here.
    gcdFound = (((value1 % value2 ) == 0 ) || ((value2 % value1 ) == 0 ));
    if (gcdFound)
    {
        return (value1 > value2 ? value2 : value1);
    }
 
    //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);
    }
 
    return counter;
}

License

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

Share

About the Author

ZamirF

United States United States
No Biography provided

Comments and Discussions

 
GeneralAs I've already mentioned: DO NOT USE THIS ALTERNATE ALGORIT... PinmemberDrABELL22-Feb-11 16:00 
GeneralReason for my vote of 5 It works. PinmemberKamran Behzad22-Feb-11 14:08 

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
Web04 | 2.8.141022.2 | Last Updated 11 Feb 2011
Article Copyright 2011 by ZamirF
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid