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!!

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.

Re: Compute binary multiplication without multiplying

I cannot use a iterative structure. I just want a formula. Is it possible?

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)

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.

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.

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?

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}

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.