Ejemplo de Algoritmo alternativo al de Euclides que calcula el MCD con operaciones binarias

El algoritmo de Euclides permite el calculo del Máximo Común Divisor. Sin embargo, este requiere de que la realización de divisiones, por eso existe el siguiente algoritmo que permite tal calculo sin que se tenga que efectuar tal operación.


Proceso AlgoritmoEuclidesBinario

 Definir u como entero;
 Definir v como entero;
 Definir desplazamiento Como Entero;
    Definir continuar como logico;
 Definir temporal como entero;
 Definir MCD como entero;

 Escribir "Ingrese uno de los numeros de los que calculara el MCD: ";
 Leer u;

 Escribir "Ingrese uno de los numeros de los que calculara el MCD: ";
 Leer v;

 desplazamiento <- 1;



 Mientras ((u %2 = 0) & (v % 2 = 0)) Hacer

  u <- u /2;
  v <- v /2;
  desplazamiento <- desplazamiento*2;

 FinMientras

 continuar <- verdadero;

 Mientras u % 2 = 0 Hacer
u <- u / 2;
 FinMientras


 Mientras continuar Hacer

  Mientras v % 2 = 0 Hacer
   v <- v / 2;
  FinMientras
  Si u > v Entonces
   temporal <- u;
   u <- v;
   v <- temporal;
  FinSi
  v <- v - u;
  Si v = 0 Entonces
   continuar <- falso;
  FinSi
 FinMientras

    MCD <- desplazamiento*u;
 Escribir "El MCD es :",MCD;


FinProceso

Basado en la Wikipeda