Multiplicación a la Russe en C

Existen varios algoritmos para la multiplicación. Uno bastante curioso y sorprendente es el de la multiplicación a la russe. Este algoritmo no es que sea muy didáctico, de hecho no se enseña en los colegios, puesto que tan solo requiere dividir y multiplicar por 2. En escencia, saberse la tabla del 2, y por supuesto, saber sumar, ¡y funciona!.

Algoritmo y ejemplo

Lo mejor para entender como funciona el algoritmo es un ejemplo. Vamos a multiplicar 35*91: el resultado debe ser de 3185.

Lo que se hace es coger el multiplicando y dividirlo por 2 mientras el resultado sea mayor a 1. Con el multiplicador se hace los contrario, se multiplica por 2. Los números que se suman son aquellas partes derechas en las que la parte izquierda sea impar. Dicho de otro modo, se suman aquellos números de la columna de multiplicaciones en los que la columna de divisiones sea impar.

Un pseudocódigo sería algo así:

russe(x, y) begin   while (x >= 1) do     if (x mod 2) then        mult = mult + y;     endif     x = x/2;      y = y*2;   end   return mult; end

Implementación en C

Resulta tentador implementar un algoritmo así. Es muy sencillo. Si tenemos en cuenta que las multiplicaciones y divisiones por 2 se hacen mediante desplazamientos a izquierda y a derecha respectivamente, resulta muy fácil.

Una mejora a esto es poner el número más pequeño como multiplicando, puesto que así nos podemos ahorrar algunas iteraciones.

_______________________________________________________

/* russe.c -- algoritmo de multiplicación a la russe
 * date: sáb jul 24 09:34:54 WEST 2010
 * Author: Juan José Fumero Alfonso
 * Compile: gcc russe.c -O3 -o russe
 */

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>  /* getopt */

#define AUTHOR "Juan José Fumero Alfonso"

void author () {
 printf ("Author: %s\n", AUTHOR);
}

void version () {
 printf ("Multiplicación a la Russe, version 0.2\n");
}

void help () {
 printf ("Use mode: \n");
 printf ("\t$ ./russe -[-hva] x <number1> -y <number2>  \n");
 printf ("\t-v: print version\n");
 printf ("\t-a: print author\n");
 printf ("\t-h: show this help\n");
}

/* Función con que realiza la multicación a la russe */
int mrusse (int auxa, int auxb) {
  int mult = 0;
  while (auxa >= 1) {
    if ((auxa % 2) == 1)  {
      mult += auxb;
    }
    auxa = auxa >> 1;
    auxb = auxb << 1;
 }
 return mult;
}

/* Entrada de los dos número a multiplicar desde la línea de 
 * comandos
 */
int main (int argc, char **argv) {
 /* Recogida ie números */
 int x, y;
 int flgn1 = 0, flgn2 = 0;
 int opt;
    while ((opt = getopt(argc, argv, ":havx:y:")) != -1) {
      switch (opt) {
        case 'h': 
           help();
          return 0;
          break;
        case 'v': 
          version();
          return 0;
          break;
        case 'a':
          author();
          return 0;
          break;
        case 'x': /* recogida de números */
         flgn1 = 1;
         x = atoi(optarg);
         break;
       case 'y': /* recogida de números */
         flgn2 = 1;
         y = atoi(optarg);
       break;
         default: /* '?' */
         help();
         exit(EXIT_FAILURE);
     }
  }
  if ((flgn1 == 0) && (flgn2 == 0)) {
     fprintf (stderr, "Error in numbers\n");
     return -1;
  } 
  int mult = mrusse(x, y);
  printf ("\t%i * %i = %i\n", x, y, mult);
  return 0;
}

_______________________________________________________

La función principal es mrusse, que es la que hace la multiplicación por software. El resto es sólo para permitir diversas opciones de entrada al programa. Modo de uso:

$ ./russe -x 35 -y 91

Use la opción -h para la ayuda.