How can I minimize the number of supplements?

Question

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

For example: if the input has a value of 5 * 8, one of the following methods, you can add a larger number less times, and this will be the answer. But how can I minimize the number of supplements?

Answer 1

I like Codor's suggestion to use shifts and have zero extras!

But if you can really use additions and other operations, such as shifts, logs, subtractions, etc., I believe that the minimum number of additions to calculate a * b will be:

 min{int[log2(a+1)] + numbits(a), int[log2(b+1)] + numbits(b)} - 2 

Where

• numbits (n) is the number of units in binary representation of the integer n

  • For example, numbits (4) = 1, numbits (5) = 2, etc.

• int [x] - integer part of float x

  • For example, int [3.9] = 3

Now how did we get there? First look at your original example. You can combine groups together. For instance.

 8+8=16 16+16=32 32+8=40 

To summarize this, if you need to multiply b times, only using the additions that you used or the calculation results already calculated, you need:

• int [log2 (b + 1)] - 1 addition for calculating all the intermediate numbers you need 2 ^ na

  • In your example int [log2 (5 + 1)] - 1 = 2: you need 2 additions to calculate 16 and 32

• numbits (b) -1 additions to add all intermediate results together, where numbits (b) is the number of units in binary representation b.

  • In your example, 5 = 2 ^ 2 + 2 ^ 0, so numbits (5) -1 = 1: you need 1 add-on to make 32 + 8

I wonder what that means is your statement

 add the bigger number smaller number of times 

Not always a recipe for minimizing the number of additions.

For example, if you need to calculate 2 ^ 9 * (2 ^ 9 - 1), you are better off calculating additions based on (2 ^ 9-1) than 2 ^ 9, although 2 ^ 9 more. Fastest way:

 x = (2^9-1) + (2^9-1) 

And then

 x = x+x 

8 times for 9 supplements.

If instead you added 2 ^ 9 to yourself, you will need 8 additions to get all 2 ^ k * 2 ^ 9 first, and then an additional 8 additions to add all these numbers together for a total of 16 additions.

Answer 2

One strategy to reduce reduce the number of additions is to add elements hierarchically. This is the same strategy that is used in the classical power algorithm, which follows the same method of 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 replace it with the addition added above and get

 M = m2 + m2 + m2 + m2 

Then you can calculate m4 = m2 + m2 and come to

 M = m4 + m4 

So, the result is calculated in additions 3 instead of the original 8 . However, adding a value to itself can be replaced with a bit on the left by 1 (if enabled), this significantly reduces the number of additions.

This technique can be elegantly implemented by analyzing the binary representation of one of the animations (just like it is usually implemented in the power algorithm). For instance. if you need to calculate a * b , you can do it this way

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

The total number of additions used by such an implementation will be the total number of bits 1 in b . He will multiply 5 by 8 in 1 addition.

Note that to achieve the fewest additions provided by this strategy, multiplying a larger number by a smaller number is not necessarily the best idea. For instance. multiplying by 8 uses fewer additions than multiplying by 5 .

Answer 3

The best example would be 5 * 7 . This is essentially binary multiplication using old methods, but with a smart choice of multiplier.

If we can use a left shift and which is not considered an addition : choose a number with fewer bits as a multiplier. In this case, it will be 5 .

  111 x 101 ------ 111 000x <== This is not an addition, only a left shift 111xx ------- 100011 <== 2 additions totally. ------- 

If we cannot use the left shift : note that the left shift is the same as doubling / adding. Then we have to use a slightly different tactic. Since the animation will be shifted as many times as (position of MSB - 1) , the number of additions will be the number with the lower value (position of MSB - 1) + (number of bits set) . In the case of 5 * 8 values (3-1) + 2 = 4 and (4-1) = 3 respectively. Less for 8 and therefore use this as a multiplier.

  101 x 1000 ------- 000 000x <== left shift 000xx <== left shift 101xxx <== left shift -------- 101000 <== no addition needed, so 3 additions totally. -------- 

The above has three shifts and zero additions.

Answer 4

suppose that a needs to be multiplied by b, and we save the result in res, we add a to res only if b is odd, otherwise continue to divide b by 2 and multiply a by 2. This is done in a loop until b becomes 0 Multiplication and division can be done using the bitwise operator.

Let two given numbers be: 'a' and 'b' 1) Initialize the result of 'res' as 0. 2) Perform the following while' b 'is greater than 0 a) If' b 'is odd, add' a 'to' res' b) Double 'a' and half 'b' 3) Return 'res'.