Add the first number to itself the number of times represented by the second variable. Then it is just summation.
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!!
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}
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.