Algorithm for multiplying two numbers

Question

We have to multiply two numbers x and y but we cannot use * operator.

One simple way is to add x , y times OR add y, x times which is simple enough and is linear.

Second way is to pick any number(say x) and see which all bits are set in that number and if ith bit is set just do this:

product +=y<<i//product is 0 initially and do this for all i.

clearly for 32 bit numbers the loop runs 32 times and its time complexity is constant.

My question is , Is there any other way?Remember we cannot use *.

Solution 1

Assuming both numbers are unsigned one can do (this is more or less equivalent to your second way)

p = 0
while x > 0
    while x is even
        x = x / 2    // a shift right operation
        y = y + y    // a shift left operation
    x = x - 1
    p = p + y

The product is now in p.

To see why this is correct consider the invariant

product = p + x*y

it is maintained by all loops in the algorithm. We start with p = 0 so it is valid at the beginning and end when x = 0 so we must have product = p then.

Solution 2

On some architectures it is possible to get first/last bit set in a word with single instruction.

E.g. GCC has __builtin_clz (unsigned int x) which returns the number of leading 0-bits in X.

Or there is int ffs(int i) in strings.h which returns the position of the first (least significant) bit set in the word i.

Using one of those you can enumerate only set bits in a word. This can reduce number of iterations required.

#include <stdlib.h>
#include <stdio.h>
#include <strings.h>

int main(int argc, char** argv)
{
  if(argc >= 2) {
    int a = atoi(argv[1]);
    int b = atoi(argv[2]);
    printf("%i * %i = %i", a, b, a*b);
    int r = 0;
    while (a) {
      int i = ffs(a) - 1;
      a ^= 1<<i;
      r += b<<i;
    }
    printf(" = %i\n", r);
  }
}

With this code, multiplication 1048576 * 123 = 128974848 will be done in single iteration because 1048576 = 0x100000 has only one bit set.