How can I minimise number of additions?

Question

Multiply two numbers without using * operator, and with minimum number of additions

For eg: If input is, 5*8, one of the following ways, can be add the bigger number smaller number of times, and that will be the answer. But how can I minimise the number of additions?

Answer 1

One strategy to minimize reduce the number of additions is to add things hierarchically. This is the same strategy that is used in the classic power algorithm, which follows the same technique for minimizing the number of multiplications.

Let's say you need

M = a * 8 = a + a + a + a + a + a + a + a

Once you calculate m2 = a + a, you can substitute it into the above addition and get

M = m2 + m2 + m2 + m2

Then you can calculate m4 = m2 + m2 and arrive at

M = m4 + m4

So, the result is calculated in 3 additions instead of the original 8. However, adding a value to itself can be replaced by a left-shift by 1 bit (if this is allowed), this greatly reducing the number of additions.

This technique can be elegantly implemented through analyzing the binary representation of one of the multiplicands (exactly as it is typically implemented in the power algorithm). E.g. if you need to calculate a * b you can do it in this fashion

int M = 0;
for (int m = a; b != 0; b >>= 1, m <<= 1)
  if ((b & 1) != 0)      
    M += m;

The total number of additions such implementation will use is the total number of 1 bits in b. It will multiply 5 by 8 in 1 addition.

Note that in order to achieve the lowest the number of additions provided by this strategy, multiplying larger number by smaller number is not necessarily the best idea. E.g. multiplying by 8 uses less additions than multiplying by 5.