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.

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

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]

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

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]

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]

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.

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]

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.