Prueba de multiplicación campesina rusa

Question

Estoy estudiando una combinatoria de texto (Cameron) en la preparación para tomar la matemática discreta este próximo semestre. Me he tomado una buena cantidad de matemáticas en la universidad, a través del Cálculo II, pero este es mi primer 500+ curso de matemáticas a nivel.

En el capítulo 2 de la Cameron libro, el autor presenta un algoritmo para la multiplicación se llama Campesina rusa de la Multiplicación. Quiero demostrar que este algoritmo el resultado será el producto de dos números.

He estado masticando en la prueba por un tiempo ahora, y sólo parece que no puede conseguir tracción. Gracias de antemano por cualquier ayuda.

Descripción del Algoritmo

Voy a tratar de explicar el algoritmo claramente. El objetivo del algoritmo es encontrar el producto de dos números de $m$$n$. La tabla de abajo se llena de $m$$n$:

$$\begin{array}{c} m&&n&\\ \hline \bigl\lfloor \frac{m}{2} \bigr\rfloor&& 2n \\ \bigl\lfloor \frac{m}{4} \bigr\rfloor&& 4n \\ \bigl\lfloor \frac{m}{8} \bigr\rfloor&& 8n \\ \bigl\lfloor \frac{m}{16} \bigr\rfloor&& 16n \\ \bigl\lfloor \frac{m}{32} \bigr\rfloor&& 32n \\ \end{array}$$

The sequence of numbers in both columns is the sequence $a_n = 2a_{n-1}\text{ donde }a_1=2$. The columns are extended down until the value in the left column is equal to the number one. After filling out the table, the product is found by adding the values of the right column where the left column is an odd number.

For example, to multiply 18 and 37 with the algorithm:

$$\begin{array}{c} m&&n&\\ \hline 18 && 37 \\ 9 && 74 \\ 4 && 148 \\ 2 && 296 \\ 1 && 592 \\ \end{matriz}$$

To find the product, cross out values of the left column where the value of the right column is even:

$$\begin{array}{c} m&&n&\\ \hline \require{enclose} \enclose{horizontalstrike}{18} && \enclose{horizontalstrike}{37} \\ 9 && 74 \\ \enclose{horizontalstrike}{4} && \enclose{horizontalstrike}{148} \\ \enclose{horizontalstrike}{2} && \enclose{horizontalstrike}{296} \\ 1 && 592 \\ \end{array}$$

And add the remaining numbers in the right column to get the result: $18\times37=74+592=666$

Alternate Description of Algorithm

As an aside, here is a shorter way to describe the algorithm, repeat the below steps until the left column == 1:

• Halve the last number in the first column
• Write the result below (discard the remainder)
• Double the last number in the first column.
• Write the result below.

Now, for every even number in the first column, delete the adjacent number in the second column. Add the remaining numbers in the second column.

What I've done so Far

I haven't been able to get much of anywhere on the proof. One thing I did was create a bit of a different way of arriving at the same outcome:

$$\begin{array}{c} m&&n&&\text{index}&&\text{remainder}&&\text{if remainder == 1, }n\times2^{Index}&\\ \hline 18 && 37 && 0 && 0 \\ 9 && 74 && 1 && 1 && 74\\ 4 && 148 && 2 && 0 \\ 2 && 296 && 3 && 0 \\ 1 && 592 && 4 && 1 && 592\\ \end{array}$$

Que trae a la luz la relación entre este algoritmo y los números binarios (la cuarta columna de la tabla anterior es el producto en binario, leer de abajo a arriba).

También escribí algunas funciones Python para que me ayude a explorar el problema, repo de Github.

Answer 1

Escriba $m$ en binario. Las líneas donde el número es impar corresponde a los bits $1$ en la expansión binaria. En tu ejemplo de $18 \times 37$ tenemos $18=10010_2=2^1+2^4,$ $18 \times 37=(2+16) \times 37$, que son exactamente los términos añadió.

Answer 2

Después de leer Ross Millikan respuesta que me decidí a escribir una evidencia completa. Este es mi intento:

Un número binario es una forma de expresar un número en potencias de dos, tomando la forma:

$$m = d_n2^{n-1}+d_{n-1}2^{n-2}+d_{n-2}2^{n-3}+...+d_{1}2^{0}$$

Where $n$ is the number of digits in the binary number. Therefore:

$$m\times n = \left[d_n2^{n-1}+d_{n-1}2^{n-2}+d_{n-2}2^{n-3}+...+d_{1}2^{0}\right]\times n$$

For example:

$$=18\times 37$$ $$\quad\;\;\;\;= \left[2^4+2\right]\times 37$$ $$\quad\;\;\;= \left[16+2\right]\times 37$$ $$\;= 592+74$$ $$666$$

The below table is a way of using this identity to multiply two numbers $m$ and $n$:

$$\begin{array}{c} \text{Index}&&m&&\text{If col. 1 is odd, }n\times 2^{Index}&\\ \hline 0 && m\\ 1 && \bigl\lfloor \frac{m}{2} \bigr\rfloor\\ 2 && \bigl\lfloor \frac{m}{4} \bigr\rfloor\\ 3 && \bigl\lfloor \frac{m}{8} \bigr\rfloor\\ 4 && \bigl\lfloor \frac{m}{16} \bigr\rfloor\\ 5 && \bigl\lfloor \frac{m}{32} \bigr\rfloor\\ \end{array}$$

Where the first column is the sequence of integers, the denominator in the second column is the sequence $a_n = 2a_{n-1}\text{ donde }a_1=2$. The summation of the third column is the product $m\times n$.

Que es equivalente a estos pasos: repetir los siguientes pasos hasta que la columna de la izquierda == 1:

• Halve the last number in the first column
• Write the result below (discard the remainder)
• Double the last number in the first column.
• Write the result below.

Ahora, para cada número en la primera columna, eliminar el adyacentes número en la segunda columna. Añadir el resto de los números de la segunda columna.