# Euclidean algorithm

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

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#

```
/// <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

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

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

### 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
```

### FORTH

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

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

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

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

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

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

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

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

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