Implementación de algoritmos de teoría de números/Algoritmo de Euclides

El algoritmo de Euclides es un método antiguo y eficaz para calcular el máximo común divisor (mcd) entre dos números enteros. Fue originalmente descrito por Euclides en la proposición 2 del libro VII de Elementos de Euclides.

Descripción formal

Versión recursiva

Utilizando recursión, se puede expresar el algoritmo de manera natural:

 función $\mathrm {mcd} (a,b)\,$
   si $b=0\,$ 
     devolver $a\,$
   si no
     devolver $\mathrm {mcd} (b,a\,{\bmod {\,}}b)$

Versión iterativa

La versión iterativa es más eficiente para la implementación en una computadora:

función $\mathrm {mcd} (a,b)\,$
  mientras $a>0\,$ hacer
    $t\leftarrow a\,$
    $a\leftarrow b\,{\bmod {\,}}a$
    $b\leftarrow t\,$
  devolver $b\,$

Versión original

El algoritmo original descrito por Euclides trataba el problema de manera geométrica; usaba la substracción repetida en lugar del residuo de la división. Esta versión es significativamente menos eficiente:

 función $\mathrm {mcd} (a,b)\,$
   mientras $b>0\,$ hacer
     si $a>b\,$
       $a\leftarrow a-b$
     si no
       $b\leftarrow b-a$
   devolver $a\,$

Implementación en distintos lenguajes de programación

En lenguaje C

(versión recursiva)

 unsigned int mcd(unsigned int a, unsigned int b){
     return (b == 0)? a : mcd(b, a % b);
 }

(versión iterativa)

 unsigned int mcd(unsigned int a, unsigned int b){
     unsigned int t;
     while (a > 0){
         t = a;
         a = b % a;
         b = t;
     }
     return b;
 }

En lenguaje Logo

(versión recursiva)

para mcd :a :b
 si :b = 0 [
  devuelve :a
 ] sino [
  devuelve mcd :b resto :a :b
 ]
fin

(versión iterativa)

para mcd :a :b
 mientras [:a > 0] [
  haz "t :a
  haz "a resto :b :a
  haz "b :t
 ]
 devuelve :b
fin

En lenguaje Visual Basic 8

(versión recursiva)

Public Shared Function mcd(ByVal a As Integer, ByVal b As Integer) As Integer
	If b = 0 Then
		Return a
	Else
		Return mcd(b, a Mod b)
	End If
End Function

(versión iterativa)

 Public Function mcd(a As UInteger, b As UInteger) As UInteger
     Dim t As UInteger
     While a > 0
         t = a
         a = b Mod a
         b = t
     End While
     Return b
 End Function

En lenguaje Haskell

(versión recursiva)

mcd::Int->Int->Int
mcd a 0 = a
mcd a b = mcd b (mod a b)

En lenguaje Pascal

(versión iterativa)

 function MCD(a , b : integer): integer;
 var
   t:integer;
 begin
     while a > 0 do
     begin
       t := a;
       a := b mod a;
       b := t;
     end;
   result:=b;
 end;

En lenguaje Java

(versión iterativa)

	public MCD(int a, b,  t) {
	  while(a>0){
	   t=a;
	   a=b%a;
	   b=t;
	  }
	  System.out.println("El maximo comun divisor es: "+b);
 	 }

En lenguaje Python

(versión recursiva)

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

(versión iterativa)

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