Logo

Programming-Idioms

  • D
  • Fortran

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.

use,intrinsic : iso_fortran_env, only : int64
function gcd(m,n) result(answer)
implicit none
integer(kind=int64),intent(in)  :: m, n
integer(kind=int64)             :: answer,irest,ifirst
   ifirst=iabs(m)
   answer=iabs(n)
   if(answer.eq.0)then
      answer=ifirst
   else
      do
         irest = mod(ifirst,answer)
         if(irest == 0)  exit
         ifirst = answer
         answer = irest
      enddo
      answer= iabs(answer)
   endif
end function gcd
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)
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.
#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