FFT.py

import math as m
from cmath import exp, pi

def recursiveFFT(x,inverse):
 n=len(x)
 if n<=1: return x
 even=recursiveFFT(x[0::2],inverse)
 odd=recursiveFFT(x[1::2],inverse)
 halfN=n//2
 sign=-1 if inverse else 1
 w=[exp(sign*pi*k/n) for k in range(halfN)]
 T=[w[k]*odd[k] for k in range(halfN)]
 R=[even[k]+T[k] for k in range(halfN)]
 R+=[even[k]-T[k] for k in range(halfN)]
 return R

def getAdditionalZeroes(n):
 power2=int(m.log(n-1,2))+1
 return 2**power2-n

def createListWithAdditionalZeroes(a):
 n=len(a)
 newList=[x for x in a]
 newList+=[0 for i in range(getAdditionalZeroes(n))]
 return newList

def fft2(a):
 n=len(a)
 a2=createListWithAdditionalZeroes(a)
 return recursiveFFT(a2,False)

def ifft2(a):
 a2=createListWithAdditionalZeroes(a)
 n2=len(a2)
 return [x/n2 for x in recursiveFFT(a2,True)]

a=[10,20,30,40,50,60,70]
#a=[10,20,30,40,50]
a2=fft2(a)
a3=ifft2(a2)
print('Results of my FFT with zero padding:')
print(a)
print(a2)
print(a3)

from numpy.fft import fft,ifft
from numpy import array

b2=fft(a)
b3=ifft(b2)
print('Results of numpy.fft:')
print(a)
print(b2)
print(b3)