Ejemplo de aplicación del algoritmo de multiplicación egipcio

A modo de ejemplo, vamos a calcular el producto $45\cdot 98$, para ello confeccionaremos una tabla con dos columnas; en la primera escribiremos las sucesivas potencias de $2$ ( empezando por $2^0=1$) y en la segunda la sucesión geométrica de razón $2$ cuyo primer término sea el segundo factor:

1  |   98
 2  |  196
 4  |  392
 8  |  784
16  | 1568
32  | 3136
.   |   .
.   |   .
.   |   .

A continuación, expresaremos el primer factor como suma de potencias de base $2$ ( los números de la primera columna ) y seleccionaremos las filas en las que se encuentran. Sumando, finalmente, los números de la segunda columna que estén en esas mismas filas, llegando así al resultado de la multiplicación pedida.

Para saber qué números de la primera columna intervienen como sumandos del número $45$ ( siendo éstos potencias de base $2$ ) escribiremos $45$ en la base de numeración $2$ ( binaria ), dividiendo sucesivamente por $2$ el número y los cocientes que se van obteniendo hasta llegar a una división con resto $0$; los números así obtenidos, incluyendo el cociente de la última división, y dispuestos en orden, comenzando con el cociente de la última división y acabando con el resto de la primera, son los coeficientes del desarrollo en serie de $45$ en suma de términos de potencias de base $2$, esto es,
$45_{(10)}=101101_{(2)}$, luego
$45=1\cdot 2^0+0\cdot 2^1+1\cdot 2^2+1\cdot 2^3+0\cdot 2^4+1\cdot 2^5$
            $=1+4+8+32$

Así pues, seleccionando los números de la segunda columna con los que se emparejan:

 1  |   98 | x
 2  |  196 |
 4  |  392 | x
 8  |  784 | x
16  | 1568 |
32  | 3136 | x

obtenemos, como resultado de la multiplicación pedida el siguiente resultado: $$98+392+784+3136 = 4410$$
$\square$

Expresando un número entero no negativo como suma de potencias de base 2

ENUNCIADO. Expresar el número $493$ como una suma de potencias de base $2$

SOLUCIÓN. $496_{(10)}=11101101_{(2)}$, luego
$493=1\cdot 2^0+0\cdot 2^1+1\cdot 2^2+1\cdot 2^3+0\cdot 2^4+1\cdot 2^5+1\cdot 2^6+1\cdot 2^7+1\cdot 2^8$
            $=1+0+4+8+0+32+64+128+256$

$\square$

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$