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 乘法，在算法分析中大量使用。

它用于寻找最近的一对点。