El algoritmo binario del mcd

El máximo común divisor (mcd) de dos números enteros no negativos se puede calcular mediante un algoritmo binario basado en las siguientes propiedades:

  1. Si a,b son pares, entonces mcd(a,b) = 2*mcd(a/2,b/2)
  2. Si a es par y b impar, entonces mcd(a,b) = mcd(a/2,b)
  3. Si a es impar y b par, entonces mcd(a,b) = mcd(a,b/2)
  4. Si a y b son impares y a > b, entonces mcd(a,b) = mcd((a-b)/2,b)
  5. Si a y b son impares y a < b, entonces mcd(a,b) = mcd(a,(b-a)/2)
  6. mcd(a,0) = a
  7. mcd(0,b) = b
  8. mcd(a,a) = a

Por ejemplo, el cálculo del mcd(660,420) es

Definir la función

Definir la función

tal que (mcd a b) es el máximo común divisor de a y b calculado mediante el algoritmo binario del mcd. Por ejemplo,

Comprobar con QuickCheck que, para los enteros no negativos, las funciones mcd y gcd son equivalentes.

Soluciones

4 Comentarios

Escribe tu solución