Un algoritmo de multiplicación encontrado en un libro de Paul Erdős: ¿cómo funciona?

Question

Estoy tratando de entender el siguiente problema de Erdos y Surányi en Temas de la teoría de números (Springer), capítulo 1 ("Divisibilidad, el Teorema Fundamental de la Teoría de Números"):

Puedes multiplicar dos números enteros positivos de la siguiente manera. Escribe los dos números uno al lado del otro. Divide el primero por la mitad, redondeando hacia abajo a un entero, y escribe el resultado debajo. Duplica el segundo número, escribiendo el resultado debajo. Continuamos este proceso de dividir/duplicar hasta que nos queda un $1$ en la primera columna. Tacha todos aquellos números en la segunda columna que están frente a un número par y suma los números restantes en esta columna para obtener el producto. Demuestra que esto funciona.

Y este es un ejemplo, $73 \cdot 217$:

$(73,217)$

$(36, 434)$

$(18, 868)$

$(9, 1736)$

$(4, 3472)$

$(2, 6944)$

$(1, 13888)$

Luego $73 \cdot 217 = 217+1736+13888 = 15841$, lo cual es correcto.

... y realmente no logro visualizar la razón por la que funciona. Mis pensamientos hasta ahora:

• Estamos dividiendo por $2$ en la columna de la izquierda, por lo que solo los valores impares provienen de una división de un número par anterior en la columna izquierda, lo que significa que la división anterior por $2$ fue "perfecta", es decir, sin decimales.

• Puedo aproximar el valor del producto de dos números naturales $p \cdot q$ si divido el primer número por $2$ continuamente hasta que llegue a $1$ y multiplico el segundo por $2$ al mismo tiempo (por lo que el valor final del segundo es una aproximación del producto).

Pero ¿por qué eliminamos algunos de ellos para la suma final? Me gustaría plantear las siguientes preguntas:

1. ¿Cómo funciona?

2. Estamos sumando los números de la segunda columna que están frente a un número impar. Entonces, ¿qué representa la suma de los números que no utilizamos de la segunda columna?

Todo esto probablemente sea bastante obvio, pero no logro ver la luz.

Answer 1

Este método es frecuentemente llamado "multiplicación campesina rusa".

A menudo se justifica pensando en escribir el primer número en binario. Aquí hay otra forma de explicarlo. En cada paso, estamos reemplazando un par $(p,q)$ ya sea por $(\frac{p}{2}, 2q)$ (cuando $p$ es par) o por $(\frac{p-1}{2},2q)$ (cuando $p$ es impar).

• En el primer caso, cuando $p$ es par, el producto de los dos números no cambia: $p \cdot q = \frac{p}{2} \cdot 2q$.
• En el segundo caso, cuando $p$ es impar, $\frac{p-1}{2} \cdot 2q = p \cdot q - q$. Así que el producto ha disminuido por $q$, y debemos apartar $q$ para más tarde.

Eventualmente, llegamos a un par $(1,r)$ cuyo producto es fácil de calcular: es simplemente $r$. Debido a que hemos mantenido un registro de cómo ha cambiado el producto de un par, sabemos que el producto original es igual a este producto, más todos los números que hemos apartado.

Pero hemos apartado $q$ del par $(p,q)$ siempre que $p$ es impar. Así que añadir los números que hemos apartado al número final simplemente corresponde a sumar el segundo número en cada par cuyo primer número es impar.

---

También querías saber qué representa la suma de los números opuestos a un número par.

Dado un $p$ y $q$ que deseas multiplicar, elige $k$ tal que $2^{k-1} - 1 < p \le 2^k - 1$. (En otras palabras, $2^k$ es la siguiente potencia de $2$ después de $p$, sin incluir $p$ en sí mismo).

Luego, si usamos este algoritmo para encontrar $(2^k-1)\cdot q$, tomaremos la misma cantidad de pasos para llegar a $1$ en el lado izquierdo, pero todos los números del lado izquierdo en el camino son impares. Esto nos dice que la suma de todos los números del lado derecho debería ser el producto $(2^k-1) \cdot q.

Dado que la suma de todos los números del lado derecho opuesta a un número del lado izquierdo impar es $p \cdot q$, la suma de todos los números del lado derecho opuesta a un número del lado izquierdo par es su diferencia $(2^k-1-p) \cdot q$.

Answer 2

Escribe $75$ en binario: $\mathtt{1001011}$; ahora escribe una tabla empezando por el dígito más a la derecha (uso $75$ para evitar simetría indeseada): $$ \begin{array}{lrr} \mathtt{1}=a_0 & 75 & 217 \\ \mathtt{1}=a_1 & 37 & 434 \\ \mathtt{0}=a_2 & 18 & 868 \\ \mathtt{1}=a_3 & 9 & 1736 \\ \mathtt{0}=a_4 & 4 & 3472 \\ \mathtt{0}=a_5 & 2 & 6944 \\ \mathtt{1}=a_6 & 1 & 13888 \end{array} $$ Como puedes ver, los números impares en la columna central corresponden a un dígito $\mathtt{1}$ en la representación binaria. Esto no es casualidad: quitar el dígito más a la derecha de la representación binaria es exactamente dividir por $2$ (descartando el residuo) y un dígito más a la derecha $\mathtt{1}$ significa que el número es impar.

El factor $m=75$ se escribe como $$ m=2^0a_0+2^1a_1+2^2a_2+2^3a_3+2^4a_4+2^5a_5+2^6a_6 $$ Por lo tanto, si $n=217$, el producto es \begin{align} mn&=(2^0a_0+2^1a_1+2^2a_2+2^3a_3+2^4a_4+2^5a_5+2^6a_6)n \\ &=2^0a_0n+2^1a_1n+2^2a_2n+2^3a_3n+2^4a_4n+2^5a_5n+2^6a_6n \\ &=\begin{aligned}[t] &a_0\cdot (2^0n)+{}\\ &a_1\cdot (2^1n)+{}\\ &a_2\cdot (2^2n)+{}\\ &a_3\cdot (2^3n)+{}\\ &a_4\cdot (2^4n)+{}\\ &a_5\cdot (2^5n)+{}\\ &a_6\cdot (2^6n) \end{aligned} \end{align} Cada número entre paréntesis en la suma final (escrita en columna) es el doble del anterior (empezando desde $n$). Ahora, usando los datos explícitos, obtenemos $$ \begin{array}{r@{}rl} 1\cdot{}&217 &+ \\ 1\cdot{}&434 &+ \\ 0\cdot{}&868 &+ \\ 1\cdot{}&1736 &+ \\ 0\cdot{}&3472 &+ \\ 0\cdot{}&6944 &+ \\ 1\cdot{}&13888 &=\\ \hline &217 &+ \\ &434 &+ \\ &1736 &+ \\ &13888 &=\\ \hline &16275 \end{array} $$

Si utilizas todos los términos de la última columna de la primera tabla, estás multiplicando $217$ por el número binario $\mathtt{1111111}=2^7-1=127$.

Por lo tanto, la suma de los números opuestos al dígito par corresponde al producto $217\cdot(127-75)$.

Answer 3

Otra forma de explicarlo para cualquiera que pase por aquí y lea esto:

Al principio tienes un montón de $217$s. $73$ de ellos. Eso es $73 \cdot 217$. Divides en un lado y duplicas en el otro para que el producto siga siendo el mismo.

Pero tienes que redondear hacia abajo cuando divides $73$. Así que en lugar de decir $73 \cdot 217$ dices $72 \cdot 217 + 1 \cdot 217$. Entonces puedes decir que tienes $36 \cdot 434 + 1 \cdot 217$.

Te "quedaste atrás" un $217$ cuando redondeaste hacia abajo. Del mismo modo, también acabas "dejando atrás" el $1736$. Así que al final, antes de decir que has terminado, tienes que volver y tener en cuenta los números que dejaste atrás.

Answer 4

El aspecto binario es algo interesante de mencionar, ya que esto está muy cerca de la implementación real de una unidad multiplicadora dentro de una CPU. Así es como iría el ejemplo 73*217 :

            (a)                 (b)
         1001001             11011001 (se suma al resultado)
          100100            110110010 (ignorado)
           10010           1101100100 (ignorado) 
            1001          11011001000 (se suma al resultado)
             100         110110010000 (ignorado) 
              10        1101100100000 (ignorado) 
               1       11011001000000 (se suma al resultado)
                       --------------
                       11110111100001 (resultado)

Si el bit menos significativo de a es 1 (esto significa que a es impar) entonces añadimos b al resultado. Luego, dividimos a por 2 (corrimiento de bits a la derecha), multiplicamos b por 2 (corrimiento de bits a la izquierda) y repetimos el proceso.

Otra forma de ver esto es imaginándolo de la misma manera en que escribimos una multiplicación en papel, en base 10: multiplicamos cada dígito de a por cada dígito de b por separado, mientras manejamos los acarreos. En binario, los dígitos son solo 0 o 1, por lo que se reduce a "sumar b" o "no sumar b".

Entonces, en lugar de dividir a por 2, podemos examinar el n-ésimo dígito de a en su representación binaria. Dado que el peso de cada dígito en a es 2^n, si el dígito n es 1, sumamos b*2^n al resultado.

            (a)                       (b)
         1001001                   11011001 (b * 2^0)
               ^ dígito 0
         1001001                11011001000 (b * 2^3)
            ^ dígito 3
         1001001             11011001000000 (b * 2^6)
         ^ dígito 6
                             --------------
                             11110111100001 (resultado)

Una CPU muy lenta hará esto de forma iterativa en software, utilizando solo instrucciones de corrimiento de bits, prueba de bits y suma.

Ejemplo para CPU Z80

Una CPU ligeramente más rápida, como Cortex-M0 "ligero", hará esto de forma iterativa en hardware: se obtiene un sumador condicional conectado a un desplazador de bits. Usará hasta 32 ciclos para una multiplicación de 32 bits x 32 bits, pero por supuesto, multiplicar por un número más pequeño podría requerir menos ciclos.

Y una CPU rápida implementará todo esto como un circuito único, que generalmente también está segmentado. Tiende a ser bastante complicado y utilizar una gran cantidad de lógica, pero así es como se obtiene una operación MUL por ciclo de reloj.

¡Así que, ese campesino ruso era en realidad bastante moderno!

Answer 5

(Nota del OP: como complemento a las respuestas, @ixi amablemente ha escrito un fragmento de Python que realiza el algoritmo del campesino ruso)

def multiplicación_campestre_rusa(a, b, acc = 0):
    print(a, b, acc+b)
    if a == 1:
        return b + acc
    elif (a % 2) == 0:
        return multiplicación_campestre_rusa(a // 2, b * 2, acc)
    else:
        return multiplicación_campestre_rusa(a // 2, b * 2, acc + b)
assert multiplicación_campestre_rusa(73, 217) == 15841