import cmath
import math

# 長さNの前半k番目のdftはk番目の偶数dftとW^k分回したk番目の奇数dftを足したもので 、
# 後半k番目のdftはk番目の偶数dftとW^k分回したk番目の奇数dftを引いたもの

data = [3.2, 3.5, 4.5, 3.0, 8.0, 5.6, 7.8, 4.0]

data_0 = [data[0], data[2], data[4], data[6]]
data_1 = [data[1], data[3], data[5], data[7]]

data_00 = [data_0[0], data_0[2]]
data_01 = [data_0[1], data_0[3]]
data_10 = [data_1[0], data_1[2]]
data_11 = [data_1[1], data_1[3]]

data_000 = [data_00[0]]
data_001 = [data_00[1]]
data_010 = [data_01[0]]
data_011 = [data_01[1]]
data_100 = [data_10[0]]
data_101 = [data_10[1]]
data_110 = [data_11[0]]
data_111 = [data_11[1]]

N = 2

# data_00 にとって data_000Dft が偶数DFT で data_001Dft が奇数 DFT
data_00Dft = [data_000[0] + cmath.exp(-2j * math.pi * 0 / N) * data_001[0],
              data_000[0] - cmath.exp(-2j * math.pi * 0 / N) * data_001[0]]
data_01Dft = [data_010[0] + cmath.exp(-2j * math.pi * 0 / N) * data_011[0],
              data_010[0] - cmath.exp(-2j * math.pi * 0 / N) * data_011[0]]
data_10Dft = [data_100[0] + cmath.exp(-2j * math.pi * 0 / N) * data_101[0],
              data_100[0] - cmath.exp(-2j * math.pi * 0 / N) * data_101[0]]
data_11Dft = [data_110[0] + cmath.exp(-2j * math.pi * 0 / N) * data_111[0],
              data_110[0] - cmath.exp(-2j * math.pi * 0 / N) * data_111[0]]

N = 4

# data_0 にとって data_00Dft が偶数DFT で data_01Dft が奇数 DFT
data_0Dft = [data_00Dft[0] + cmath.exp(-2j * math.pi * 0 / N) * data_01Dft[0],
             data_00Dft[1] + cmath.exp(-2j * math.pi * 1 / N) * data_01Dft[1],
             data_00Dft[0] - cmath.exp(-2j * math.pi * 0 / N) * data_01Dft[0],
             data_00Dft[1] - cmath.exp(-2j * math.pi * 1 / N) * data_01Dft[1]]
data_1Dft = [data_10Dft[0] + cmath.exp(-2j * math.pi * 0 / N) * data_11Dft[0],
             data_10Dft[1] + cmath.exp(-2j * math.pi * 1 / N) * data_11Dft[1],
             data_10Dft[0] - cmath.exp(-2j * math.pi * 0 / N) * data_11Dft[0],
             data_10Dft[1] - cmath.exp(-2j * math.pi * 1 / N) * data_11Dft[1]]

N = 8
data_Dft = [data_0Dft[0] + cmath.exp(-2j * math.pi * 0 / N) * data_1Dft[0],
            data_0Dft[1] + cmath.exp(-2j * math.pi * 1 / N) * data_1Dft[1],
            data_0Dft[2] + cmath.exp(-2j * math.pi * 2 / N) * data_1Dft[2],
            data_0Dft[3] + cmath.exp(-2j * math.pi * 3 / N) * data_1Dft[3],
            data_0Dft[0] - cmath.exp(-2j * math.pi * 0 / N) * data_1Dft[0],
            data_0Dft[1] - cmath.exp(-2j * math.pi * 1 / N) * data_1Dft[1],
            data_0Dft[2] - cmath.exp(-2j * math.pi * 2 / N) * data_1Dft[2],
            data_0Dft[3] - cmath.exp(-2j * math.pi * 3 / N) * data_1Dft[3]]

print("\nFFT Output:")
for i, val in enumerate(data_Dft):
    # 複素数を見やすく丸めて表示
    real = round(val.real, 2)
    imag = round(val.imag, 2)
    print(f"X[{i}] = {real} + {imag}j")