Campesina rusa Método para la multiplicación

Question

Exactamente lo que sucede con el resto de este algoritmo? Yo no entiendo por qué se "cayó".

Ejemplo:

$$\begin{array}{c} \text{Half}&&\text{Double}&\text{Remainder}\\ \hline 38&\times&15&1\\ 18&\times&30&1\\ 9&\times&60\\ 4&\times&120\\ 1&\times&480 \end{array}$$

Lo que está sucediendo con el $1$'s???

Answer 1

Creo que has algunas ideas erróneas sobre el funcionamiento del algoritmo y la razón por la que funciona.

Vamos a mirar en detalle en $37\cdot 15=555$. Aquí está la tabla correcta, en el acuerdo que usted utiliza en su pregunta, pero con un poco más de detalle. (Ignore los subrayados y las $\text{Row}$ columna por ahora.)

\begin{array}{c|cc} \text{Row}&\text{Half}&&\text{Double}&\text{Remainder}\\ \hline 0&37&\times&\underline{15}&1\\ 1&18&\times&30&0\\ 2&9&\times&\underline{60}&1\\ 3&4&\times&120&0\\ 4&2&\times&240&0\\ 5&1&\times&\underline{480}&1 \end{array}

Hay un resto en la última línea porque $1$ sería dejar un resto si iba a reducir a la mitad.

Ignorar la $\text{Double}$ columna por ahora. La primera y última columnas de decirle que

$$\begin{align*} 37&=2\cdot 18+1\\ &=2(2\cdot 9+0)+1\\ &=2^2\cdot9+1\\ &=2^2(2\cdot4+1)+1\\ &=2^3\cdot4+2^2+1\\ &=2^3(2\cdot2+0)+2^2+1\\ &=2^4\cdot2+2^2+1\\ &=2^5+2^2+1\;. \end{align*}\etiqueta{1}$$

En otras palabras, que muestran cómo expresar $37$ como una suma de potencias de $2$, es decir, cómo escribir en binario (base dos) notación: $37=1\cdot2^5+0\cdot2^4+0\cdot2^3+1\cdot2^2+0\cdot2^1+1\cdot2^0$, por lo que en binario es $100101$.

Ahora lea el $\text{Remainder}$ columna de abajo a arriba: $100101$. Es exactamente el mismo. Y si se examina de cerca los cálculos en $(1)$ y pensar en cómo se relaciona con la tabla original, verás que esto siempre funciona: el $\text{Remainder}$ columna, leer de abajo a arriba, le da la representación binaria del número que está a la mitad.

Ahora, por fin, vamos a ver lo que está sucediendo en el $\text{Double}$ columna. Queremos $37\cdot15$. Ahora sabemos que $37=2^5+2^2+1$, por lo que

$$\begin{align*} 37\cdot 15&=(2^5+2^2+1)\cdot 15\\ &=2^5\cdot15+2^2\cdot15+1\cdot15\;. \end{align*}$$

Ahora $2^5\cdot15=\underbrace{2\cdot2\cdot2\cdot2\cdot2}_{5\text{ twos}}\cdot15$ es lo que usted consigue cuando usted haga doble $15$ cinco veces, $2^2\cdot15$ es lo que usted consigue cuando usted haga doble $15$ dos veces, y, por supuesto, $1\cdot15$ es más que el original de $15$. El $\text{Row}$ columna de la tabla muestra cómo muchos doblajes (y halvings) se han realizado para llegar a una fila determinada, por lo que son los números que he subrayado en el $\text{Double}$ columna. Por lo tanto,

$$\begin{align*} 37\cdot 15&=(2^5+2^2+1)\cdot 15\\ &=2^5\cdot15+2^2\cdot15+1\cdot15\\ &=480+60+15\\ &=555\;. \end{align*}$$

Observe que estos son también los números en la $\text{Double}$ columna adyacente a $1$'s de la $\text{Remainder}$ columna. Eso no es un accidente: los $1$'s mostró que los poderes de $2$ fueron necesarios para hacer el multiplicador $37$, y por lo tanto que compuesto doblajes de $15$ debe agregarse para obtener el producto.

La idea es el uso repetido de reducir a la mitad el multiplicador a escribir como una suma de potencias de dos, debido a la multiplicación de otro número, como $15$, por una potencia de $2$ es fácil: $2^na$ es lo que usted consigue cuando usted haga doble $a$ $n$ veces, y la duplicación es fácil. Los restos de la $1$ no están realmente perdidos: dicen que los poderes de $2$ son realmente necesarios en la representación binaria del multiplicador y así decirte que doblajes de los otros número deben ser sumadas para obtener el producto.

Answer 2

Este es un método para la multiplicación? Así, en el caso ideal, podemos precisamente a la mitad de un lado, y el doble de la otra:

$4\times120 = 2\times240 = 1\times480$

Sin embargo, en algunos casos, no podemos exactamente a la mitad, porque tenemos un número impar de reducir a la mitad. Podemos lidiar con esto por tener un resto:

$9\times60 = 4\times120 + 60$. Así, tenemos un adicional de 60 que no se trata - así que vamos a ignorarlo por ahora, van a seguir y agregar 60 para el resultado final más adelante.

Yo no soy exactamente claro acerca de su método, pero supongo que lo mejor sería como sigue:

$$\begin{array}{c} \text{Half}&&\text{Double}&\text{Remainder}\\ \hline 38&\times&15&\\ 19&\times&30&\\ 9&\times&60&30\\ 4&\times&120&60\\ 1&\times&480 \end{array}$$

Así, el resultado va a ser $38 \times 15 = 480 + 60 + 30 = 570$

Este algoritmo parece ser más rápido si se le reduce a la mitad el número más pequeño. Pero, esto nos lleva a dos problemas - 38 es más difícil de doble de 15 años (que sería el doble a un múltiplo de 10), y porque 15 es sólo uno por debajo de 16 (potencia de 2), es decir, tenemos un montón de desagradables restos:

$$\begin{array}{c} \text{Half}&&\text{Double}&\text{Remainder}\\ \hline 15&\times&38&\\ 7&\times&76&38\\ 3&\times&152&76\\ 1&\times&304&152\\ \end{array}$$

Me parece que lo hizo a un menor paso de trabajo. Pero, el resultado es $15 \times 38 = 308+154+76+38 = 570$. Puaj! De esta manera alrededor de no hacer que sea sencillo para calcular a mano.