Cooley Tukey twiddle factor in a simple python script

Question

I'm reading how the cooley tukey method works, but I have a few problems with the following python script:

def fft_CT_twiddles(x, inverse = False, verbose = False, twiddles = None) :
    """
    Computes the DFT of x using Cooley-Tukey's FFT algorithm. Twiddle factors
    are precalculated in the first function call, then passed down recursively.
    """
    t = time.clock()
    N = len(x)
    inv = -1 if not inverse else 1
    if N % 2 :
        return dft(x, inverse, False)
    M = N // 2
    if not twiddles :
        twiddles = [math.e**(inv*2j*math.pi*k/N) for k in xrange(M)]+[N]
    x_e = x[::2]
    x_o  = x[1::2]
    X_e = fft_CT_twiddles(x_e, inverse, False, twiddles)
    X_o  = fft_CT_twiddles(x_o, inverse, False, twiddles)
    X = []
    for k in range(M) :
        X += [X_e[k] + X_o[k] * twiddles[k * twiddles[-1] // N]]
    for k in range(M,N) :
        X += [X_e[k-M] - X_o[k-M] * twiddles[(k - M) * twiddles[-1] // N]]
    if inverse :
        X = [j/2 for j in X]
    t = time.clock() - t
    if verbose :
        print "Computed","an inverse" if inverse else "a","CT FFT of size",N,
        print "in",t,"sec."
    return X

What does the twiddles = [math.e**(inv*2j*math.pi*k/N) for k in xrange(M)]+[N] line does? Seems like an array but why the +[N]?

And why accessing the twiddles[-1] value then?

I can't figure this out

Answer 1

Trying to explain code when the level of expertise of the person asking the question is unknown is difficult. That said here it goes:

1. python has a concatenation operator for sequences nl. + so the twiddles = line creates a sequence of some sort and appends the number N to it.
2. twiddles[-1] accesses the last element in the sequence here the number N as the comments suggest.
3. the twiddles sequence expression uses complex numbers to generate a sequence consisting of the N points on the unit circle by dividing it in N equal slices.

Answer 2

The code you asked about is doing the following:

+[N] # appends N to the end of the array


twiddles[-1] # is the last element of the array ( the N in this case ).

The code appears to add the 'N' to the end of the twiddles array just for convenience, so that it can be used later, and so that it can easily be passed to the function as part of the twiddles argument instead of passing it as a separate variable.