algorithm - 复数乘积仅使用三个乘法

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 的复数乘法算法，这是另一种只用三个乘法进行复数乘法的方法。总而言之，您计算

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

Answer 3

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;

现在的问题是：我们可以用少于三个实数乘法的两个复数进行乘积吗？

答案是否定的，由Winograd 定理提供

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

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

Answer 4

一些算法，例如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技巧

Answer 5

如果您想混合加法和乘法，Winograd 实际上是正确的。但是，如果您只想进行复数乘法，请使用对数极坐标表示，即乘法只是添加对数幅度和角度；但当然 logpolar 添加很难！Logpolar 可以很好地用于有限精度的 FFT，例如微处理器上的 8 位对数幅度 +j8 位相位。