快速傅里叶变换(fft)

以下是python代码实现:

```python

from cmath import pi, exp

def fft(coefficients, w):

    n = len(coefficients)  # n的值一定是一个偶数

    # 如果只有一个值，那么将这个值返回

    if n == 1:

        return coefficients

    coefficients_even = []  # 偶数项系数

    coefficients_odd = []  # 奇数项系数

    for i in range(0, n // 2):

        coefficients_even.append(coefficients[2 * i])

        coefficients_odd.append(coefficients[2 * i + 1])

    y_even, y_odd = fft(coefficients_even, w ** 2), fft(coefficients_odd, w ** 2)

    current_x = 1  # 默认values上的第i个坐标上的值是第i个单位根上对应的y值, 所以第一个值为1

    values = [0 for _ in range(n)]

    # 分别计算每一个点对应当前函数的对应的值

    for i in range(0, n // 2):

        values[i] = y_even[i] + current_x * y_odd[i]

        values[i + n // 2] = y_even[i] - current_x * y_odd[i]

        current_x = current_x * w  # 计算下一个x的值

    return values

def solver_fft(coefficient_a: list, coefficient_b: list):

    # 填充0，将a和b的长度扩展为2的次数

    min_coefficient_count = len(coefficient_a) + len(coefficient_b) - 1

    exponent_value = 1

    while 2 ** exponent_value < min_coefficient_count:

        exponent_value += 1

    coefficient_count = 2 ** exponent_value

    # 扩展系数值

    coefficient_a.extend([0 for _ in range(coefficient_count - len(coefficient_a))])

    coefficient_b.extend([0 for _ in range(coefficient_count - len(coefficient_b))])

    # 计算当前单位根的间距，也就是每一个相邻单位根的插值

    w = exp(2 * pi * 1j / coefficient_count)

    a_values = fft(coefficient_a, w)

    b_values = fft(coefficient_b, w)

    a_times_b_values = [a_values[i] * b_values[i] for i in range(coefficient_count)]

    # 逆向傅里叶变化，将点值对转换为系数

    result = [round((x / coefficient_count).real) for x in fft(a_times_b_values, w ** -1)]

    # 将末尾不必要的0进行删除

    while result[-1] == 0:

        del result[-1]

    return result

print(solver_fft([1, 5, 3, 2], [10, 3, 0, 0, 0, 1]))

# [10, 53, 45, 29, 6, 1, 5, 3, 2]

```

*参考:*

*1、<python算法设计和分析>*

*2、The Fast Fourier Transform (FFT): Most Ingenious Algorithm Ever? - YouTube*