Results 1 to 9 of 9

Math Help - Compute binary multiplication without multiplying

  1. #1
    Newbie
    Joined
    Mar 2014
    From
    Peru
    Posts
    4

    Compute binary multiplication without multiplying

    Hi all.

    As the tittle says, the problem is to find a way to compute the result of the multiplication of 2 binary variables without multiplying them.

    I have 2 binary variables X and Y, such that the summation tables is:

    X Y X+Y
    0 0 0
    0 1 1
    1 0 1
    1 1 2

    The subtraction table is:

    X Y X-Y
    0 0 0
    0 1 -1
    1 0 1
    1 1 0

    I want some way to compute their multiplication:

    X Y X*Y
    0 0 0
    0 1 0
    1 0 0
    1 1 1

    In order to achieve this, I can use summations, substractions, multiplication with constants and divisions by constants. The unique thing that I cannot do is to multiply the 2 variables directly. I was thinking hard how to solve the problem, but I cannot find the solution. Is possible to do something like that? or is it impossible?

    Thanks for the answers!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,932
    Thanks
    782

    Re: Compute binary multiplication without multiplying

    Add the first number to itself the number of times represented by the second variable. Then it is just summation.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2014
    From
    Peru
    Posts
    4

    Re: Compute binary multiplication without multiplying

    I cannot use a iterative structure. I just want a formula. Is it possible?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,932
    Thanks
    782

    Re: Compute binary multiplication without multiplying

    Can you use bit shift? Suppose you have 100101 * 1101. Then you want (100101 << 3 + 100101 << 2 + 100101 << 0). This is the same as (100101000 + 10010100 + 100101)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Mar 2014
    From
    Peru
    Posts
    4

    Re: Compute binary multiplication without multiplying

    Actually, I want to solve the problem for the values X in {0,1} and Y in {0,1}, i.e., just for 4 cases (the cases of the tables). And I cannot use bit shift.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,932
    Thanks
    782

    Re: Compute binary multiplication without multiplying

    Ok, then given x*y, if x=0, then the answer is zero. If x = 1, then add 0+y.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Mar 2014
    From
    Peru
    Posts
    4

    Re: Compute binary multiplication without multiplying

    But I just can use summations, substractions, multiplication with constants and divisions by constants. No iterative, no conditionals. I just want a formula, is it possible?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Mar 2014
    From
    lima
    Posts
    1

    Re: Compute binary multiplication without multiplying

    Here is a little proof that IT CAN NOT BE DONE finding that calculation

    Let suppouse by contradiction that it is possible to do it. Then, it exists
    ai, bi such that

    x*y = a1x + a2x + ..anx + b1y + ... + bmy

    Let A (B) the sum of the ai's (bi's), then

    x*y = Ax + By.

    When x=0, y=1, 0 = A0+By
    When x=1, y=0, 0 = Ax + B0

    Then, A=B=0, but when x=1, y=1, we have that
    1= x*y = 0x + 0y = 0. Contradicción.

    Open question, what about if x, y are in {0, 1, 2}, what about x, y in {0, 1, ...n}
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,414
    Thanks
    1853

    Re: Compute binary multiplication without multiplying

    You can define a binary operation in pretty much any way you like. Are you requiring that this be a ring? If so then the multiplication must be 0*0= 0, 0*1= 0, 1*0= 0, and 1*1= 1, in order to satisfy the distributive law.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: May 25th 2012, 04:14 PM
  2. Replies: 6
    Last Post: April 4th 2010, 05:29 PM
  3. Multiplying in GF(2)
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: February 8th 2010, 11:20 AM
  4. Multiplying CIS
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: November 5th 2009, 03:08 AM
  5. Replies: 0
    Last Post: April 7th 2008, 08:45 PM

Search Tags


/mathhelpforum @mathhelpforum