Algunos de nuestros lectores reclaman la demostración matemática del algoritmo de los campesinos rusos que publicamos ayer.
En realidad, lo que estamos haciendo es descomponer el número de la derecha en potencias de dos. En el ejemplo de ayer, teníamos 105×68. Si descomponemos 68 en potencias de dos, tenemos que 68 = 64 + 4 = 2^6 + 2^2. Como la multiplicación es distributiva, está claro que 105×68 = 105×(64+4) = 105×64 + 105×4.
¿Cómo se conecta esto con el algoritmo? Comencemos por la columna de la derecha. En la primera fila, si el número de la derecha es par, quiere decir que a la hora de descomponerlo en potencias de dos, no aparecerá 2^0 = 1, por eso lo tachamos. (En caso de que el número de la derecha fuese impar, sí que aparecería el 1 en su descomposición. Por ejemplo, 5 = 4 + 1 = 2^2 + 2^0).
Ahora pasamos a la segunda fila. A la derecha, hemos dividido todo por 2. Sigamos con nuestro ejemplo: si 68 = 2^6 + 2^2, al dividir por dos tenemos 34 = 2^5 + 2. Ahora llega el paso clave: si el sumando 2^0 = 1 apareciese al descomponer el número de la segunda fila, equivaldría a que el sumando 2^1 = 2 apareciese en la primera fila (donde tenemos el número original).
En nuestro ejemplo, 34 vuelve a ser par. Esto quiere decir que 2^0 no aparece al descomponer 34 en potencias de dos. Si multiplicamos por dos, equivale a decir que 2^1 no aparece al descomponer 68 (nuestro número original) en potencias de dos.
¿Seguís el hilo? bien, pasemos a la tercera fila. En este caso tenemos 17 = 2^4 + 2^0. Si deshacemos el camino andado y multiplicamos por 4, tenemos que 68 = 2^6 + 2^2. Es decir, como el sumando 1 aparece al descomponer 17, esto equivale a que el sumando 4 aparezca al descomponer 68 = 17×4.
A la hora de dividir por dos nuevamente, como ya hemos contado la influencia del sumando 1, lo restamos: 17 – 1 = 16, 16 / 2 = 8. Por eso se redondea a la baja. 8 vuelve a ser par, tachamos la fila. En la siguiente iteración, 4 es par, tachamos la fila. Una vez más, 2 es par, tachamos la fila. Al final del todo, en la sexta iteración, obtenemos 1, que es impar, lo cual quiere decir que en nuestro número original aparecerá 2^6 en su descomposición.
Ya hemos acabado con la columna de la derecha. En ella, hemos visto como 68 se descompone en 2^6 + 2^2, y por tanto nuestra multiplicación original se descompone de la siguiente forma: 105×68 = 105×(64+4) = 105×64 + 105×4 = 105×(2^6) + 105×(2^2).
¿Y qué hemos hecho en la columna de la izquierda? Pues precisamente ir multiplicando nuestro número original (105) sucesivamente por 2^0 = 1, 2^1 = 2, 2^2 = 4, etc. De modo que al final, cuando hemos descartado las filas que no nos interesan, precisamente nos ha quedado 105×(2^2) y 105×(2^6). Haciendo la suma, obtenemos el valor de la multiplicación original 105×68.
Demostración genérica
Para los que queráis una demostración matemática estricta, usaremos el principio de inducción (si no sabes lo que es, puedes dejar de leer aquí ;)). Denotemos A×B el producto de dos números naturales A y B usando el algoritmo habitual (la multiplicación de toda la vida con todas sus propiedades asociadas), y A*B el producto de dos números A y B usando el método de los campesinos rusos (sobre el cual a priori conocemos su ‘mecanismo’, pero no sus propiedades). Para B = 1, comprobamos que se cumple A×B = A*B, independientemente de cual sea el número A. Vamos a aplicar el principio de inducción sobre la variable B.
Supongamos la hipótesis de que para un B natural cualquiera se cumple 2A×[B/2] = 2A*[B/2]. ([n] denota la parte entera redondeando a la baja). Entonces, aplicando el algoritmo de los campesinos rusos, tenemos que
A*B = 2A*[B/2] + x, siendo x = A si B es impar, x = 0 si B es impar (!!).
Por otro lado, por las propias características de la multiplicación habitual, es inmediato que
A×B = 2A×[B/2] + x, siendo x = A si B es impar, x = 0 si B es par.
Como hemos supuesto 2A×[B/2] = 2A*[B/2], podemos extender nuestra hipótesis a que A×B = A*B.
Veamos ahora que si nuestra hipótesis es cierta para B, también lo es para B+1:
A*(B+1) = 2A*[(B+1)/2] + x, siendo x = A si B+1 es impar (es decir, si B es par) y x = 0 si B+1 es par (es decir, si B es impar).
Y aquí hemos hecho una pirueta muy interesante, atención: si B es par, resulta que al hacer A*B tenemos que x = 0, de modo que A*B = 2A*[B/2]. Ahora, al hacer A*(B+1) tenemos que x = A… ¡pero [(B+1)/2] = [B/2]! (ya que estamos redondeando a la baja). Es decir, que
A*(B+1) = A*B + A.
Por otro lado,
A×(B+1) = A×B + A.
Aquí no tenemos que demostrar nada ya que en la multiplicación tradicional damos por sentada la propiedad distributiva. Como en un principio hicimos la hipótesis A×B = A*B, resulta que
A*(B+1) = A*B + A = A×B + A = A×(B+1).
Aplicando el principio de inducción, hemos demostrado que para cualquier número natural par B, A×B = A*B, es decir, el algoritmo ruso es totalmente equivalente al tradicional. Para los B impares, la demostración es totalmente análoga, a partir de la ‘pirueta’ simplemente hay que considerar B impar y los resultados salen igual. Os lo dejo como ejercicio ;)
Y como no hemos impuesto restricciones sobre A, queda demostrado que para cualquier pareja de números naturales, el algoritmo de los campesinos rusos (al que hemos denotado como A*B) es totalmente equivalente a la operación tradicional de multiplicación, denotada por A×B.
Actualización: me acabo de dar cuenta de que la igualdad marcada con (!!) no es ni mucho menos inmediata y también requiere una explicación, ¿alguien se anima?. Recordad que el asterisco (*) no denota el producto habitual, sino el producto dado por el algoritmo de los campesinos rusos, de la que a priori no sabemos sus propiedades (precisamente el objetivo de la demostración es probar que en realidad la operación que hemos denotado como (*) equivale al producto de toda la vida).
Comentarios
Me ha costado ¿eh? Porque tenía tiempo libre, si no, no esperéis muchas más de estas :P
Se te agradece el esfuerzo Ignacio :)
Gracias.
Todavía me queda entender algún que otro punto. Me he liado un poco.
Muy buen esfuerzo, necesario para personas exigentes.
La forma en que yo la entiendo es de la siguiente manera, sacas un factor de dos del segundo número y lo multiplicas por el otro.
105 · 68
105 (2 · 34)
210 · 34
210 (2 ·17)
420 · 17
y aqui hay un problema que resolvemos descomponiendo
420 ·(16+1)
(420 · 16) + 420
seguimos descomponiendo el primer término
(420 · 2 · 8) + 420
(840 · 2 · 4) + 420
(1680 · 2 · 2) + 420
(3360 · 2) + 420 6720 + 420
=7140
Y disculpa por no responder la última cuestión que no la entendí.
A riesgo de hacerme pesado, la 'demostracion' mas entendible para mi seria pasar los numeros a binario (base 2) y multiplicar normalmente con lapiz y papel. Vemos que los pasos que seguimos son exactamente los mismo que los del sistema de los campesinos.
Si sabemos que la multiplicacion tradicional es correcta, este metodo 'intuitivamente' tambien lo seria. Con los mismo numeros del ejemplo:
105...........1101001
68............1000100
----------------------
..............0000000
.............00000000
420.........110100100
...........0000000000
..........00000000000
.........000000000000
6720....1101001000000
----------------------
7140....1101111100100
Observad que los numeros que 'nos quedamos' corresponden con los dos 'unos' que hay en el multiplicador '68'. Aqui solo hay que mirar las cifras, como es normal. Pero en el metodo de los campesinos esto se sabe dividiendo el 68 por dos cada vez y mirando si el resultado es par o impar. Asi saben si es un 'uno' o un 'cero'.
Cada linea del sumatorio es el '105' multiplicado por 2, por 4, 8, 16... esto aqui supone simplemente ir añadiendo un cero a la derecha del 68 cada vez.
De hecho este metodo se podria aplicar a numeros en base 3, 4, 5... o en cualquier base. Quizas en otro planeta donde tenga diferente numero de dedos usen otra base de forma natural.
A ver si se ve mejor:
..............1101001....105
..............1000100....68
----------------------
..............0000000
.............00000000
............110100100....420
...........0000000000
..........00000000000
.........000000000000
........1101001000000....6720
----------------------
........1101111100100....2140
???????????? estoy perdido.
Después de leerlo varias veces, me parece satisfactorio el post aunque se ha convertido en algo lioso.
Sólo un apunte, los primeros en usar este método fueron los egipcios. Por cierto, alguien me puede confirmar si este método se usa para multiplicar en ordenadores?
'Peasant', 'binary' y 'shift and add' son el mismo sistema de multiplicacion:
http://thedailywtf.com/Articles/Programming-Praxis... http://www.answers.com/topic/binary-notation#Multi... http://www.answers.com/topic/multiplication-algori...
Escribir un comentario
Para hacer un comentario es necesario que te identifiques: ENTRA o conéctate con FacebookConnect