仅使用三个乘法的复数乘积

一尘不染

algorithm

我们进行复数乘法，如下所示：

(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)

这涉及四个实数乘法。仅用三个实数乘法怎么办？

阅读 354

2020-07-28

共1个答案

一尘不染

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

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

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

2020-07-28