Wrong output for FFT implementation

Question

I'm trying to implement in Python the following Algorithm of FFT but the output is almost always wrong. I don't understand my mistakes. Can someone put some light on my mistakes ? That'll be great !

EDIT:

• cpo2(x,y) return the closest power of 2 of max(x,y)
• fill(A,n) fills the list A (by zeros at the end of the list) till A reaches length n
• An example where my function works (according to numpy.fft.fft):

input [1,2] -> output [3, -1]

• Here are some examples where my function doesn't work:
• input : -> output (wrong) // output (true based on np.fft.fft)
• [1,2,3,4] -> [(10+0j), (-2-2j), (-2+0j), (-2+2j)] // [10.+0.j -2.+2.j -2.+0.j -2.-2.j]
• [1,2,3] ->[6, 2] //[ 6. +0.j -1.5+0.8660254j -1.5-0.8660254j]
• [1,4,4,0] -> [(9+0j), (-3+4j), (1+0j), (-3-4j)] //[ 9.+0.j -3.-4.j 1.+0.j -3.+4.j]

def FFT(A):
    n = int(len(A))
    if n == 1:
        return A
    w_n = np.exp(complex(0,2*np.pi/n))
    w = 1
    (A0,A1) = decomp(A)
    A0_star = FFT(A0)
    A1_star = FFT(A1)
    A_star0 = list()
    A_star1 = list()
    for k in range(int(n/2)):
        A_star0.append(A0_star[k] + w*A1_star[k])
        A_star1.append(A0_star[k] - w*A1_star[k])
        w = w*w_n
    A_star = A_star0 + A_star1
    return list(np.around(A_star))

def decomp(A):
   l = len(A)
   n = cpo2(l,l)
   A = fill(A,n)
   A0 = A[0::2]
   A1 = A[1::2]
   return(A0,A1)

Answer 1

Two things immediately stand out to me:

1. Your for k in range(int(n/2)): means that this only works for even values of n. And since you're calling FFT recursively, that probably means this only works when n is a power of two. Maybe that's OK, often all you care about is input lengths that are powers of two. But one of your example failures has n=3, which is not a power of two.
2. When n=4, all your failure cases are just failures where the imaginary part of the result is the negative of what you expected. There are different definitions of FFT, which differ by the sign of the exponent in the complex exponential (the w_n in your code). It appears that you have implemented a definition which is the opposite of what np.fft.fft implements. The implementation of np.fft.fft probably follows the convention used in electrical engineering where there is a minus sign in the exponential. Your implementation seems to follow the convention used in physics where there is a plus sign in the exponential. So, try using w_n = np.exp(complex(0,-2*np.pi/n)).

There might be more issues as well, but start with those...