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?

  • 3
    HINT Try using $(a+b) \cdot (c+d)$.2011-11-09
  • 0
    Thank you! But how can I apply this to the ordered pair? When I subtract the terms of the respective components of the pair like this: $((a+b)(c+d)-(ad+bc), (a+b)(c+d)-(ac+bd))$ the result would be correct, but that uses exactly twice as much operations as allowed.2011-11-09
  • 4
    @Zoidberg: you don't need to think of it as an ordered pair. You just need to produce the values of $ac+bd$ and $ad+cb$ with the given number of operations. So define $e=(a+b)(c+d)$ (which uses one multiply and two adds) and see if you can use the rest of the calculations given to get where you need to be. In particular, the sum of the two is exactly $e$, so if you can get one with the subtract left, you can do (ac+bd,e-(ac,bd))2011-11-09
  • 0
    @RossMillikan: Nice answer. The little typo may confuse the OP. So, to the OP you may wish to define $r=a.c+b.d$ and your answer is then ($r$,$e-r$).2011-11-09
  • 0
    @Swapan: Right you are. Thanks2011-11-09
  • 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."]

  • 1
    Note that besides saving a multiplication at the expense of a couple of "divide by 2" operations, there's also the change from 3 Adds, 1 Subtract to 3 Adds, 3 Subtracts.2011-11-09
  • 0
    Ah, I was answering the question in the subject, somehow missed the more specific goals of the body of the post. Still, usually these problems try to avoid multiplications because the cost of multiplication is much much higher than addition and subtraction and, hopefully, division by two.2011-11-09
  • 0
    I think that this question wasn't asked with optimization in mind, but thanks for this interesting answer, though. :)2011-11-10