Loading [MathJax]/jax/output/CommonHTML/jax.js

Herramientas de usuario

Herramientas del sitio


algoritmos-oia:enteros:maximo-comun-divisor

¡Esta es una revisión vieja del documento!


Tabla de Contenidos

Idea

Si queremos el máximo común divisor (mcd) entre A y B (digamos que AB), podemos pensar esto:

Si un número d divide a A y a B, entonces divide a la diferencia. Esto se ve ya que si A=nd y B=md, entonces (AB)=(nm)d, que como n y m son enteros es múltiplo de d.

Entonces, si todos los divisores comunes de A y B dividen a la diferencia, en particular el más grande lo hará mcd(A,B)=mcd(A,AB).

Ahora, qué pasa si queremos usar esto para calcular mcd(10000,1)? Diríamos “bueno, eso es igual a mcd(9999,1), que es igual a mcd(9998,1),. Pero eso es bastante lento. Algo que podemos pensar es que al principio, cuando tenemos mcd(10000,1), ya sabemos cuántas veces vamos a restar el 1 al número más grande. Tantas veces como pueda mientras siga siendo no negativo.

Entonces si A=kB+r, con r no negativo, le vamos a restar k veces el número B al otro número, y luego de eso nos va a quedar r en vez de A, junto con B que no lo modificamos.

Les suena la expresión A=kB+r? El valor de r viene a ser el resto de A en la división por B.

Un código pequeño pero muy efectivo a la hora de buscar un máximo común divisor es el siguiente:

int mcd(int a, int b){
    if(b==0){
        return a;
    }else{
        return mcd(b, a%b);
    }
}

Complejidad

Esto es importante para asegurarnos que este método conviene más que ir mirando los divisores de uno de los dos y ver si divide al otro.

Si tenemos los números A y B, con A>B, cuánto se achica el número A al reemplazarlo por A?

  • Si B>A/2, entonces A=B+r con r<A/2
  • Si BA/2, entonces como el resto r de dividir por B es siempre menor que BrB/2

Entonces el número más grande será a lo sumo la mitad del más chico. Luego de un paso más, el número que no se modificó, B, será a lo sumo la mitad del otro, que es a lo sumo la mitad de B, por lo que B se reemplaza por a lo sumo B/4.

De este razonamiento se puede ver que la complejidad es del orden del logaritmo del número más chicos de los iniciales.

Comentario

Una propiedad válida para todo par de enteros A,B es que AB=mcd(A,B)mcm(A,B), donde mcm denota el mínimo común múltiplo. Entonces, una manera de calcular el mcd de dos enteros de manera rápida es hacer simplemente mcd(A,B)=AB/mcd(A,B).

algoritmos-oia/enteros/maximo-comun-divisor.1511403988.txt.gz · Última modificación: 2017/11/23 02:26 por sebach