import numpy as np from numpy.fft import fft, ifft from matplotlib import pyplot as plt import seaborn as sns from numpy import dot import math from math import pi #returns smallest power of 2 that is greater or equal than v def power_2_bound(v): v -= 1 v |= v >> 1 v |= v >> 2 v |= v >> 4 v |= v >> 8 v |= v >> 16 return v + 1 #complex mul and add def cdot(x, y): return np.array([x[0] * y[0] - x[1] * y[1], x[0] * y[1] + x[1] * y[0]]) def cadd(x, y): return np.array([x[0] + y[0], x[1] + y[1]]) n = 100 np.set_printoptions(suppress=True) resolution = power_2_bound(n) root_angles = np.array([(2 * math.pi) * i / resolution for i in xrange(resolution)]) roots = np.array([np.cos(root_angles) + 1j* np.sin(root_angles)]) MUL = 32 roots_long = np.zeros(roots.size*MUL, dtype=np.complex) roots_long[:roots.size] = roots[:] sns.plt.scatter(roots_long.real, roots_long.imag, c='blue') sns.plt.scatter(fft(roots_long).real / math.sqrt(roots.size*MUL), fft(roots_long).imag / math.sqrt(roots.size*MUL), c='green') sns.plt.scatter(ifft(roots_long).real * math.sqrt(roots.size*MUL), ifft(roots_long).imag * math.sqrt(roots.size*MUL), c='red')