# DFT vs FFT - porovnani casu
from cmath import exp, pi
import numpy as np
import time


def fft(f):
    N = len(f)

    if N <= 1:
        return f

    even = fft(f[0::2])
    odd = fft(f[1::2])

    T = [exp(-2j * pi * k / N) * odd[k] for k in range(N // 2)]

    return [even[k] + T[k] for k in range(N // 2)] + [even[k] - T[k] for k in range(N // 2)]


def dft(f):
    N = len(f)
    result = [0] * N

    for i in range(N):
        for j in range(N):
            result[i] += f[j] * exp(-2j * pi * i * j / N)
    return result


print("i,  2**i      DFT,      FFT,    numpy")
for i in range(10, 21):
    f = [1] * 2**i
    start_time_D = end_time_D = 0
    if i < 15:
        start_time_D = time.time()
        dft(f)
        end_time_D = time.time()

    start_time_F = time.time()
    fft(f)
    end_time_F = time.time()

    start_time_N = time.time()
    np.fft.fft(f)
    end_time_N = time.time()
    print(i, 2**i, end_time_D - start_time_D, end_time_F - start_time_F, end_time_N - start_time_N)