Question

Implement (provide pseudocode) the 'A la Russe' algorithm which does not use arrays.

Answer 1

PSEUDOCODE

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

Example

CODE IN C

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

void help () {
 printf ("Use mode: 
");
 printf ("      $ ./russe -[-hva] x <number1> -y <number2>  
");
 printf ("      -h: show this help
");
}

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;
}

int main (int argc, char **argv) {
 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 'x': 
         flgn1 = 1;
         x = atoi(optarg);
         break;
       case 'y': 
         flgn2 = 1;
         y = atoi(optarg);
       break;
         default: /* '?' */
         help();
         exit(EXIT_FAILURE);
     }
  }
  if ((flgn1 == 0) && (flgn2 == 0)) {
     fprintf (stderr, "Error in numbers
");
     return -1;
  } 
  int mult = mrusse(x, y);
  printf ("     %i * %i = %i
", x, y, mult);
  return 0;
}

OUTPUT

$ ./russe -x 35 -y 91