Método muy interesante para la multiplicación de números naturales

Question

En algún libro vi este ejemplo sobre cómo multiplicar números de $83$$157$.

$$83 \qquad 157$$ $$41 \qquad 314$$ $$20 \qquad 628$$ $$10 \qquad 1256$$ $$5 \qquad 2512$$ $$2 \qquad 5024$$ $$1 \qquad 10048$$

El procedimiento es que en la columna de la izquierda se divide por números de dos y anote el resultado en el número que dividido (si el número es impar entonces tomamos entero que es la más cercana al resultado, y el resultado) y repetimos el procedimiento hasta llegar al número uno.

En la columna de la derecha tomamos el siguiente número para ser dos veces tan grande como la anterior.

Ahora nos fijamos en las dos columnas y descartar aquellos números en la columna de la derecha si se corresponden con el número en la columna de la izquierda, por lo que descartamos $628$$1256$$5024$.

Si ahora añadimos el resto de los números en la columna de la derecha obtenemos $157+314+2512+10048=13031$ pero $13031=83 \cdot 157$.

Así que mi pregunta sería:

1) ¿este método funciona para cada dos números naturales $m,n$?

2) ¿Puede alguien explicar por qué este método funciona?

Answer 1

Si se escribe en la base de las $2$ es un poco más claro:

$$\begin{matrix}1010011_2&10011101_2\\ 101001_2&100111010_2\\ 10100_2&1001110100_2\\ \dots \end{de la matriz}$$

Por lo tanto, si $m=83,n=157$, luego la segunda columna de la $k$ fila (empezando por la fila $0$)$2^kn$. Y estamos agregando que en la suma de si hubo una $1$ $k$th bit de la derecha de $m$.

Así que esto va a funcionar en general.

Esta es básicamente la manera binaria de hacer la base habitual diez de la multiplicación.

En general, dada cualquier operación binaria asociativa $\star$, podemos hacer lo mismo para el cómputo de los $n^{\star m}=n\star n\star \cdots\star n$, donde tenemos $m$ ocurrencias si $n$. En este caso, $\star$ ( $+$ ), pero el método en sí es a menudo llamado "exponenciación por repetir la escuadra" porque es comúnmente usado con $\star$ de la multiplicación.

Answer 2

pensemos que queremos multiplicar a por b.($a < b$)

Suponga que a es un número par. A continuación,$a * b = (a / 2) * (b * 2)$.

Así que mientras a $a$ es aún, no tenemos ningún problema.

Pero cuando $a$ se convierte en extraño, entonces tenemos un problema. Pero podemos resolverlo como este:

$a * b = (a / 2) * (b * 2) = (\lfloor a/2 \rfloor + 0.5) * (b * 2)$

Así que para simplificar, en este método, se recomienda que la negligencia que $0.5$ parte y se siguen dividiendo y multiplicando por 2, hasta que $a$ se convierte en 1. Pero bueno, tenemos que añadir los $0.5$ partes. Como sabéis $0.5 * b * 2 = b$. Que es el número en la columna de la derecha.(El que estuvimos multiplicar por 2). Así que lo agregamos con el número que tiene en el final.

Lo que funciona para cada $m, n \in \mathbb{R}$