multiplication of two positive integers or general multiplication

The Gateway to Computer Science Excellence

+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?

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,645 questions

56,601 answers

195,856 comments

102,229 users