Algoritmo de la multiplicación rusa. Un ejemplo

Realícese la multiplicación $45\cdot 98$ empleando el algoritmo 'ruso'

procedimiento multiplicación_rusa(a,b)
inicio
{
 i:=1;
 a_i:=a;
 b_i:=b;
 p:=0;
 mientras a_i!=1 hacer
  {
   i:=i+1;
   a_i:=entero_por_defecto(a_i/2);
   b_i:=2·b_i
   si resto(a_i div 2 ) != 0, p:=p+b_i
  }
 escribir('a·b=',p);
}
fin

Ejemplo de implementación:

% multiplicación_rusa(45,98)
salida:
->  45·98=4410

Proceso paso a paso:

------------------------------------------------------------------
  i  |  a_i    | ¿ a_i es impar ?   |   b_i   |  si a_i es impar
     |         |                    |         |   acumula suma de
     |         |                    |         |   b_i  
------------------------------------------------------------------
  1  |  45     |      sí            |    98   |       98
------------------------------------------------------------------
  2  |  22     |      no            |   196   |       98
------------------------------------------------------------------
  3  |  11     |      sí            |   392   |   98+392=490
------------------------------------------------------------------
  4  |   5     |      sí            |   784   |  490+784=1274
------------------------------------------------------------------
  5  |   2     |      no            |  1568   |      1274
------------------------------------------------------------------
  6  |   1     |      sí            |  3136   | 1274+3136=4410
------------------------------------------------------------------

$\square$

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$