in Algorithm Challenges
1,210 views
0 votes
0 votes
Write a function (proper programming code) for multiplying two integers without using '*' operator and considering all corner cases.
in Algorithm Challenges
by
1.2k views

2 Comments

multiplication of two positive integers or general multiplication
0
0
general :)
0
0

2 Answers

2 votes
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)).

edited by

4 Comments

yes, in last recursive call, x+x rt?
1
1
one more suggestion would be to swap x and y if x is lower than y.
1
1
and time complexity will be O(y) rt sir ?
0
0
0 votes
0 votes
let two numbers be a and b

mul(a,b)={ 0   if b=0

                a+mul(a,b-1)   if b>0

                   mul(-a,-b) if b<0
by

4 Comments

@arjun sir.. for this we can do better if u apply shiftin on multiplier
0
0
yes, as given by Manojk. Can we do even better? Booth's algorithm?
0
0
yes sir with booths algo. it can be done in constant time
0
0

Related questions