Greatest Common Divisor (GCD) of Big Numbers – A Recursive Approach (C++)

In this post I will provide mathematical background and C++ implementation of greatest common divisor (GCD) calculation of big numbers problem. Problem can be described as:

You have two numbers to calculate their GCD. First number is very big, let say 250 digits long. Other number is not so long, maybe less than 6 digits. How  do you calculate GCD of these two numbers.

We’ll use Euclidean Algorithm in this solution. Below is the Euclidean Algorithm shortly:

Formal description of the Euclidean algorithm

• Input Two positive integers, a and b.
• Output The greatest common divisor, g, of a and b.
• Internal computation
  1. If a<b, exchange a and b.
  2. Divide a by b and get the remainder, r. If r=0, report b as the GCD of a and b.
  3. Replace a by b and replace b by r. Return to the previous step.

Ok, this works with regular integers, but 250 digits long integer’s modulus is not possible with standart C, C++. And in fact you can not have 250 digits long integer at all, you must save these number in string (C++) or char array (C, C++).

So program becomes string represented data and regular integer modulus.

Let’s say big number is: “1234567890987654321” and other number is 10. How can we calculate GCD these two number.

Remember from modulus calculation:

A = p (mod n)

means “A” equals “p” in mod “n”. For example:

13 = 3 (mod 10)

Modulus arithmetic have following characteristics.

Addition property:

A = p (mod n)

B = k (mod n)

then A + B = p + k (mod n)

Multiplication property:

A = p (mod n)

B = k (mod n)

A * B = p * k (mod n)

Having these properties we’ll apply divide and conquer solution to this problem. We’ll start from right “d” digits that fits into integer range (for example 5 digit) and make calculation as follows.

let say A = "1234567890987654321" and n = 10

A = x (mod n) which is:

"1234567890987654321" = x (mod 10)

we’ll calculate x.

let say we’ll process 5 digits of big number at a time (d = 5). So below equation is hold.

A = "1234567890987654321" = "12345678900987600000" + "54321"

Further:

"1234567890987600000" = "12345678909876" * 100000

So we can write A as:

A = "12345678909876" * 100000 + "54321"

Remember Addition and Multiplication Properties of modulus. We can further write these equation as:

A mod 10 = ("12345678909876" mod 10) * (100000 mod 10) + (54321 mod 10)

Now (100000 mod 10), and (54321 mod 10) can be calculated easily now, and we can write their equivalents now as below:

A mod 10 = ("12345678909876" mod 10) * 0 + 1

As it can easily seen multiplication with 0 gives zero and result will be 1 but we’ll go further for the demonstration of other possibilities.

Now we need to calculate modulus of “12345678909876”. Similar steps occur. Let say B = “12345678909876”

B mod 10 = ("12345678909876" mod 10 ) = ("12345678900000" mod 10) + (09876 mod 10), further

B mod 10 = ("123456789" mod 10) * (100000 mod 10) + (09876 mod 10)

now B can be rewritten as:

B mod 10 = ("123456789" mod 10) * 0 + 6

Bigger picture can be rewritten as:

A = "1234567890987654321" mod 10 = (("123456789" mod 10) * 0 + 6) * 0 + 1)

I think this is enough for the procedure. Recursively we’ll get 5 digits from big number and write their equivalents for the modulus. Termination criteria for the recursion is the digit count of the big number. In my implementation if bignumber’s digit is less than 6 it returns directly its modulus, as it can fit into integer range and can be calculated.

Code is given below:

// Hayati Gonultas
// CopyLeft
#include <iostream>
#include <string>
#include <sstream>

using namespace std;

unsigned int bigmodulus(string bignumber, int m) {
    static const int modulus_multiply_e6 = 100000 % m;

    if (bignumber.length() <= 5) {
        int currNumber;
        stringstream(bignumber) >> currNumber;

        return (currNumber % m);
    }

    string rightFiveDigit = bignumber.substr(bignumber.length()-5, 5);

    bignumber = bignumber.substr(0, bignumber.length()-5);

    int remainder;
    stringstream(rightFiveDigit) >> remainder;
    int modulusRemainder = remainder % m;

    return (bigmodulus(bignumber, m)*modulus_multiply_e6 + modulusRemainder) % m;
}

int gcd(int n1, int n2);

int gcd(string bignumber, int othernumber) {
    int m = bigmodulus(bignumber, othernumber);

    if (m == 0)
        return othernumber;

    return gcd(othernumber, m);
}

int gcd(int n1, int n2) {
    if (n1 < n2) {
        int temp = n1;
        n1 = n2;
        n2 = n1;
    }

    if (n1 % n2 == 0)
        return n2;
    else
        n1 = n1 % n2;

    return gcd(n2, n1);
}

int main ()
{
    string bignumber = "1234567890987654321";

    cout << gcd(bignumber, 3) << endl;

    return 0;
}