Programming-Idioms

Edit summary for version 9 by :

↷

2015-08-25, 21:06:54

2015-08-25, 21:17:11

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.

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.

http://rosettacode.org/wiki/Greatest_common_divisor#D

Next change ↷