为什么复数乘法几乎和 python 中的整数乘法一样快？

Question

我的印象是复数乘法比实数乘法需要更长的时间，因为它需要 3 multiplications。

但是我尝试了以下方法：

a, b = 3, 4
c, d = 5, 6
print(a*c - b*d, a*d + b*c)

e = 3+4j
f = 5+6j
print(e*f)

%timeit a*c - b*d
%timeit a*d + b*c
%timeit e*f
%timeit a*b

得到了

-9 38
(-9+38j)
110 ns ± 0.2 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
102 ns ± 0.193 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
47.2 ns ± 0.942 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
43 ns ± 1.52 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

为什么复数乘法几乎和实数乘法一样快？

我明白 Python 是一门高级语言，但这个结果仍然让我感到困惑...

我能想到的唯一解释是，我的两种计算都达到了如此低的速度，不知何故瓶颈不是计算本身，而是其他原因..

这是我原来想问的问题

我有这个版本的离散傅里叶变换，它使用复杂的操作：

from math import e, pi, cos, sin, log2

def W(n, N):
    theta = n * -1 * 2 * pi / N
    return cos(theta) + 1j*sin(theta)

def dft(signal):
    N = len(signal)
    total = []
    for k in range(N):
        s = 0
        for n in range(N):
            s += signal[n] * W(n*k, N)
        total.append(s)
    return total

我也有这个版本的 DFT，它不使用复杂的运算而是使用两个实数信号，因为信号的虚部被编码到一个实数数组中。

def Wri(n, N):
    theta = n * -1 * 2 * pi / N
    return cos(theta), sin(theta)

def dft_ri(signal_r, signal_i):
    N = len(signal_r)
    tr, ti = [], []
    for k in range(N):
        sr = 0
        si = 0
        for n in range(N):
            a = signal_r[n]
            b = signal_i[n]
            c, d = Wri(n*k, N)
            sr += a*c - b*d
            si += a*d + b*c
        tr.append(sr)
        ti.append(si)
    return tr, ti

使用以下复杂信号

x = np.linspace(0, T, 1024)
def signal2(t):
    return np.where(np.logical_and((t%T>=0), (t%T<np.pi)), t%T+t%T*1j, np.pi+np.pi*1j)

s = list(signal2(x))
sr = list(np.real(s))
si = list(np.imag(s))

这两个 W 花费的时间大致相同

%timeit W(8, 3)
%timeit Wri(8, 3)

产出

464 ns ± 0.756 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
424 ns ± 2.21 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

但是

%timeit dft(s)
%timeit dft_ri(sr, si)

产出

935 ms ± 4.63 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
1.6 s ± 3.04 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

问题

为什么没有复杂运算的DFT比有复杂运算的DFT耗时将近两倍？

Answer 1

您的计时几乎是 100% 的开销。无论哪种方式，实际的硬件级乘法都只是成本的一小部分。

尝试使用 NumPy 数组，它的每个元素开销要低得多，你会看到一个不同的故事：

In [1]: import numpy

In [2]: x = numpy.ones(10000)

In [3]: y = x.astype(complex)

In [4]: %timeit x*x
4.2 µs ± 51.5 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [5]: %timeit y*y
16.6 µs ± 696 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [6]: z = x.astype(int)

In [7]: %timeit z*z
6.54 µs ± 1 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)

每个元素的时间接近 1 纳秒，而您的时间更像是每个元素 40 到 100。

您在 FFT 实施中看到的性能差异也是由开销造成的。您的运行时间实际上很少花在做数学上。

为什么复数乘法几乎和 python 中的整数乘法一样快？

Why is complex multiplication nearly as fast as integer multiplication in python?

python

performance

complex-numbers

为什么复数乘法几乎和实数乘法一样快？

问题