#Python, 166 151 150 characters

This uses the radix-2 Cooley-Tukey FFT algorithm

from math import*
def F(x):N=len(x);t=N<2or(F(x[::2]),F(x[1::2]));return N<2and x or[
a+s*b/e**(2j*pi*n/N)for s in[1,-1]for(n,a,b)in zip(range(N),*t)]

Testing the result

>>> import numpy as np
>>> x = np.random.random(512)
>>> np.allclose(F(x), np.fft.fft(x))
True

Python, 166 151 150 characters

This uses the radix-2 Cooley-Tukey FFT algorithm

from math import*
def F(x):N=len(x);t=N<2or(F(x[::2]),F(x[1::2]));return N<2and x or[
a+s*b/e**(2j*pi*n/N)for s in[1,-1]for(n,a,b)in zip(range(N),*t)]

Testing the result

>>> import numpy as np
>>> x = np.random.random(512)
>>> np.allclose(F(x), np.fft.fft(x))
True

#Python, 166 151 characters

This uses the radix-2 Cooley-Tukey FFT algorithm

from math import*
def F(x):N=len(x);t=N<2or(F(x[::2]),F(x[1::2]));return N<2and x or[
a+s*b*e**(-2j*pi*n/N)for s in[1,-1]for(n,a,b)in zip(range(N),*t)]

Testing the result

>>> import numpy as np
>>> x = np.random.random(512)
>>> np.allclose(F(x), np.fft.fft(x))
True

#Python, 166 151 150 characters

This uses the radix-2 Cooley-Tukey FFT algorithm

from math import*
def F(x):N=len(x);t=N<2or(F(x[::2]),F(x[1::2]));return N<2and x or[
a+s*b/e**(2j*pi*n/N)for s in[1,-1]for(n,a,b)in zip(range(N),*t)]

Testing the result

>>> import numpy as np
>>> x = np.random.random(512)
>>> np.allclose(F(x), np.fft.fft(x))
True

Python: 166 151 Characters

This uses the radix-2 Cooley-Tukey FFT algorithm

from math import*
def F(x):N=len(x);t=N<2or(F(x[::2]),F(x[1::2]));return N<2and x or[
a+s*b*e**(-2j*pi*n/N)for s in[1,-1]for(n,a,b)in zip(range(N),*t)]

Testing the result

>>> import numpy as np
>>> x = np.random.random(512)
>>> np.allclose(F(x), np.fft.fft(x))
True

#Python, 166 151 characters

This uses the radix-2 Cooley-Tukey FFT algorithm

from math import*
def F(x):N=len(x);t=N<2or(F(x[::2]),F(x[1::2]));return N<2and x or[
a+s*b*e**(-2j*pi*n/N)for s in[1,-1]for(n,a,b)in zip(range(N),*t)]

Testing the result

>>> import numpy as np
>>> x = np.random.random(512)
>>> np.allclose(F(x), np.fft.fft(x))
True