复数乘积仅使用三次乘法

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

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

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

这是高斯的，不是唐叶的。Karatsuba 乘法用于两个双精度整数的四精度乘积。1960 年，当这一点被发现时，计算机中的乘法是一种由移位和加法组成的缓慢运算——一个 32 位整数需要 32 次这样的运算，就像俄罗斯农民的乘法一样。是的，高斯和唐叶的程序非常相似，但目标不同。Karatsuba 可以递归地应用于更大的问题；不是高斯。 (2认同)

Answer 2

为了完整起见,我想指出高斯的复数乘法算法,这是另一种只用三次乘法进行复数乘法的方法.总结一下,你计算

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技巧

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;

现在的问题是：我们可以用少于三个实数乘法来计算两个复数之间的乘积吗？

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

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

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