Skip to content

Latest commit

 

History

History
17 lines (13 loc) · 1.31 KB

complexMult.md

File metadata and controls

17 lines (13 loc) · 1.31 KB

On the complex number multiplication using one less submultiplication

Given two complex numbers a + bi and c + di, the product of the two is (ac - bd) + (ad + bc)i. Even when this approach is straightforward, it requires four submultiplications (ac, ad, bc, bd) to achieve the result. It is known that multiplications are, to some extent, more expensive than sums. So, in order to reduce algorithm's time complexity, we could increase the amount of sums we make with the terms (a, b, c, d) if that does represent a decrease in the amount of submultiplications.

Let's define the sums:

S1 = d - c
S2 = a + b
S3 = d + c
And the submultiplications:
P1 = aS1
P2 = cS2
P3 = bS3

We then calculate P1 + P2 = ad - ac + ac + bc = ad + bc = Im{R} and P2 - P3 = ac + bc - bd - bc = ac - bd = Re{R}. So R = (P2 - P3) + (P1 + P2)i, and we taxed our CPU with only three submultiplications.