快速傅里葉變換(fft)
以下是python代碼實現(xiàn):
```python
from cmath import pi, exp
def fft(coefficients, w):
? ? n = len(coefficients)? # n的值一定是一個偶數(shù)
? ? # 如果只有一個值，那么將這個值返回
? ? if n == 1:
? ? ? ? return coefficients
? ? coefficients_even = []? # 偶數(shù)項系數(shù)
? ? coefficients_odd = []? # 奇數(shù)項系數(shù)
? ? 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)]
? ? # 分別計算每一個點對應當前函數(shù)的對應的值
? ? 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的次數(shù)
? ? 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
? ? # 擴展系數(shù)值
? ? 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)]
? ? # 逆向傅里葉變化，將點值對轉(zhuǎn)換為系數(shù)
? ? 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*
