Euclidean algorithm

From CodeCodex

Revision as of 13:28, 20 June 2007 by 206.160.140.2 (Talk)

Related content:

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

Implementations

C

Recursive version:

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

  return gcd(b, a % b);
}
C#

public static int TBH_GCD(int a, int b)
        {
            if(0==b)
                return a;
            else
                return TBH_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.

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

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

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

Perl

<HIGHLIGHTSYNTAX language="perl"> use Math::Cephes qw(euclid); euclid($m, $n); # returns GCD as first element </HIGHLIGHTSYNTAX>

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


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

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;

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