import numpy as np


def bit_reverse(val: int, num_bits: int) -> None:
    b = '{:0{num_bits}b}'.format(val, num_bits=num_bits)
    return int(b[::-1], 2)


def fft_reorder(x: np.array) -> np.array:
    result = np.zeros(x.size)
    for i in range(x.size):
        result[i] = x[bit_reverse(i, int(np.log2(x.size)))]
    return result


def fft(x: np.array) -> np.array:
    x = fft_reorder(x).astype('complex64')

    N0 = x.size
    N = 2
    # while N <= N0:
    for N in [2, 4, 8]:
        first_sub_fft_index = 0
        while first_sub_fft_index < N0:
            for k in range(N // 2):
                factor = np.exp(-2j * np.pi * k / N)

                temp = factor * x[first_sub_fft_index + N // 2 + k]

                x[first_sub_fft_index + N//2 + k]\
                    = x[first_sub_fft_index + k] - temp
                x[first_sub_fft_index + k]\
                    = x[first_sub_fft_index + k] + temp

            first_sub_fft_index += N
        # N *= 2

    return x


def main():
    x = np.arange(8)
    print(fft(x))
    print(np.fft.fft(np.arange(8)))


if __name__ == "__main__":
    main()