A simple complex problem

[Yoruichi-san]

I couldn't resist responding to happy chance...;P Not my own creation, but you don't need to know too about complex numbers to solve it, just the basic definition of i =sqrt(-1) should suffice.

So the straightforward method of computing the product (a+bi)(c+di) = (ac-bd)+i(bc+ad) requires four (real) multiplications and two additions. However, most computers require a significantly more time to compute multiplication than addition. Find an algorithm for computing (a+bi)(c+di) with only three multiplications.

Edited May 12, 2012 by rookie1ja

[bonanova]

I can't do spoilers on iPad, but this answer is a bit of hoax, I judge.

So showing it doesn't disclose the real (npi) solution.

  Reveal hidden contents

Normalizing the two numbers WRT their real parts reduces the multiplications to two.

Of course, it ALSO requires two divisions, hardly creating a more efficient algorithm.

a+bi x c+di = ac-bd +i (ad+bc) - four multiplications.

Normalize 

a+bi = a(1+Bi). 

c+di = c(1+Di)

Product = ac[1-BD +i(B+D)] - two multiplications.

[Yoruichi-san]

Thanks, rookie!

Bonanova: lol, clever. Yeah, division pretty much counts as multiplication (of the inverse), and subtraction counts as addition (of the negative)

[bonanova]

To stretch the point, if you convert to polar coordinates (a mere 4 squares, 2 additions, 2 square roots and 2 arc tangents, it'll take only 1 multiplication and 1 addition.

Well, to recover a Cartesian result, add on 1 sine, 1 cosines and 2 more multiplications. Still only 3 multiplications instead of 4.

[bonanova]

OK I think it can be done, but it will cost you

  Reveal hidden contents

Let r₁ = ac, r₂ = bd. Two multiplications so far.

(a+bi)(c+di) = (r₁-r₂) + {(a+b)(c+d)-(r₁+r₂}i Third multiplication.

[Yoruichi-san]

  On 5/13/2012 at 8:44 PM, bonanova said:

OK I think it can be done, but it will cost you

  Reveal hidden contents

Let r₁ = ac, r₂ = bd. Two multiplications so far.

(a+bi)(c+di) = (r₁-r₂) + {(a+b)(c+d)-(r₁+r₂}i Third multiplication.

Yep, I think that is the solution, its the one I got, too. Like I said, I didn't create this problem, and I don't know that much about computers. But I think the point was that additions take, like, nearly an order of magnitude less than multiplication.

As for polar coordinates...this problem was actually suppose to be simple ;P.

[bonanova]

  On 5/13/2012 at 9:18 PM, Yoruichi-san said:

As for polar coordinates...this problem was actually suppose to be simple ;P.

Back in the day, swapping x <---> + in computations made a difference.

p.c. Answer was just using time while I worked on the real answer .

[Morningstar]

  On 5/13/2012 at 1:58 AM, bonanova said:

I can't do spoilers on iPad, but this answer is a bit of hoax, I judge.

So showing it doesn't disclose the real (npi) solution.

  Reveal hidden contents

Normalizing the two numbers WRT their real parts reduces the multiplications to two.

Of course, it ALSO requires two divisions, hardly creating a more efficient algorithm.

a+bi x c+di = ac-bd +i (ad+bc) - four multiplications.

Normalize

a+bi = a(1+Bi).

c+di = c(1+Di)

Product = ac[1-BD +i(B+D)] - two multiplications.

What does WRT mean?

Also, how does a+bi = a(1+bi)?

[Yoruichi-san]

  On 6/7/2012 at 1:59 PM, Morningstar said:

What does WRT mean?

Also, how does a+bi = a(1+bi)?

[With Respect To] and it's a+bi=a(1+Bi), where B=b/a. It's common for mathematicians to use capital letter to represent a newly defined coefficient that is related to, but not equal to, the old coefficient.