import numpy as np
import matplotlib.pyplot as plt

x = np.array([0+0j, 1+0j, 2+0j, 3+0j, 4+0j, 5+0j, 6+0j, 7+0j])
N = len(x)
m = int(np.log2(N))
idx = np.arange(N)
idx = ((idx & 1) << (m - 1)) | (idx >> 1)
x = x[idx]
count = 0
for s in range(1, m + 1):
    bsep = 2 ** s
    p = N // bsep
    bwidth = bsep // 2
    for j in range(bwidth):
        r = p * j
        theta = 2 * np.pi * r / N
        wn = np.cos(theta) - np.sin(theta) * 1j

        for topval in range(j, N, bsep):
            botval = topval + bwidth
            temp = x[botval] * wn
            x[botval] = x[topval] - temp
            x[topval] = x[topval] + temp
    print("Output after layer",count+1,"=", x, "\n")
    count += 1

print("Final Output = ", x)
plt.stem(range(N), np.real(x), label='Real', linefmt='C0-', markerfmt='C0o', basefmt='C0-')
plt.stem(range(N), np.imag(x), label='Imaginary', linefmt='C1-', markerfmt='C1o', basefmt='C1-')
plt.xlabel('Index')
plt.ylabel('Value')
plt.legend()
plt.show()