FFT Transform Code Snippets

def DFT_slow(x):
	x = np.asarray(x, dtype=float)
	N = len(x)
	n = np.arange(N) # n is current sample we're consider - 1 to N-1. 
	k = n.reshape((N, 1)) # 5000 LENGHT X 1 width - current freq we're looking at 1 - N-1. 
	M = np.exp(-2j * np.pi * k * n / N) #  multiply 
	return np.dot(M, x)
# O(nlogn) runtme
# Outputs the spectrum of frequencies - dissecting what vmakes up various parts of hte sound waves
def FFT(x):
	N = len(x)	
	print(N)
	if N % 2 > 0: # must be a power of two. 
		raise ValueError("hey")
	elif (N <= 32):
		return DFT_slow(x)
	else:
		odd = x[1::2]
		even = x[::2]
		transformed_odd = FFT(odd)
		transformed_even = FFT(even)
		n = np.arange(N)
		factor = np.exp(-2j * np.pi * np.arange(N) / N)
		return np.concatenate([transformed_even + factor[:int(N / 2)] * transformed_odd,
                               transformed_even + factor[int(N / 2):] * transformed_odd])
		

def pad_if_needed(x):
	print(x)
	check = np.log2(len(x))
	print(check.is_integer())
	while check.is_integer() is False:
		x = np.append(x, 0)
		check = np.log2(len(x))

		print(len(x))
	return x