domingo, 11 de diciembre de 2016

Algoritmo 'ruso' ( o de duplicación y mediación ) para multiplicar dos números naturales

ENUNCIADO. Aplicar el algoritmo ruso de la multiplicación para hallar el producto $p$ de $a=26$ por $b=13$

SOLUCIÓN.
Observemos que desarrollando en serie de potencias de base $2$ el segundo factor, $13$, obtenemos $$13=1\cdot 2^0+0\cdot 2^1+1\cdot 2^2 + 1\cdot 2^3$$ esto es $$13=1+0\cdot 2^1+1\cdot 2^2 + 1\cdot 2^3$$ luego el producto pedido es $$26\cdot 13=26 \cdot (1+0\cdot 2^1+1\cdot 2^2 + 1\cdot 2^3) =26+104+208=338$$ donde, en el último paso hemos empleado la propiedad distributiva de la multiplicación con respecto de la suma.

Organizaremos los cálculos de la siguiente forma
--------------------------------
 a=26           b=13    sumandos
--------------------------------
  26             13          
  13   impar     26         26 
   6             52         
   3   impar    104        104
   1   impar    208        208

                          =====
                        suma=338 ---> p
En la primera columna se anotan las mitades sucesivas, partiendo de $a$, y sin considerar el resto (de la división por $2$). En la segunda columna se anota si el número de la misma fila y de la primera columna es impar. En la tercera columna, y partiendo del segundo factor $b$, se van anotando el doble de los números que vamos obteniendo . Finalmente, en la cuarta columna, volvemos a escribir los números de la tercera, siempre que el numero de la primera y de la misma fila sea impar; éstos números son los que sumaremos para obtener $p$.

Así, pues, con la ayuda de dicha tabla, es fácil obtener el producto pedido, sin necesidad de recordar las tablas de multiplicar ( basta saber extraer la mitad ( mediar ), duplicar, y sumar ), así que, de manera muy mecánica, obtenemos $$a \cdot b = 26 \cdot 13 = 338$$

$\square$