from cmath import exp, pi


def fft(x):
    """
    fft implementation from rosettacode.
    The purpose of this task is to calculate the FFT (Fast Fourier Transform) of an input sequence.
    The most general case allows for complex numbers at the input and results in a sequence of
    equal length, again of complex numbers. If you need to restrict yourself to real numbers,
    the output should be the magnitude (i.e. sqrt(re²+im²)) of the complex result.
    :param x:
    :type x:

    >>> print( ' '.join("%5.3f" % abs(f) for f in fft([1.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0])) )
    4.000 2.613 0.000 1.082 0.000 1.082 0.000 2.613
    """
    N = len(x)
    if N <= 1: return x
    even = fft(x[0::2])
    odd = fft(x[1::2])
    T = [exp(-2j * pi * k / N) * odd[k] for k in range(int(N / 2))]
    return [even[k] + T[k] for k in range(int(N / 2))] + \
           [even[k] - T[k] for k in range(int(N / 2))]