multiplication of two positive integers or general multiplication

The Gateway to Computer Science Excellence

0 votes

Write a function (proper programming code) for multiplying two integers without using '*' operator and considering all corner cases.

+2 votes

One of possible case for multiplying two integers without using '*' operator.
**Case:1 Recursively add x y time.**

int mul(int x, int y)

{

if(y == 0 || x==0)

return 0;

if(y > 0 )

return (x + mul(x, y-1));

if(y < 0 )

return mul(-x, -y);

}

**Time complexity of above function is O(y).**

**case 2:swap x and y if x is lower than y.**

int mul(int x,int y,int mult){

if(y==0)

return mult;

if(y<0){

x=-x;

y=-y;

}

return mul(x,y-1,mult+x);

}

**Case 3:We have alternative which is optimal.**

mul(x,y)

{

if(x==0||y==0)

return 0;

if (y == 1)

return x;

if (y % 2 == 0)

return mul(x + x, y >> 1);

else

return x + mul(x + x, y >> 1);

}

**Time complexity of this function is O(log(y)).**

0 votes

0

since addition take constant time..and the recursive calls depend upon b(multiplier)

so it will be O(b)

so it will be O(b)

0

yes, say if we have about 1000 multiplications and for b = 1000,000 it takes hours to do this. Can we do better?

52,345 questions

60,471 answers

201,798 comments

95,274 users