复数乘积仅使用三次乘法

Question

我们做复数乘法如下：

(a + i * b) * (c + i * d) = (a * c - b * d) + i * (a * d + b * c)

结果的实部和虚部是

real part = (a * c - b * d)
imag part = (a * d + b * c)

这涉及四次实数乘法。我们怎么能只用三次实数乘法呢？

Answer 1

您对两个数字感兴趣：A=ac−bd和B=ad+bc。计算三个实数乘法S1=ac，S2=bd和S3=(a+b)(c+d)。现在您可以将结果计算为A=S1−S2和B=S3−S1−S2。

此过程称为Karatsuba乘法，并在算法分析中大量使用。

它用于找到最接近的点对。

Answer 2

为了完整起见，我想指出Gauss' complex multiplication algorithm，这是另一种只用三次乘法进行复数乘法的方法。总结一下，你计算

k1 = c * (a + b)
k2 = a * (d - c)
k3 = b * (c + d)
Real part = k1 - k3
Imaginary part = k1 + k2

Answer 3

一些算法，例如Split-radix FFT对复数乘法设定了更高的期望，需要精确3次实数乘法和3次实数加法的复杂性。

(a+ib)(c+id)=ac−bd+i(ad+bc)    

x=a(c−d)
y=a+b
z=a−b
ac-bd=zd+x
ad+bc=yc−x

在FFT中，y和z完全来自旋转因子，因此它们可以预先计算并存储在查找表中。因此满足了要求。 FFT Tricks

Answer 4

Vallabh Patade已经回答了如何在两个复数之间执行产品，只有三个实数乘法。 Karatsuba算法的应用确实如下

x = a + i * b;
y = c + i * d;

real(x * y) = a * c - b * d;
imag(x * y) = (a + b) * (c + d) - a * c - b * d;

现在的问题是：我们能否在两个实数乘法少于三次的复数之间执行乘积？

答案是否定的，由威诺格拉德定理提供

S. Winograd, "On the number of multiplications required to compute certain functions", Commun. Pure Appl. Math. 23 (1970), 165-179.

在两个复数之间计算乘积所需的最小乘法数是3。