Logo

Programming-Idioms

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

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.

x = gcd a b
gcd a b
    |   a==b =a
    |   a>b = gcd(a-b) b
    |   otherwise = gcd a (b-a)
gcd x y =  gcd' (abs x) (abs y)
	where
	gcd' a 0  =  a
	gcd' a b  =  gcd' b (a `rem` b)
#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