# multiplying two numbers without multiplication operator

#### Kittu20

Joined Oct 12, 2022
434
I can multiply two numbers without using multiplication operator in c. I know that in recursion we call function inside function. I don't understand the recursion method for multiplying two numbers.

C:
#include<stdio.h>

int main()
{
int x = 2;
int y = 4;
int mul = 0;

// x = 0 + 2 = 2
// x = 2 + 2 = 4
// x = 4 + 2 = 6
// x = 6 + 2 = 8

for (int i = 0; i < y; i++)
{
mul = (mul + x);
}

printf("%d", mul);

return 0;
}
https://www.geeksforgeeks.org/multi...iply-division-bitwise-operators-and-no-loops/

can someone explain math for multiplying two numbers using recursion ?

#### Papabravo

Joined Feb 24, 2006
20,626
Multiplication is just a shorthand for repeated addition of a number to itself a prescribed number of times. Similarly, division can be decomposed into repeated subtractions.

As a side note, the code fragment is NOT an example of a recursive procedure. It is just a simple looping construct. Recursion would invove repeated calls by a function to itself. Computing factorials in this manner is a classic example.

Here is the pseudo code for it:

Recursive Factorial Procdure:
fac ≔ proc(n) local s;
if n=0 then s≔ 1 else s≔ n*fac(n-1) end if;
return s;
end proc:
Notice how the function calls itself in the else part of the conditional 'if' statement. Each call results in a completely new stack frame for the function and when the top level return is executed the value return will be the required answer.

Last edited:

#### DickCappels

Joined Aug 21, 2008
10,104
But...your looping structure is the right idea for multiplication. Have you tested it yet?

#### WBahn

Joined Mar 31, 2012
29,535
I can multiply two numbers without using multiplication operator in c. I know that in recursion we call function inside function. I don't understand the recursion method for multiplying two numbers.

C:
#include<stdio.h>

int main()
{
int x = 2;
int y = 4;
int mul = 0;

// x = 0 + 2 = 2
// x = 2 + 2 = 4
// x = 4 + 2 = 6
// x = 6 + 2 = 8

for (int i = 0; i < y; i++)
{
mul = (mul + x);
}

printf("%d", mul);

return 0;
}
https://www.geeksforgeeks.org/multi...iply-division-bitwise-operators-and-no-loops/

can someone explain math for multiplying two numbers using recursion ?
Your code does not scale well to large numbers. The number of times that your loop executes is equal to y. If you use your loop to multiply two two-digit numbers together, it will take a certain amount of time. If you then use it to multiply two three-digit numbers together, it will take, on average, ten times as long. By the time you get to multiplying two ten-digit numbers together, it is taking a billion times as long. Now consider how long it takes a human to multiply two ten-digit numbers together compared to two two-digit numbers -- perhaps fifty times as long. Ask a human to multiply two 20-digit numbers together, and they'll slog it out in about half an hour, while your program will likely take several thousand years.

As for the recursive approach, which is a REALLY poor use of recursion, the underlying math is simple.

z = x*y = x(1 + y - 1) = x*1 + x*(y-1) = x + x*(y-1)

When do you stop?

If y = 0, the result is simply 0.

This approach requires that y be a non-negative integer. We can relax the non-negative requirement by noting that x*y = -x(-y) and use that as our first check to get the ball rolling with a non-negative y.

As for dealing with non-integer values -- that's a completely different problem. The notion that multiplication is repeated addition runs into difficult when asked to multiply x by itself 3.872 times.

#### ApacheKid

Joined Jan 12, 2015
1,274
I can multiply two numbers without using multiplication operator in c. I know that in recursion we call function inside function. I don't understand the recursion method for multiplying two numbers.

C:
#include<stdio.h>

int main()
{
int x = 2;
int y = 4;
int mul = 0;

// x = 0 + 2 = 2
// x = 2 + 2 = 4
// x = 4 + 2 = 6
// x = 6 + 2 = 8

for (int i = 0; i < y; i++)
{
mul = (mul + x);
}

printf("%d", mul);

return 0;
}
https://www.geeksforgeeks.org/multi...iply-division-bitwise-operators-and-no-loops/

can someone explain math for multiplying two numbers using recursion ?
How big can the numbers get? A 2D array will work, just populate it with the products of integer pairs and you're done. You can save space too by recognizing that 2*3 is the same as 3*2 and so on. This approach has constant cost too, 3*4 is "computed" in the time same as 234*75.

#### WBahn

Joined Mar 31, 2012
29,535
How big can the numbers get? A 2D array will work, just populate it with the products of integer pairs and you're done. You can save space too by recognizing that 2*3 is the same as 3*2 and so on. This approach has constant cost too, 3*4 is "computed" in the time same as 234*75.
This approach becomes untenable long before the loop approach does. Just to deal with 16-bit x 16-bit numbers would result in an 8 GB table, even after exploiting symmetry.

#### ApacheKid

Joined Jan 12, 2015
1,274
This approach becomes untenable long before the loop approach does. Just to deal with 16-bit x 16-bit numbers would result in an 8 GB table, even after exploiting symmetry.
Indeed, I asked about the desired range too. I thought it helpful to show the OP there are often unconventional ways to look at these kinds of problem.