Logo

Programming-Idioms

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

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.

gcd a b
    |   a==b =a
    |   a>b = gcd(a-b) b
    |   otherwise = gcd a (b-a)
x = gcd a b

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);
(defn gcd [a b]
  (if (zero? b)
    a
    (recur b (mod a b))))
unsigned long long int GCD(unsigned long long int a, unsigned long long int b)
{
    unsigned long long int c=a%b;
    if(c==0)
        return b;
    return GCD(b, c);
}
#include <cstdint>
#include <functional>
using namespace std;
using u64 = uint64_t;
function<u64(u64, u64)> gcd;
gcd = [&gcd] (u64 a, u64 b) {
    return !b ? a : gcd(b, a % b);
};
auto x {gcd(a, b)};
#include <numeric>
auto x = std::gcd(a, b);
int gcd(int a, int b)
{
  while (b != 0)
  {
    int t = b;
    b = a % t;
    a = t;
  }
  return a;
}
int gcd(int a, int b)
{
  if (b == 0) 
    return a;
  else 
    return gcd(b, a % b);
}
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);
import std.numeric: gcd;
x = gcd(a, b);
int gcd(int a, int b) {
  while (b != 0) {
    var t = b;
    b = a % t;
    a = t;
  }
  return a;
}
x = a.gcd(b);
defmodule Gcd do
  def gcd(x, 0), do: x
  def gcd(x, y), do: gcd(y, rem(x,y))
end

x = Gcd.gcd(a, b)
x = Integer.gcd(a, b)
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 "math/big"
x.GCD(nil, nil, a, b)
const gcd = (a, b) => b === 0 ? a : gcd (b, a % b)
import java.math.BigInteger;
BigInteger x = a.gcd(b);
(setf x (gcd a b))
function gcd(x, y)
	if (y == 0) then
		return x
	else 
		return gcd(y, x%y)
	end
end
function gcd(a, b)
	return b==0 and a or gcd(b,a%b)
end
extension=gmp
$x = gmp_gcd($a, $b);
function GCD(a,b:int64):int64;

var t:int64;

begin
  while b <> 0 do
    begin
       t := b;
       b := a mod b;
       a := t;
    end;
    result := a;
end;

use bigint;
sub gcd {
    my ($A, $B) = @_;
    return 0 == $B
        ? $A
        : gcd($B, $A % $B);
}

import math
x = math.gcd(a, b)
from fractions import gcd
x = gcd(a, b)
def gcd(a, b, *args):
    def f(a, b):
        while b:
            a, b = b, a % b
        return a
    if not args:
        return f(a, b)
    else:
        return gcd(f(a, b), *args)
x = gcd(a, b)
from functools import reduce
from math import gcd
x = reduce(gcd, (a, b))
x = a.gcd(b)
extern crate num;

use num::Integer;
use num::bigint::BigInt;
let x = a.gcd(&b);
Imports System.Numerics
Dim x = BigInteger.GreatestCommonDivisor(a, b)
New implementation...
< > ⌨
deleplace 
gcd a b
    |   a==b =a
    |   a>b = gcd(a-b) b
    |   otherwise = gcd a (b-a)
x = gcd a b

gcd x y =  gcd' (abs x) (abs y)
	where
	gcd' a 0  =  a
	gcd' a b  =  gcd' b (a `rem` b)
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);
(defn gcd [a b]
  (if (zero? b)
    a
    (recur b (mod a b))))
unsigned long long int GCD(unsigned long long int a, unsigned long long int b)
{
    unsigned long long int c=a%b;
    if(c==0)
        return b;
    return GCD(b, c);
}
using namespace std;
using u64 = uint64_t;
function<u64(u64, u64)> gcd;
gcd = [&gcd] (u64 a, u64 b) {
    return !b ? a : gcd(b, a % b);
};
auto x {gcd(a, b)};
auto x = std::gcd(a, b);
int gcd(int a, int b)
{
  while (b != 0)
  {
    int t = b;
    b = a % t;
    a = t;
  }
  return a;
}
int gcd(int a, int b)
{
  if (b == 0) 
    return a;
  else 
    return gcd(b, a % b);
}
BigInt gcd(in BigInt x, in BigInt y) pure {
    if (y == 0)
        return x;
    return gcd(y, x%y);
}

gcd(a, b);
x = gcd(a, b);
int gcd(int a, int b) {
  while (b != 0) {
    var t = b;
    b = a % t;
    a = t;
  }
  return a;
}
x = a.gcd(b);
defmodule Gcd do
  def gcd(x, 0), do: x
  def gcd(x, y), do: gcd(y, rem(x,y))
end

x = Gcd.gcd(a, b)
x = Integer.gcd(a, b)
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

x.GCD(nil, nil, a, b)
const gcd = (a, b) => b === 0 ? a : gcd (b, a % b)
BigInteger x = a.gcd(b);
(setf x (gcd a b))
function gcd(x, y)
	if (y == 0) then
		return x
	else 
		return gcd(y, x%y)
	end
end
function gcd(a, b)
	return b==0 and a or gcd(b,a%b)
end
$x = gmp_gcd($a, $b);
function GCD(a,b:int64):int64;

var t:int64;

begin
  while b <> 0 do
    begin
       t := b;
       b := a mod b;
       a := t;
    end;
    result := a;
end;

sub gcd {
    my ($A, $B) = @_;
    return 0 == $B
        ? $A
        : gcd($B, $A % $B);
}

x = math.gcd(a, b)
x = gcd(a, b)
def gcd(a, b, *args):
    def f(a, b):
        while b:
            a, b = b, a % b
        return a
    if not args:
        return f(a, b)
    else:
        return gcd(f(a, b), *args)
x = gcd(a, b)
x = reduce(gcd, (a, b))
x = a.gcd(b)
let x = a.gcd(&b);
Dim x = BigInteger.GreatestCommonDivisor(a, b)