<< Algoritmo de Euclides >>

Dificultad:

Lecciones anteriores:

Divisor común mayor En esta lección se explica la idea del DCM y se ven algunos programas que permiten comparar los distintos algoritmos para camcular el DCM.

Divisor común mayor factorizando

Método básico:

En esta lección vamos a ver el Algoritmo de Euclides que es un método muy astuto para calcular el divisor común entre dos números. Una de sus principales ventajas es que no es necesario calcular los divisores ni los factores de los números, por lo que anda muy muy rápido, incluso cuando alguno de los números es un primo o tiene algún factor primo grande.

Este método se basa en la siguiente propiedad:

• si A y B son enteros entonces DCM(A,B) = DCM(A-B,B)

Pueden encontrar la demostración aquí.

La idea es ir achicando los números tanto como se pueda hasta que el divisor común mayor (DCM) sea obvio, por ejemplo que sean ambos números iguales, o que uno de los dos sea cero.

Por ejemplo: DCM entre 8069 y 5209 (Charladito)

Resulta que el DCM entre 8069 y 5209 es igual al DCM entre el más chico de los dos y la diferencia entre ellos, o sea al DCM entre 5209 y 8069-5209=2860.

Ahora sólo tenemos que calcular el DCM entre 5209 y 2860. La mala noticia es que es casi tan fea como la cuenta inicial. La buena noticia es que son números más chicos, asi que confiemos en Euclides y sigamos.

El DCM entre 5209 y 2860, sabemos que es igual al DCM entre el más chico (2860) y la diferencia (5209-2860), o sea al DCM entre 2860 y 2349.

Ahora sólo tenemos que calcular el DCM entre 2860 y 2349...

Y así seguimos un rato ... largo ... hasta encontrar una cuenta fácil. Creanme que al final, después de un par de páginas, da 1.

Por ejemplo: DCM entre 8069 y 5209 (Con fórmulas)

Podemos reescribir toda la discusión de arriba en fórmulas, así queda mas corto.

DCM(8069,5209) =DCM(8069-5209,5209) =DCM(2860,5209) =DCM(5209-2860,2860) =DCM(2349,2860) =DCM(2860-2349,2349) =DCM(511,2349) =DCM(2349-511,511) =DCM(1838,511) =DCM(1838-511,511) =DCM(1327,511) =DCM(1327-511,511) =DCM(816,511) =DCM(816-511,511) =DCM(305,511) =DCM(511-305,305) =DCM(206,305) =DCM(305-206,206) =DCM(99,206) =DCM(206-99,99) =DCM(107,99) =DCM(107-99,99) =DCM(8,99) =DCM(99-8,8) =DCM(91,8) =DCM(91-8,8) =DCM(83,8) =DCM(83-8,8) =DCM(75,8) =DCM(75-8,8) =DCM(67,8) =DCM(67-8,8) =DCM(59,8) =DCM(59-8,8) =DCM(51,8) =DCM(51-8,8) =DCM(43,8) =DCM(43-8,8) =DCM(35,8) =DCM(35-8,8) =DCM(27,8) =DCM(27-8,8) =DCM(19,8) =DCM(19-8,8) =DCM(11,8) =DCM(11-8,8) =DCM(3,8) =DCM(8-3,3) =DCM(5,3) =DCM(5-3,3) =DCM(2,3) =DCM(3-2,2) =DCM(1,2)= DCM(2-1,1) =DCM(1,1) =DCM(1-1,1) =DCM(0,1) =1

Así que el divisor común mayor entre 8069 y 5209 es 1.

Si revisan con cuidado, van a ver que a pesar de que son muchas cuentas, todas son muy simples (solo hay que restar y restar y restar). En cambio si uno trata de calcular el divisor común mayor de la manera usual, puede pasarse bastante tiempo buscando cuales son los divisores de 8069 y 5209.

Por ejemplo: DCM entre 8069 y 5209 (Con fórmulas, cortito)

Reescribimos la cuenta de arriba, pero sin indicar las restas. Así queda más claro.

DCM(8069,5209) =DCM(2860,5209) =DCM(2349,2860) =DCM(511,2349) =DCM(1838,511) =DCM(1327,511) =DCM(816,511) =DCM(305,511) =DCM(206,305) =DCM(99,206) =DCM(107,99) =DCM(8,99) =DCM(91,8) =DCM(83,8) =DCM(75,8) =DCM(67,8) =DCM(59,8) =DCM(51,8) =DCM(43,8) =DCM(35,8) =DCM(27,8) =DCM(19,8) =DCM(11,8) =DCM(3,8) =DCM(5,3) =DCM(2,3) =DCM(1,2) =DCM(1,1) =DCM(0,1) =1

Veamos otro ejemplo: Calcular el DCM(1651,2353)

En este otro ejemplo, hacemos las cuentas rápido sin indicar las restas.

DCM(1651,2353) =DCM(702,1651) =DCM(949,702) =DCM(247,702) =DCM(455,247) =DCM(208,247) =DCM(208,247) =DCM(39,208) =DCM(169,39) =DCM(130,39) =DCM(91,39) =DCM(52,39) =DCM(13,39) =DCM(26,13) =DCM(13,13) =DCM(0,13) =13

Así que el divisor común mayor entre 1651 y 2353 es 13.

Función automática:

Se puede hacer una función para que la computadora haga estas cuentas y así calcule el DCM entre dos números. Vamos a definirla con el mismo formato que usamos en las lecciones anteriores. (En realidad esta función anda bien si a y b son enteros positivos o cero.)

En la lección Divisor común mayor hay un programa que pregunta dos números y usa una función para calcular el DCM (sirve para ver si andan bien). En el probador de funciones hay otro programa que genera unos 1000 pares de números y les calcula el DCM (sirve para ver cuál anda más rápido). Pueden reemplazar la función DCM que está en esos programas por esta y compararlas.

Función en Basic:

Deflng A-Z 'Las variables son enteros largos

Function DCMRestando(a,b) 

    CopiaA=a 'Copia a A (ver nota abajo)

    CopiaB=b 'Copia a B (ver nota abajo)

    'Print "DCM("; CopiaA; ","; CopiaB; ")"

    Do While CopiaB <> 0

        If CopiaA < CopiaB Then

            'si estan al reves los doy vuelta

            Temp = CopiaA

            CopiaA = CopiaB

            CopiaB = Temp

        End If

        CopiaA = CopiaA - CopiaB

        'Print "=DCM("; CopiaA; ","; CopiaB; ")"

    Loop

    DCMRestando = CopiaA

    'Print "=" ; CopiaA

End Function

Todas las salidas a pantalla (Print) están comentadas para que no molesten en un programa normal, pero puede ser útil activarlas para entender como funciona exactamente la función.

Un poco más rápido:

Para acelerar un poco las cuentas se puede utilizar la división entera para hacer varios de estos pasos al mismo tiempo. Al dividir A por B el cociente representa la cantidad de veces que entra B completamente en A y el resto es lo que sobra para que la cuenta sea exacta, por lo que después de restarle B a A varias veces vamos a terminar obteniendo el resto.

Por ejemplo en el primer ejemplo aparece

DCM(2349,511) =DCM(1838,511) =DCM(1327,511) =DCM(816,511) =DCM(305,511)

y al hacer la división entera de 2349 dividido 511 se obtiene como resultado 4 y resto 305. Por esto se ve en el ejemplo hay que restarle 4 veces 511 y se obtiene como resultado 305.

De esta manera los ejemplos quedan:

DCM(8069,5209) =DCM(8069-5209,5209) =DCM(2860,5209) =DCM(5209-2860,2860) =DCM(2349,2860) =DCM(2860-2349,2349) =DCM(511,2349) =DCM(2349-4*511,511) =DCM(1838,511) =DCM(305,511) =DCM(511-305,305) =DCM(206,305) =DCM(305-206,206) =DCM(99,206) =DCM(206-2*99,99) =DCM(8,99) =DCM(99-12*8,8) =DCM(3,8) =DCM(8-2*3,3) =DCM(2,3) =DCM(3-2,2) =DCM(1,2)= DCM(2-2*1,1) =DCM(0,1) =1

Si uno mira el primer ejemplo con cuidado, se ve que estamos restando 12 veces el número 8. Acá hacemos todas esas restas en un solo paso. El otro ejemplo es similar, pero ponemos directamente el resto en vez de indicar las restas.

DCM(1651,2353) =DCM(702,1651) =DCM(949,702) =DCM(247,702) =DCM(208,247) =DCM(208,247) =DCM(39,208) =DCM(13,39) =DCM(0,13) =13

Con esta observación podemos mejorar la función de la siguiente manera, usando el resto de la división entera. En esta función no se necesita verificar si el valor de a es mayor que el de b, porque si a fuera más chico la primera división de 0 y sólo se dan vuelta los números.

Deflng A-Z 'Las variables son enteros largos

Function DCMEuclides(a,b) 

    CopiaA=a 'Copia a A (ver nota abajo)

    CopiaB=b 'Copia a B (ver nota abajo)

    Do While CopiaB<>0

        'si es necesario las da vuelta

        Temp = CopiaA Mod CopiaB

        CopiaA = CopiaB

        CopiaB = Temp

    Loop

    DCMEuclides = CopiaA

End Function

Es sorprendente lo corta que es esta función y además anda realmente muy rápido, así que en (¿casi?) todos los casos es preferible usar esta función a todas las que vimos antes.

Nota: En ambos programas se hacen copias de los parámetros a y b para operar con las copias y no modificarlos. Esto es necesario porque sino al cambiarse los valores dentro de la función, se cambian los valores de las variables en el programa principal (o de donde se llame a la función). Esto sólo es necesario en QB y VB, pero no en Pascal, C, etc. porque en estos lenguajes la función recibe normalmente sólo el valor de las variables. En general uno ni se preocupa por todo esto, hasta que el programa comienza a hacer cosas inexplicables. Si querés leer un poco más sobre este tema y ver otros ejemplo podes ir las notas sobre valor y referencia.

Comentarios:

Cuando hay que hacer los cálculos de divisores comunes mayoras a mano, a veces se puede utilizar un poco de astucia para combinar este método con las propiedades que vimos la lección pasada. Por ejemplo, es facil ver a simple vista cuando un número es múltiplo de 10, o cuando es par. Así que también se podrían resolver los ejemplo anteriores de la siguiente manera:

DCM(8069,5209) =DCM(2860,5209) =DCM(286*10,5209) =DCM(286,5209) =DCM(143*2,5209) =DCM(143,5209) =DCM(143,5209) =DCM(5209-143*3,143) =DCM(4780,143) =DCM(239*20,143) =DCM(239,143) =DCM(96,143) =DCM(49,96) =DCM(7*7,3*31) =1

En esta cuenta, en el tercer paso usamos que 2860 es múltiplo de 10, y 5209 no es múltiplo de 2 ni de 5, así que DCM(2860,5209) =DCM(286,5209). Y repetimos el truco varias veces. ¡En el otro ejemplo, podemos tachar un 100 en un sólo paso!

DCM(1651,2353) =DCM(702,1651) =DCM(351,1651) =DCM(1300,351) =DCM(13,351) =13

Sin embargo la mayoría de estos trucos que se pueden hacer a ojo (usando las reglas de divisibilidad más sencillas) no son tan útiles en un programa.

Ejercicios:

1. Comparar las funciones de las tres lecciones. ¿Cuál va más rápido? ¿Cómo depende el tiempo del valor de la constante máximo en el probador de funciones?
   
2. Encontrar n entero positivo de manera que el divisor común mayor entre n² y (n+10)² sea lo más grande posible. (Sugerencia: probar un rato con la computadora y cuando se convenzan de que tienen el resultado correcto demostrarlo con lápiz y papel.)
   
3. Tratar de encontrar dos enteros para que la función DCMEuclides tenga que hacer la mayor cantidad de cuentas posibles. Comparar el tiempo que tarda en el peor caso que consigan con el peor caso de las funciones de la lección pasada.
   
4. Escribir una función que calcule el DCM mezclando el algoritmo de Euclides y la factorización. Por ejemplo que pruebe con los primos más chicos (por ejemplo hasta 100) y al pedazo que le quede sin factorizar le aplique el algoritmo de Euclides. (Nota: Creo que eligiendo bien el máximo número primo con que prueba (por ejemplo 100) se puede hacer que vaya un poco más rápido que las funciones normales. Sin embargo esta nueva función es más complicada y difícil de escribir. Si encontrás algo interesante mandalo a cym98@oma.org.ar )
   

Lecciones siguientes:

ninguna