Logo

Programming-Idioms

  • Go
  • Java
  • 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.

#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);
import "math/big"
x.GCD(nil, nil, a, b)

The first two arguments can be ignored in this use case.

x, a, b have pointer type *big.Int .
import java.math.BigInteger;
BigInteger x = a.gcd(b);
(defn gcd [a b]
  (if (zero? b)
    a
    (recur b (mod a b))))

New implementation...
< >
deleplace