Logo

Programming-Idioms

This language bar is your friend. Select your favorite languages!
  • D

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.

import std.bigint;
BigInt gcd(in BigInt x, in BigInt y) pure {
    if (y == 0)
        return x;
    return gcd(y, x%y);
}

gcd(a, b);

As this time, std.numeric.gcd doesn't work with BigInts. Here is a non-optimal but working implementation.
import std.numeric: gcd;
x = gcd(a, b);

This is the standard way to compute gcd, however it doesn't work with std.bigints right now (https://issues.dlang.org/show_bug.cgi?id=7102)
#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