martes, 19 de marzo de 2013

Algoritmo de Euclides binario


Esta entrada participa en la Edición 4.12 del  Carnaval de Matemáticas cuyo anfitrión es el blog High Ability Dimension.


En este blog nos motiva mucho el construir un esquema en hoja de cálculo que explique de la mejor forma posible el funcionamiento de un proceso o un algoritmo. Lo haremos hoy con la variante binaria del Algoritmo de Euclides.

Restar en lugar de dividir

Ya se sabe que el algoritmo de Euclides por divisiones se puede sustituir por otro efectuado a base de restar los dos números. Parece más lento, pero al ahorrar divisiones puede resultar más eficiente. Hace sesenta años lo usábamos los alumnos de Bachillerato (con once añitos) para comprobar si dos segmentos eran inconmensurables o no. Llevábamos uno sobre otro y nos quedábamos con la diferencia. Si al reiterar llegábamos al segmento nulo, es que tenían una medida común. Aquello era Geometría de Euclides pura.

Si el algoritmo clásico se organizaba a partir de la división euclídea, en esta variante se usa la resta. Así, para encontrar MCD(96,36) por divisiones sería: 96=2*36+24; 36=1*24+12; 24=2*12+0, luego el MCD(96,36)=12. Por restas formaríamos estas parejas: (96,36), (60,36), (36,24), (24,12), (12,12), (12,0), llegando al mismo resultado.

Eliminar el factor 2 siempre que se pueda.

En computación con sistema de numeración binario la división y la multiplicación por 2 se reducen a trasladar un lugar a la derecha o izquierda del dígito que se multiplica. Por eso, es interesante dar protagonismo al número 2 en los cálculos. Una primera idea es que si expresamos los dos números A y B de la forma A=2m*p, B=2n*q, con p y q los mayores divisores impares, el M.C.D se puede encontrar con dos cálculos por separado. Por una parte quedándonos con el menor exponente del 2 y por otra hallando MCD(p,q).

En el algoritmo que estamos presentando, se elimina en primer lugar la potencia de 2 común a ambos números, y se toma nota de ella. Una vez eliminada, el factor 2 no va a influir en el resultado, y cuando aparezca en alguno de los dos números se podrá igualmente suprimir. En términos binarios suprimir un 2 es trasladar los dígitos una posición hacia la derecha.

En Wikipedia y otras páginas que hemos consultado expresan lo anterior en forma de tres reglas. http://en.wikipedia.org/wiki/Binary_GCD_algorithm. No son difíciles de razonar.

(1) Si A y B son ambos pares se cumple MCD(A,B)=2*MCD(A/2,B/2)

Esto justifica que el primer paso que demos sea el de separar las potencias de 2.

(2) Si A es par y B impar se tiene MCD(A;B)=MCD(A/2,B)

Igualmente se aplicaría si B es par y A impar. En virtud de esta regla eliminaremos todos los factores 2 una vez que se ha separado la potencia común.

(3) Si ambos A y B son impares y A<B, MCD(A,B)=MCD(B-A,A). Si es B<A, MCD(A,B)=MCD(A-B,B)

Esta es la esencia del algoritmo de Euclides, restar ambos números.

Eliminar la potencia de 2 común (Regla 1)

Hemos creado una demo en hoja de cálculo para seguir visualmente los pasos del algoritmo binario. Lo puedes descargar desde la dirección

http://hojamat.es/sindecimales/divisibilidad/herramientas/herrdiv.htm#euclibin

Como nuestro objetivo es visual, desarrollaremos ahora los pasos sugeridos pero en forma de esquema. En una hoja de cálculo se escribirán los dos números y con un botón iterativo se irán avanzando pasos hasta llegar al MCD. Esta primera fase de eliminar el factor común lo puedes ver en las imágenes siguientes:









En primer lugar hemos escrito los números 192 y 84. Al pulsar sobre el botón Aceptar números se han convertido ambos en binario y se han reconstruido a la derecha. La potencia de 2 común figura al principio con el valor 1.

Observamos que ambos números terminan en dos ceros (en binario), luego compartirán el factor 22=4.
Según estamos explicando, el primer paso del algoritmo binario es eliminar el factor 2 común. Si ahora usamos el botón Paso a paso dos veces veremos que los dígitos de ambos números se mueven dos posiciones a la derecha y que la potencia de 2 se convierte en 4.



A la derecha figuran los números ya simplificados, 48 y 21, y la potencia de 2, que nos servirá al final.

Resto de pasos

Ahora la estrategia es triple:

(1) Si el primer número contiene aún potencias de 2, se eliminan (Regla 2)

Observa que en nuestro ejemplo el número 48 termina en cuatro ceros, luego al cabo de cuatro toques del botón Paso a paso desaparecerán.


(2) Se opera igual con el segundo: se le elimina el factor 2 (Regla 2)

En nuestro ejemplo ya no quedan factores 2 (por ahora)

(3) Si ambos son impares, se sustituye el mayor de ellos por la diferencia entre ambos.

Este es el núcleo del algoritmo de Euclides por diferencias. En la práctica quizás haya que intercambiar los valores de A y B, pero no entraremos en esos detalles.

Al restar dos impares se producirán nuevos factores 2, por lo que en la siguiente pasada del algoritmo los eliminará. Lo ves en las siguientes dos imágenes:




Reiteramos estas tres reglas hasta que lleguemos al valor 0. En ese momento el algoritmo construye el M.C.D. multiplicando el resultado por la potencia de 2 que tenía almacenada.
Aquí lo tienes:


Visto así, en hoja de cálculo, no parece ser nada del otro mundo, pero todas las operaciones que realiza son altamente eficientes en el sistema de numeración binario. Por algo lo introdujo el programador israelí Stein en 1967. Aquí sólo se nos queda como un tema de cultura matemática, pero es divertido implementarlo.

Versión recursiva

Lo que hemos desarrollado, con un botón que en cada paso reacciona según lo que se encuentra, nos permite sospechar que todo esto se resuelve también mediante una función recursiva. Es cierto, y está publicado. Lo que haremos aquí es adaptarlo al Basic de Excel y Calc:

Public Function mcdbin(m, n)
Dim mb

'Si son iguales, hemos llegado al MCD
If m = n Then
mb = m

'Si ambos son divisibles entre 2, se saca ese factor
ElseIf m / 2 = m \ 2 And n / 2 = n \ 2 Then
mb = 2 * mcdbin(m / 2, n / 2)

'El primero contiene un 2. Se elimina
ElseIf m / 2 = m \ 2 Then
mb = mcdbin(m / 2, n)

'Operamos de igual forma con el segundo
ElseIf n / 2 = n \ 2 Then
mb = mcdbin(m, n / 2)

'Ambos son impares. Se restan
Else
If m > n Then mb = mcdbin(m - n, n)
If n > m Then mb = mcdbin(m, n - m)
End If

'La función recoge el valor de mb
mcdbin = mb
End Function

Tiene toda la elegancia de las funciones recursivas
(ver http://hojaynumeros.blogspot.com.es/2012/03/funciones-recursivas-en-las-hojas-de.html)

En este caso resulta un poco complicada, pero funciona muy bien. Si te apetece, estudia la versión clásica y recursiva:

Public Function mcdeuclid(m, n)
Dim mb

'Si uno es múltiplo de otro, obtenemos el MCD
If m / n = m \ n Then
mb = n
ElseIf n / m = n \ m Then
mb = m
Else
'En caso contrario, se restan
If m > n Then mb = mcdeuclid(m - n, n)
If n > m Then mb = mcdeuclid(m, n - m)
End If
'La función recoge el valor de mb
mcdeuclid = mb
End Function

Ambas están implementadas en la herramienta que ofrecemos.




jueves, 14 de marzo de 2013

Funciones generatrices en Combinatoria– La teoría



En la entrada anterior presentábamos como un artificio sustituir los elementos de un producto cartesiano condicionado de conjuntos numéricos por polinomios en una indeterminada con exponentes idénticos a los números a combinar.

Hoy lo convertiremos en un desarrollo teórico.

Función generatriz de un conjunto numérico

Dado un conjunto ordenado de números reales o complejos (aquí usaremos casi exclusivamente los enteros positivos) {a0, a1, a2, a3,…an} llamaremos función generatriz (ordinaria) o generadora del mismo al polinomio de la forma


Si el conjunto tiene infinitos términos sustituiremos el polinomio por una serie de potencias, pero en este caso la igualdad


sólo tendrá sentido si dicha serie posee un radio de convergencia no nulo y la función está definida dentro de ese radio. No obstante, aquí  no trataremos la convergencia, sino las relaciones entre coeficientes. Si no converge, P(x) no será una función, pero las técnicas siguen valiendo.

Casos sencillos

El caso más sencillo de función generatriz es la que corresponde al conjunto {1,1,1,1,…1}
Si este es finito con n elementos, sabemos que su función generatriz se puede obtener mediante la fórmula de la suma de una progresión geométrica


Ya usamos esta fórmula en la entrada anterior

Si el conjunto es infinito {1,1,1,1,…}también es sencillo verificar que


Aquí nos encontramos con la potencia que tiene este método. Si derivamos miembro a miembro (omitimos detalles y también la cuestión de la convergencia) nos encontraremos con que

Por tanto esta es la función generatriz del conjunto {1,2,3,4,….}

La fórmula del binomio de Newton nos proporciona otro ejemplo de función generatriz. Los números combinatorios para un n dado tienen por función generatriz (1+x)n ya que


Podíamos seguir dando ejemplos hasta llenar páginas enteras, pero destacaremos especialmente dos técnicas

Manipulación algebraica

Con las técnicas algebraicas y sin plantearnos ahora el problema de la convergencia podemos encontrar la función generatriz de muchos conjuntos de coeficientes.

Por ejemplo, es fácil encontrarla para los números de Fibonacci F0, F1, F2,  F3,  F4…, de los que suponemos se conocen sus valores y propiedades. Observa estas manipulaciones:

F(x)=F0+F1x+F2x2+ F3x3+ F4x4+…=
F0+F1x+(F0+F1)x2+(F1+F2)x3+(F2+F3)x4+… =
F0+F1x+(F0 x2+ F1 x3+ F2 x4+…) + (F1 x2+ F2 x3+ F3 x4+…)

Pero en los paréntesis se está reconstruyendo F(x) de alguna forma, por lo que podemos escribir (pon tú los detalles)

F(x)= F0+F1x+F(x) x2+(F(x)- F0)x

Despejamos F(x), sustituimos F0 por su valor 0 (a veces se toma 1) y F1 por 1 y ya la tenemos:


Sólo hemos usado técnicas algebraicas sencillas. Más adelante comprobaremos este resultado.

Manipulación analítica

Si consideramos la derivación e integración formales podemos encontrar fácilmente funciones generatrices. Ya hemos considerado un ejemplo de derivación.

De la misma forma podemos usar la integración. Por ejemplo en la geométrica podemos integrar

Nos resultaría entonces



En cualquier manual puedes encontrar muchos ejemplos similares de este tipo de manipulación. No olvides que podemos mezclar las dos técnicas, analítica y algebraica, así como sumar, multiplicar y otras.

Problema inverso

Si la serie que define la función generatriz converge y conocemos esta, encontrar los coeficientes de la serie siempre es posible por la fórmula de McLaurin


Es un camino muy pesado, pero seguro. Sin embargo el problema contrario de dar los coeficientes y encontrar la expresión de P(x) quizás no lo puedas resolver. Es el clásico problema de la suma de series.

Con la ayuda de un ordenador se puede simplificar el proceso. Damos un ejemplo:

Antes vimos que los números de Fibonacci tenían como función generatriz (si se toma F0=0. A veces se toma F0=1 y entonces tiene una expresión ligeramente distinta)

Si tuviéramos posibilidad de desarrollar por McLaurin en algún lenguaje o programa, nos ahorraríamos mucho trabajo. Nosotros lo hemos hecho con el lenguaje PARI. Se entiende fácilmente aunque no se haya usado nunca:

{write("final.txt",taylor(x/(1-x-x^2), x,12))}

Ordenamos que escriba en el archivo “final.txt” 12 términos del desarrollo de Taylor (es en x=0) de la función dada. El resultado es:

0+x + x^2 + 2*x^3 + 3*x^4 + 5*x^5 + 8*x^6 + 13*x^7 + 21*x^8 + 34*x^9 + 55*x^10 + 89*x^11 + O(x^12)

Como vemos, los coeficientes son los números de Fibonacci. Si quisiéramos hacer F0=1 nos daría otro resultado, pues la función generatriz seria 1/(1-x-x2) (intenta demostrarlo)

Programaríamos en PARI esta variante:

{write("final.txt",taylor(1/(1-x-x^2), x,12))}

Obtendríamos la sucesión comenzando en 1:

1 + x + 2*x^2 + 3*x^3 + 5*x^4 + 8*x^5 + 13*x^6 + 21*x^7 + 34*x^8 + 55*x^9 + 89*x^10 + 144*x^11 + O(x^12)

Lo podemos intentar con el ejemplo de la entrada anterior, el de las bolas de colores, cuya función generatriz sin desarrollar era

Deberíamos escribir en PARI

{write("final.txt",taylor(x^5*(x^4-1)^2*(x^5-1)/(x-1)^3, x,20))}

Obtendríamos

x^5 + 3*x^6 + 6*x^7 + 10*x^8 + 13*x^9 + 14*x^10 + 13*x^11 + 10*x^12 + 6*x^13 + 3*x^14 + x^15 + O(x^20)

Identificamos los resultados de la entrada anterior: Con grado 9 el coeficiente es el esperado, 13. Para el grado 14 sólo 3 y para el grado 7 los 6 que ya se obtuvieron.

En otra entrada posterior veremos las funciones generatrices de combinaciones, variaciones y demás. Hoy seguiremos con ejemplos:

¿De cuántas formas se puede descomponer el número 28 como suma de primos distintos?

Los primos inferiores a 28 son 2, 3, 5, 7, 11, 13, 17, 19, 23. Cada uno de ellos o está en la suma una vez o no está. Entonces podemos usar términos del tipo (1+x^7) o (1+x^11) para combinarlos en la función generatriz:

F(x)= (1+x2) (1+x3) (1+x5) (1+x7) (1+x11) (1+x13) (1+x17) (1+x19) (1+x23)

Desarrollamos con wxMmaxima y nos da (hemos recortado la imagen):



Vemos que para el exponente 28 el coeficiente es 6, luego existen 6 formas distintas de expresar 28 como suma de primos distintos

Lo comprobamos con nuestra herramienta PARTLISTA (http://hojamat.es/sindecimales/aritmetica/herramientas/herrarit.htm#reprenum)



Con ella vemos las seis sumas: 28=11+17=5+23=3+5+7+13=2+7+19=2+3+23=2+3+5+7+11

Con la función generatriz hemos conseguido también otros muchos coeficientes, pero cuidado con la lista de primos 2, 3, 5, 7, 11, 13, 17, 19, 23. Este desarrollo sólo valdría hasta el 28. Para números mayores deberíamos añadir (1+x^29)(1+x^31)…

Luego con la función generatriz podemos resolver varios problemas a la vez.

Estos desarrollos algebraicos son pesados incluso con ayuda de los CAS. Sería bueno elegir un solo coeficiente en ellos. El lenguaje PARI que estamos usando últimamente (es gratuito aunque de gestión poco amigable) posee la función POLCOEFF(P(x),E) en la que P(x) es un polinomio y E un exponente dado, y nos devuelve el coeficiente de ese polinomio correspondiente al grado E. Nuestro problema del 28 se calcularía así:

print(polcoeff((x^2+1)*(x^3+1)*(x^5+1)*(x^7+1)*(x^11+1)*(x^13+1)*(x^17+1)*(x^19+1)*(x^23+1),28))

Daría un resultado de 6. Si cambiamos 28 por un número inferior obtendremos más resultados. Para números superiores deberíamos incrementar los primos.



jueves, 7 de marzo de 2013

Funciones generatrices en Combinatoria


Nota: Esta entrada es la primera de una serie que dedicaremos a las funciones generatrices y a los productos cartesianos condicionados. Aunque estarán enlazadas dentro de una secuencia lógica, para no convertir este blog en un tratado primaveral sobre Combinatoria, las iremos alternando con varias referentes a otros temas, en los que no abandonaremos nuestros queridos números ni a las hojas de cálculo.


Antes de iniciar cualquier planteamiento teórico sobre las funciones generadoras (o generatrices), muy usadas en Combinatoria y en el estudio de las sucesiones de números, las introduciremos mediante un ejemplo. Después, en sucesivas entradas, estudiaremos el concepto con más profundidad. Al principio no se ve bien la utilidad de estas funciones, pero si lees la serie entera que vamos a ir publicando descubrirás que constituyen un buen instrumento de cálculo. Paciencia, pues.

Problema

Deseamos elegir nueve cuentas de colores. Disponemos de cantidad suficiente de cuentas rojas, amarillas y verdes, pero queremos elegir entre 2 y 5 rojas, menos de 4 amarillas y al menos 3 verdes. ¿De cuántas formas podemos efectuar la elección?

Este problema nos plantea el desarrollo de particiones condicionadas de un número.

Ya hemos tocado este tema en el blog (http://hojaynumeros.blogspot.com.es/2011/02/particiones-de-un-numero.html y en
http://hojaynumeros.blogspot.com.es/2011/02/funciones-de-particion-de-un-numero.html)

Independientemente de que se trate de particiones, intentaremos resolver el problema con varias técnicas, y entre ellas la del uso de una función generatriz.

Con un producto cartesiano

Como de las rojas hemos de elegir entre 2 y 5, de las amarillas de 0 a 3 y de las verdes un mínimo de 3 y un máximo de 7 (¿por qué 7?), bastará formar el producto cartesiano  {2,3,4,5}{0,1,2,3}{3,4,5,6,7} e ir eligiendo las ternas que sumen 9. Un problema totalmente elemental que se puede resolver en enseñanzas medias.

A poco que nos pongamos obtendremos: 9= 2+0+7 = 2+1+6 = 2+2+5 = 2+3+4 = 3+0+6 = 3+1+5 = 3+2+4 = 3+3+3 =4+0+5 = 4+1+4 = 4+2+3 = 5+0+4 = 5+1+3.

En total 13 particiones. Para este problema no se necesitarían más técnicas, pero lo estamos tomando como modelo sencillo de introducción.

Con la hoja de cálculo “Cartesius”, aún en fase beta y que presentaremos más adelante, se pueden construir productos cartesianos condicionados. En el problema que nos ocupa plantearíamos esto, que se comprende sin más explicación:



Y obtendríamos



Como era de esperar, son los mismos resultados. Veamos ahora el método que deseamos explicar hoy.

Función generatriz

La idea revolucionaria de la función generatriz consiste en sustituir los distintos elementos numéricos por potencias de una indeterminada, y los conjuntos convertirlos en polinomios. Así el producto cartesiano {2,3,4,5}{0,1,2,3}{3,4,5,6,7} se puede escribir en forma de producto de polinomios:


Es fácil  darse cuenta de que si multiplicamos algebraicamente estos polinomios, el término de grado 9 tendrá como coeficiente el número de particiones pedido, en este caso 13.

Hemos sustituido una técnica de conteo por otra de tipo algebraico o analítico (esto último lo veremos más adelante)

En este caso tan sencillo parece que esto es una complicación, pero en casos generales veremos que puede resultar muy útil. Por dos motivos:

  •  Las técnicas algebraicas y analíticas permiten simplificar estos productos y  encontrar directamente el coeficiente deseado.
  •  Al desarrollar estos polinomios no sólo resolvemos el problema para 9 cuentas, sino para cualquier otro total posible.

Disponemos en este caso de una ayuda, y es que sabemos sumar muy bien las progresiones geométricas. Así, el producto de polinomios dado se puede expresar como



Este a su vez se puede simplificar como


Con tres pasadas del algoritmo de Ruffini encontraremos todos los coeficientes (omitimos los que no influyen en el problema)



Hemos destacado el que nos interesa: con grado 9 aparece el coeficiente 13, que es la solución, pero este procedimiento nos devuelve mucho más. Por ejemplo, con suma 7 sólo son posibles estas elecciones: 7=2+0+5=2+1+4=2+2+3=3+0+4=3+1+3=4+0+3, seis en total, como marca el esquema, y con suma 14 sólo deberán aparecer 3. Son estas: 4+3+7 = 5+3+6 = 5+2+7

Hemos resuelto varios problemas en uno

Si dispones de un CAS puedes ahorrarte bastante trabajo. Aquí tienes el resultado con la calculadora Wiris (hemos recortado la imagen) Compara los coeficientes con los que resultan con Ruffini.











Es normal que pienses que es mucha complicación, pero se trataba de un problema elemental. En sucesivas entradas daremos un enfoque teórico a las funciones generatrices y nos complicaremos un poco, descubriendo así su utilidad.