2
$\begingroup$

I have an ordered pair $(ac+bd, ad+cb)$ where $a$, $b$, $c$ and $d$ are natural numbers. How can I rearrange that pair, so that exactly 3 multiplications, 3 additions and 1 subtraction are used?

I tried to place some of the factors outside the brackets for each component of the pair, but that always involves a division. I think that I have to add additional variables somehow, but I have no idea how to do that.

Can you give me a hint?

  • 0
    Great! Thank you very much for your help, Ross, Srivatsan and Swapan!2011-11-10

1 Answers 1

2

[Not an answer to the exact question above, which was answered in comments, but an additional optimization.]

If division by $2$ is considered "easy," you can do it in two multiplications.

Specifically:

$(a+b)(c+d)+(a-b)(c-d) = 2(ac+bd)$ and $(a+b)(c+d)-(a-b)(c-d)=2(ad+bc)$

So you only need to compute the multiplications $(a+b)(c+d)$ and $(a-b)(c-d)$ (if division by 2 is "easy.")

Otherwise, use the method in the comments above.

[I got this answer by considering your output as the output of a matrix multiplication of the $2\times 2$ matrix $A=[a,b;b,a]$ with the column vector $(c,d)^T$. I then found the eigenvectors of $A$ to be $v_1=(1,1)^T$ and $v_2=(1,-1)^T$ with corresponding eigenvlues $a+b$ and $a-b$. Then I wrote $(c,d)^T=\frac{c+d}{2}v_1 + \frac{c-d}{2}v_2.$ In retrospect, the answer is obvious, but often faster computations are found this way - representation as a linear algebra computation, then using eigenvalues and eigenvectors to "simplify."]

  • 0
    I think that this question wasn't asked with optimization in mind, but thanks for this interesting answer, though. :)2011-11-10