32 lines
641 B
Python
32 lines
641 B
Python
import numpy as np
|
|
|
|
|
|
def fft(x: np.array) -> np.array:
|
|
N = len(x)
|
|
|
|
if N == 1:
|
|
return x
|
|
else:
|
|
even_fft = fft(x[::2])
|
|
odd_fft = fft(x[1::2])
|
|
|
|
factors = np.exp(-2j * np.pi * np.arange(N) / N)
|
|
|
|
result = np.concatenate([even_fft + factors[:N // 2] * odd_fft,
|
|
even_fft + factors[N // 2:] * odd_fft])
|
|
|
|
return result
|
|
|
|
|
|
def main():
|
|
x = np.arange(8)
|
|
fft(x)
|
|
# # x = np.random.normal(size=4)
|
|
# x = np.array([1, 0, 1, 0, 0, 0, 0, 0])
|
|
# print(f"own:\t{fft(x)}")
|
|
# print(f"numpy:\t{np.fft.fft(x)}")
|
|
|
|
|
|
if __name__ == "__main__":
|
|
main()
|