Editing Idiom 74 : Compute GCD

Idiom

# 74 Compute GCD

Created by

Lead paragraph

Compute the greatest common divisor _x of big integers _a and _b. Use an integer type able to handle huge numbers.

Implementation

Language

Elixir

Added by

Last edited by

Imports

Code

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)

Documentation URL

Original attribution URL

Online demo

Edit summary

Username

Be concise.

Be useful.

All contributions dictatorially edited by webmasters to match personal tastes.

Please do not paste any copyright violating resource.

Please try to avoid dependencies to third-party libraries and frameworks.

Implementation edit is for fixing errors and enhancing with metadata.

Instead of changing the code of the snippet, consider creating another Elixir implementation.

Other implementations

import "math/big"

x.GCD(nil, nil, a, b)

Demo
Doc

from fractions import gcd

x = gcd(a, b)

extern crate num;

use num::Integer;
use num::bigint::BigInt;

let x = a.gcd(&b);

Demo

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;

Origin

int gcd(int a, int b) {
  while (b != 0) {
    var t = b;
    b = a % t;
    a = t;
  }
  return a;
}

Demo

import std.numeric: gcd;

x = gcd(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);

Origin

x = a.gcd(b)

x = gcd a b

import java.math.BigInteger;

BigInteger x = a.gcd(b);

Demo
Doc

extension=gmp

$x = gmp_gcd($a, $b);

Demo
Doc

const gcd = (a, b) => b === 0 ? a : gcd (b, a % b)

Origin

(defn gcd [a b]
  (if (zero? b)
    a
    (recur b (mod a b))))

use bigint;

sub gcd {
    my ($A, $B) = @_;
    return 0 == $B
        ? $A
        : gcd($B, $A % $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);

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);
}

Imports System.Numerics

Dim x = BigInteger.GreatestCommonDivisor(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);
}

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

function gcd(a, b)
	if (b ~= 0) then
		return a
	else 
		return gcd(y, x%y)
	end
end

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

#include <numeric>

auto x = std::gcd(a, b);

Preview