# Compute binary multiplication without multiplying

• Mar 20th 2014, 01:29 PM
mijail
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?

• Mar 20th 2014, 01:41 PM
SlipEternal
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.
• Mar 20th 2014, 01:45 PM
mijail
Re: Compute binary multiplication without multiplying
I cannot use a iterative structure. I just want a formula. Is it possible?
• Mar 20th 2014, 01:55 PM
SlipEternal
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)
• Mar 20th 2014, 02:12 PM
mijail
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.
• Mar 20th 2014, 02:16 PM
SlipEternal
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.
• Mar 20th 2014, 03:54 PM
mijail
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?
• Mar 20th 2014, 05:45 PM
juangutierrez
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}
• Mar 21st 2014, 05:19 AM
HallsofIvy
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.