The Gateway to Computer Science Excellence
0 votes
207 views
Write a function (proper programming code) for multiplying two integers without using '*' operator and considering all corner cases.
in Algorithm Challenges by Veteran (425k points) | 207 views
0
multiplication of two positive integers or general multiplication
0
general :)

2 Answers

+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)).

by Boss (38.5k points)
edited by
0
complexity?
+1
multiplication depends here on y so it should be O(y).rt sir ?
0
yes, can be optimized?
+1
yes may be by using shift operation .rt ?

I am figuring that out.
+1
Sir i think it will do in O(log(y)) time.

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);
}
+1
yes, in last recursive call, x+x rt?
+1
one more suggestion would be to swap x and y if x is lower than y.
0
and time complexity will be O(y) rt sir ?
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 Boss (11k points)
0
what's the complexity?
0
since addition take constant time..and the recursive calls depend upon b(multiplier)

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?
0
sir one thing:if we directly add b-1 times then it will be O(1)...
0
yes sir we can do better ..by right sifting we can half the calls each time ..this will save more time
0
@arjun sir.. for this we can do better if u apply shiftin on multiplier
0
yes, as given by Manojk. Can we do even better? Booth's algorithm?
0
yes sir with booths algo. it can be done in constant time
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,601 answers
195,856 comments
102,229 users