CODEWITHSUNDEEP
algorithmmultiplicationaddition
KawaiKx
KawaiKx

Reputation: 9918

algorithm to simulate multiplication by addition

How to design an algorithm to simulate multiplication by addition. input two integers. they may be zero, positive or negative..

Upvotes: 2

Views: 10966

Answers (6)

Kyriet
Kyriet

Reputation: 421

I got here because I was looking for multiplication algorithm without using * operation. All I see here is just adding or subtracting number n-times. It's O(n) and it's ok, but...

If you have bitwise shift operations you can get O(log n) algorithm for multiplication.

Here is my pseudocode:

function mul(n, x)
    if n < 0 then   # 'n' cannot be negative
        n := -n
        x := -x
    endif

    y := 0
    while n != 0 do
        if n % 2 == 0 then
            x := x << 1     # x := x + x
            n := n >> 1     # n := n / 2
        else
            y := y + x
            x := x << 1     # x := x + x
            n := n - 1      # n := (n-1)/2
            n := n >> 1
        endif
    endwhile

    return y                # y = n * x
end

Remember that function above for mul(1000000, 2) is O(log 1000000) and for mul(2, 1000000) is only O(log 2).

Of course, you will get the same results, but keep in mind that the order of the parameters in function call does matter.

Edit: sidenote for using n % 2

Implementation of n % 2 using bitwise shift

It's pretty straightforward. First divide n by 2, then multiply n by 2 and check if n has changed. Pseudocode:

function is_even(n)
    n_original := n
    n := n >> 1        # n := n / 2
    n := n << 1        # n := n * 2
    if n = n_original then
        return true    # n is even
    else
        return false   # n is not even
    endif
end

Implementation of n % 2 using bitwise and

function is_even(n)
    if n and 1 = 0 then
        return true
    else
        return false
    endif
end

Upvotes: 0

Jonathan Ramos
Jonathan Ramos

Reputation: 2161

How about this for integers:

int multiply(int a, int b)
{
    int product = 0;
    int i;
    if ( b > 0 )
    {
        for(i = 0; i < b ; i++)
        {
            product += a;
        }
    }
    else
    {
        for(i = 0; i > b ; i--)
        {
            product -= a;
        }
    }

    return product;
}

Upvotes: 0

lokesh5790
lokesh5790

Reputation: 62

    mul(a,b)
    {
    sign1=sign2=1;
    if(a==0 || b==0)
return 0;
if(a<0){
    sign1=-1;
    a=-a;
    }
    if(b<0){
    sign2=-1;
    b=-b;
    }
    s=a;
    for(i=1;i<b;i++)
    s+=a;
    if(sign1==sign2)
    return s;
    else
    return -s;
    }

Upvotes: 0

jemmanuel
jemmanuel

Reputation: 476

val:= 0
bothNegative:=false

if(input1 < 0) && if(input2 < 0)
  bothNegative=true
if(bothNegative)
  smaller_number:=absolute_value_of(smaller_number)
for [i:=absolute_value_of(bigger_number);i!=0;i--]
do val+=smaller_number

return val;

Upvotes: 1

Dr. Acula
Dr. Acula

Reputation: 2422

def multiply(a, b):                                                                                                                                                               
    if (a == 1):
        return b
    elif (a == 0):
        return 0
    elif (a < 0):
        return -multiply(-a, b)
    else:
        return b + multiply(a - 1, b)

Upvotes: 10

Tudor Constantin
Tudor Constantin

Reputation: 26861

some pseudocode:

function multiply(x, y)
  if abs(x) = x and abs(y) = y or abs(x) <> x and abs(y) <> y then sign = 'plus'
  if abs(x) = x and abs(y) <> y or abs(x) <> x and abs(y) = y then sign = 'minus'

 res = 0
 for i = 0 to abs(y)
  res = res + abs(x)
 end

 if sign = 'plus' return res
    else return -1 * res

end function

Upvotes: 1

Related Questions