La multiplicación de los campesinos rusos: demostración

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).