Logo

Programming-Idioms

  • PHP
  • C++

Idiom #74 Compute GCD

Compute the greatest common divisor x of big integers a and b. Use an integer type able to handle huge numbers.

unsigned long long int GCD(unsigned long long int a, unsigned long long int b)
{
    unsigned long long int c=a%b;
    if(c==0)
        return b;
    return GCD(b, c);
}

This implementation is the cleanest I know, but it is not meant for negative integers.
#include <numeric>
auto x = std::gcd(a, b);

C++17 or later

Uses the absolute values of a and b in calculations
extension=gmp
$x = gmp_gcd($a, $b);

both $a and $b must be instances of the GMP class
#include <gmp.h>
mpz_t _a, _b, _x;
mpz_init_set_str(_a, "123456789", 10);
mpz_init_set_str(_b, "987654321", 10);
mpz_init(_x);

mpz_gcd(_x, _a, _b);
gmp_printf("%Zd\n", _x);

New implementation...
< >
deleplace