Euclidean algorithm

From CodeCodex

Image:Lightbulb.png Related content:
<DPL>

category=Math shownamespace=false </DPL>

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

Contents

[edit] Implementations

[edit] C

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.

[edit] C++ 

#include <algorithm>
#include <cstdlib>

// Euclid's Algorithm for GCD
int GCD(int a, int b) {
    // No negatives
    a = abs(a);
    b = abs(b);

    // Ensure a >= b; can save a useless MOD
    if (b > a) { std::swap(a, b); }

    // Main loop of algorithm
    int temp;
    while (b > 0) {
        temp = b;
        b = a % b;
        a = temp;
    } // end while
    return a;
} // end GCD()

[edit] C#


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

[edit] F#

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

[edit] FORTH

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

[edit] Haskell

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

[edit] OCaml

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

[edit] Perl

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

[edit] PHP

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

[edit] Python

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

[edit] Ruby

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

[edit] Seed7

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;

[edit] Common Lisp

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

[edit] Scheme


(define (gcd i j)
(if (= j 0)
i
(gcd j (modulo i j))))
Retrieved from "http://codecodex.com/wiki/Euclidean_algorithm"