How to perform a multiplication using only additions and assignments?

Viewed 1175

How do I change the following program, so that it performs the same Task, but using only additions and assignments?

I can only do max 27 additions, and the Output has to be generated in a single Input. Loops and other control flow operations are not allowed

#include <iostream>

int main()
{
    int a;
    std::cout << "Enter number: ";
    std::cin >> a;

    std::cout << a*29 << std::endl;

    return 0;
}
9 Answers

Another approach that requires 7 +:

int M1  = a;        // 1a
int M2  = M1 + M1;  // 2a
int M4  = M2 + M2;  // 4a
int M8  = M4 + M4;  // 8a
int M16 = M8 + M8;  // 16a
int res = M16 + M8 + M4 + M1; // 29a

The result is constructed from the binary pattern of the multiplier, i.e. 29 decimal is 0001.1101 binary. So we need to add M16, M8, M4 and M1 (and exclude M2).

This is not general, and it cannot be, but to multiply just by 29 you can do this:

// x is input
int t = x;  // x*1
x = x + x;
x = x + x;
t = t + x;  // x*5
x = x + x;
t = t + x;  // x*13
x = x + x;
t = t + x;  // x*29

This is just unrolled binary multiplication, like the similar answers, but without naming the temporary results. The additions to t correspond to the set bits in 29.

This way you can do it with 21 additions.

#include <iostream>

int main()
{
    int a;
    std::cout << "Enter number: ";
    std::cin >> a;
    int b = (a+a+...+a) // 10 times
    b = b + b;
    b = b + (a + a + a ... + a ); // 9 times
    std::cout << b << std::endl;

    return 0;
}

Can you use an additional var?

b = a + a + a//3 times a 
b = b + b + b//9 times a
b = b + b + b//27 times a
b = b + a + a//29 times a

Multiplication is just a repeated addition. Use a loop for this. Do you know how many times your loop should execute? Yes! So use a for loop.

So here is the plan:

  1. Get input
  2. Use a for loop to perform the addition
  3. Output sum

Example:

// get input
int input;
std::cout << "Enter number: ";
std::cin >> input;

// use a for loop to perform the addition
int sum = 0;
for(int i = 0; i< 29; ++i)
    sum += a;

// output result
std::cout << sum << std::endl;

,resRepetitive addition is multiplication -- mathematically

So repeat addition of a for n number of times. A simple for/while loop can do this

#include <iostream>

int main()
{
    int a,i,temp=0;
    std::cout << "Enter number: ";
    std::cin >> a;
    for(i=1;i<=29;i++)
        temp+=a;//add a repeatedly for 'n' number of times. Here 29 as per your requirement. a*n  
    std::cout << temp <<std::endl; 
    return 0;
}

Without loop

int b=0,result=0;
b=a+a+a+a+a+a+a;\\adding for 7 times
result=b+b+b+b+a;\\4 times 7 (of a)= 28+a= 29 times (of a).

This involves 10 addition.

If you are only allowed to use + and =, and are not allowed to cheat by introducing other variables, there is no way of doing this unless you indulge in a bit of undefined behaviour and allow yourself something of the form

... + (a += ...) + ...

where ... is any number of a +. The trick here is that (a += ...) changes the value of a part way through evaluation of the expression.

Tempting as it may be, alas this is not portable C++ since += and + are not sequencing points. On your classroom compiler, you might be able to get this to work.

See https://ideone.com/fC3fai, you can see that

(a + a + a + a + a + (a += a + a + a) + a + a + a + a + a)

does the job on that particular compiler (at the time of writing). (For what it's worth, it also does the correct thing in Java where the expression is well-defined).

You can try this -

b = a + a + a + a + a + a + a + a + a + a + a + a + a + a + a; // equivalent to a*15

b += b -a;

You can add value multiple times:

int sum=0;
for(int i=0; i<multipler; i++){
    sum+=a; //adds value of a to itself
}
return sum;

If you want to multiple only by 2 you can just shift left:

a = a << 1;
Related