Improving the GCD algorithm

**deathslice** · 05-07-2015

So the exercise that I'm doing now in the book is to find the GCD for two integers. The solution seems to be working very well for both small and large integers(up to a million or more is how far I've tested) and I was wondering if someone could take a gander at my code and give me some feedback on how I could make this better.

Code:

#include <stdio.h>
#include <stdbool.h>


int main()
{
    int m, n, remainder;    bool isPrimeNum1 = true, isPrimeNum2 = true;
    int d;


    printf("Enter two integers. ");
    scanf("%d %d", &m, &n);


    // Check to see if we already have the gcd by checking if one of the integers is zero.
    // The integer that is not zero is the gcd.
    if(m == 0)
    {
        gcd = n;
    }
    else
        gcd = m;


    // Check to see if the first number is prime.
    for(d = 2; d * d < m; d++)
    {
        if(m % d == 0)
        {
            isPrimeNum1 = false;
            break;
        }
    }


    // If the first number is not prime, check to see if the next number is prime.
    if(!isPrimeNum1)
    {
        for(d = 2; d * d < n; d++)
        {
            if(n % d == 0)
            {
                isPrimeNum2 = false;
                break;
            }
        }
    }


    // If either one them is prime, check to see if the gcd is either the prime number itself or 1.
    if(isPrimeNum1 || isPrimeNum2)
    {
        if(n % m == 0)
        {
            gcd = m;
        }
        else if(m % n == 0)
        {
            gcd = n;
        }
        else
        {
            gcd = 1;
        }
    }


    // Find the GCD by dividing the larger number with the smaller number and dividing the next larger number by the remainder.
    // Repeat the step until you get a remainder of zero


    while (n != 0)
    {
       remainder = m % n;
       m = n;
       n = remainder;
    }


    printf("The greatest common divisor is: %d", m);

    return 0;
}

**deathslice** · 05-07-2015

Final edit.

Code:

#include <stdio.h>
#include <stdbool.h>


int main()
{
   int m, n, gcd, remainder;    
   bool isPrimeNum1 = true, isPrimeNum2 = true;
   int d;


    printf("Enter two integers. ");
    scanf("%d %d", &m, &n);


    // Check to see if we already have the gcd by checking if one of the integers is zero.
    // The integer that is not zero is the gcd.
    if(m == 0)
    {
        gcd = n;
        printf("The greatest common divisor is: %d", gcd);
        return 0;
    }
    else
    {
        gcd = m;
        printf("The greatest common divisor is: %d", gcd);
        return 0;
    }


    // Check to see if the first number is prime.
    for(d = 2; d * d < m; d++)
    {
        if(m % d == 0)
        {
            isPrimeNum1 = false;
            break;
        }
    }


    // If the first number is not prime, check to see if the next number is prime.
    if(!isPrimeNum1)
    {
        for(d = 2; d * d < n; d++)
        {
            if(n % d == 0)
            {
                isPrimeNum2 = false;
                break;
            }
        }
    }


    // If either one them is prime, check to see if the gcd is either the prime number itself or 1.
    if(isPrimeNum1 || isPrimeNum2)
    {
        if(n % m == 0)
        {
            gcd = m;
            printf("The greatest common divisor is: %d", gcd);
            return 0;
        }
        else if(m % n == 0)
        {
            gcd = n;
            printf("The greatest common divisor is: %d", gcd);
            return 0;
        }
        else
        {
            gcd = 1;
            printf("The greatest common divisor is: %d", gcd);
            return 0;
        }
    }


    // If we get to this part, then we must find the GCD by dividing the larger number with the smaller number 
    // and dividing the next larger number by the remainder.
    // Repeat the step until you get a remainder of zero


    while(1)
    {
        remainder = m % n;
        m = n;
        n = remainder;


        if(n == 0)
        {
            gcd = m;
            break;
        }
    }


    printf("The greatest common divisor is: %d", gcd);


    return 0;
}

**rcgldr** · 05-07-2015

Why bother checking for prime numbers, the GCD algorithm will converge on the answer fairly quickly. The worst case scenario occurs when the two numbers are successive Fibonacci numbers. For 64 bit unsigned integers, m = 12200160415121876738 and n = 7540113804746346429 will take 91 loops (gcd == 1). For 32 bit unsigned integers, m = 2971215073 and n = 1836311903 will take 45 loops (gcd == 1). Note that 12200160415121876738 = 2×557×2417×4531100550901, and it would a take a while to find all of it's prime factors.

**Nominal Animal** · 05-08-2015

Very good point, rcgldr.

Going a bit into detail, there is a huge practical advantage by working with nonnegative numbers, and applying Euclid's algorithm in elementary terms -- you then only need some comparisons and one subtraction per iteration; no division or modulus needed at all. Of course, if one or both of your terms is negative, you only need to take their absolute value. (If the original values had the same sign, all common divisors are positive anyway. Otherwise, it depends on how you define the sign for the divisors.)

Because subtraction is fast compared to division or modulus, this means that each iteration will be fast. On an Intel Core i5-4200U, we're talking about 3 clock cycles per iteration, median.

The Wikipedia article linked to above does not contain the pseudocode for this case (Euclid's algorithm in elementary terms), but it is pretty much just

Code:

Let num1 be first nonnegative term (i.e. negate if negative)
Let num2 be second nonnegative term (i.e. negate if negative)

if num1 or num2 is less than one,
    the greatest common divisor is zero

while num1 and num2 are both larger than 0:
    if num1 is larger than num2,
        num1 = num1 - num2
    else
    if num2 is larger than num1
        num2 = num2 - num1
    else
        the greatest common divisor is num1 == num2.

if num1 == 0:
    the greatest common divisor is num2
else
    the greatest common divisor is num1

Whether the binary GCD algorithm (which replaces the divisions in Euclid's algorithm with bit shifts) is faster, is an open question. Current Intel/AMD CPUs are superscalar, pipelined beasts, that do all sorts of funky stuff, which means that something you think is faster may very well not be so.

I did test gcd(12200160415121876738,7540113804746346429) using both approaches, and on my i5-4200U, the elementary approach takes about 190 cycles, median, whereas the binary GCD approach takes about 267 cycles, median. So, for this particular pair the elementary approach is faster.

I'm too lazy to check any other number pairs, so I don't want to say anything about which one is faster, but I definitely like the simplicity of the elementary approach I pseudocoded above.

Which segways nicely to the original topic: Improving the GCD algorithm. The two to three hundred clock cycles is what a few (less than a dozen) integer division or modulus operations take on this CPU, so the speed is certainly fast enough to use either one. (If you had some scientific problem you used this in solving in, and really needed the absolute fastest approach, I'd keep both, and add some magic to my Makefile to build and test them at compile time, and pick the faster one for that CPU, as a final finessing touch.)

So, to me, improvement would refer at least as much to making the code robust, maintainable, easy to read, and documented, as it would be to speed. And that is why rcgldr's post is so good: it is short, easy to understand, and pushes you towards improvement no matter whether you put the emphasis on speed or robustness/readability/maintainability. I like that.

**deathslice** · 05-08-2015

Thanks for your suggestions.

Thread: Improving the GCD algorithm

Thread Tools

Search Thread

Display

Improving the GCD algorithm

Similar Threads

help improving code

Help on Improving

Improving penmanship

Improving C++ graphics

Tags for this Thread