Euclidean algorithm

From CodeCodex

Related content:

The Euclidean algorithm (also called Euclid's algorithm) is an algorithm to determine the greatest common divisor of two integers.

Implementations[edit]

C[edit]

Recursive version:

int gcd(int a, int b) {
  if (b == 0)
    return a;

  return gcd(b, a % b);
}

Iterative version:

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

Version with loop-unrolling:

int gcd(int a, int b)
{
  while(true)
  {
    a = a%b;
    if(a==0)
    {
      return b;
    }
    b = b%a;
    if(b==0)
    {
      return a;
    }
  }
}

For normal C/C++ integers loop-unrolling does not make much difference; in the case of big integers (several hundreds of digits), however, it avoids the cost of unnecessary copies of the integers.

int gcd(int u, int v) { u = (u < 0) ? -u : u; // make u non-negative v = (v < 0) ? -v : v; // make v non-negative while (u > 0){ if (u < v){ int t = u; // swap u and v u = v; v = t; } u -= v; } return v; // the GCD of u and v }

C#[edit]


/// <summary>
/// Greatest Common Divisor (Recursive)
/// </summary>
/// <param name="a">Integer A</param>
/// <param name="b">Integer B</param>
/// <returns>Greatest Common Divisor Between Integer A and Integer B</returns>
public static int GCD_Recursive(int a, int b)
{
    if (0 == b)
        return a;
    else
        return GCD_Recursive(b, a % b);
}

/// <summary>
/// Greatest Common Divisor (Iterative)
/// </summary>
/// <param name="a">Integer A</param>
/// <param name="b">Integer B</param>
/// <returns>Greatest Common Divisor Between Integer A and Integer B</returns>
public static int GCD_Iterative(int a, int b)
{
    int t;
    while (b != 0)
    {
        t = b;
        b = a % b;
        a = t;
    }
    return a;
}

/// <summary>
/// Greatest Common Divisor (Loop-Unrolling)
/// </summary>
/// <param name="a">Integer A</param>
/// <param name="b">Integer B</param>
/// <returns>Greatest Common Divisor Between Integer A and Integer B</returns>
public static int GCD_LoopUnrolling(int a, int b)
{
    while (true)
    {
        if ((a %= b) == 0) return b;
        if ((b %= a) == 0) return a;
    }
}

Common Lisp[edit]

Recursive version:

;;; Common Lisp already includes a function which does this, called
;;; GCD.
;;; Tail recursive (remember that tail-recursive optimization is
;;; usually off by default in most CL compilers and interpreters)
(defun greatest-common-divisor (a b)
    (if (zerop b)
        a
        (greatest-common-divisor b (mod a b))))

Iterative version:

;;; Common Lisp already includes a function which does this, called
;;; GCD.
(defun greatest-common-divisor (a b)
    (do ()
        ((zerop b) a)
        (psetf a b b (mod a b))))

Erlang[edit]

gcd(A, 0) -> A;
gcd(A, B) ->
    gcd(B, A rem B).

F#[edit]

Tail-recursive version (equivalent to an iterative version):

> let rec gcd a = function
    | 0 -> a
    | b -> gcd b (a % b);;
val gcd : int -> int -> int

For example:

> gcd 25 30;;
val it : int = 5

FORTH[edit]

: GCD
	DUP 0=
	IF DROP
	ELSE SWAP OVER MOD RECURSE
	THEN ;

Haskell[edit]

There is already a better "gcd" function included in the Prelude.

gcd :: (Integral a) => a -> a -> a
gcd a 0 = a
gcd a b = gcd b (a `mod` b)

For example:

> gcd 25 30
5

OCaml[edit]

Tail-recursive version (equivalent to an iterative version):

# let rec gcd a = function
    | 0 -> a
    | b -> gcd b (a mod b);;
val gcd : int -> int -> int = <fun>

For example:

# gcd 25 30;;
- : int = 5

Perl[edit]

Using Math::Cephes:

use Math::Cephes qw(euclid);
euclid($m, $n); # returns GCD as first element

Iterative:

sub gcd {
($m,$n) = @_;
while (($r = ($m % $n)) !=0) { $m = $n; $n = $r; }
return $n;
}

PHP[edit]

Recursive version:

function gcd($a, $b) {
    if ($b == 0)
        return $a;
    return gcd($b, $a%$b);
}

Iterative version:

function gcd($a, $b) {
    while ($b != 0)
        list($a, $b) = array($b, $a%$b);
    return $a;
}

Python[edit]

Recursive version:

def gcd(a, b):
    if b==0:
        return a
    return gcd(b, a%b)

Iterative version:

def gcd(a, b):
    while b!=0:
        a, b = b, a%b
    return a

Ruby[edit]

Recursive version:

def gcd(a, b)
  return a  if b.zero?
  gcd(b, a%b)
end

Iterative version:

def gcd(a, b)
  a, b = b, a%b  until b.zero?
  a
end

Seed7[edit]

const func integer: gcd (in var integer: a, in var integer: b) is func
  result
    var integer: result is 0;
  local
    var integer: help is 0;
  begin
    while a <> 0 do
      help := b rem a;
      b := a;
      a := help;
    end while;
    result := b;
  end func;

Wow I must confess you make some very tercnhant points.

Tcl[edit]

proc gcd {p q} {
 if {$q == 0} {return $p}
 gcd $q [expr {$p % $q}]
}