from cmath import exp , sqrt , pi

def FFT(f):
    N = len(f) # How many elements in the input?
    print "Entering FFT with N="+str(N)
    if N==1: return [f[0]] # sequence with one element.
    F = N * [0]      # space for the answers.
    f_even = f[0::2] # every other element, starting at 0
    f_odd  = f[1::2] #   "     "      "         "    "  1
    print "f_even: "+str(f_even)
    print "f_odd:  "+str(f_odd)
    F_even = FFT(f_even) # first recursive call.
    F_odd  = FFT(f_odd)  # second recursive call
    # Now combine:
    N2 = int(N/2)
    for i in range(N2):
        twiddle = exp(-2*pi*1j*i/N)
        oddTerm = F_odd[i] * twiddle
        F[i]    = F_even[i] + oddTerm
        F[i+N2] = F_even[i] - oddTerm
    return F

# Now for a test:
f8 = [1, 2, 0, -2, 3, 0, -4, -2] # sample data
F = FFT(f8)
print F