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 *.

Depending on how sensitive you are to precision and what number representation you're allowed to use, you might just do x / (1 / y) — polettix, Jan 09 '16 at 10:12
That won't work for integral types, polettix, unless you're willing to tweak it to do floating point operations (which can introduce loss of precision). — Peter, Jan 09 '16 at 10:31
@SumeetSingh I would suggest to update the question too, then. — polettix, Jan 23 '16 at 16:45

Henry · Accepted Answer · 2016-01-09T10:43:03.973

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.

score 1 · Answer 2 · edited May 23 '17 at 10:27

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.

score 0 · Answer 3 · answered Jan 09 '16 at 13:42

To multiply without *

Solution 1 with integers:

I assume you can use +

Do a loop: x + x + .. + x (y times). or y + ... + y (x times).

Solution 2:

decompose everything, keep a table of x*y for every figure 0-9, and reproduce manual operations, like in elementary school.

Solution 3: combines the two others and most simple and robust:

For integers: do it in binary

13 * 7 :

1101 * 111 = 1101 + 11010 + 110100 = 1011011 = 91

Processors work like that. there is no +, only binary operations (and,or,xor)

For non integers : do it in with integers managing the 0s

For negative numbers: same thing, manage +/-

time complexity is constant with 32 bits: this is irrelevant because everything is constant.

time complexity in general: binary operations are rather efficient:

number of bits = O(log n)

=> x*y => O(log x) * O(log y)

"there is no +, only binary operations (and,or,xor)": what do you mean by this? All processors I know have an `add` machine instruction. — Henry, Jan 09 '16 at 18:05
@Henry "add" machine instruction is a conjunction of binary operations for integer (typically 8/16/32/64 bits), or floating point operations with co-processor, or specific hardware, micro-code or more subtle algos. — guillaume girod-vitouchkina, Jan 09 '16 at 21:00

Algorithm for multiplying two numbers

3 Answers3