``````

In [1]:

import numpy as np
import matplotlib.pyplot as plt
import time

``````
``````

In [2]:

#esse bloco tem funções a serem utilizadas nos blocos seguintes

#transformação discreta de Fourier no modo convencional
def DFT(x):
N = x.shape[0] #quantidade de elementos
n = np.arange(N)
k = n.reshape((N, 1)) #transposição de n
M = np.exp(-2j * np.pi * k * n / N)
return np.dot(M, x)

#fonte https://jakevdp.github.io/blog/2013/08/28/understanding-the-fft/
def FFT(x):
"""A vectorized, non-recursive version of the Cooley-Tukey FFT"""
x = np.asarray(x, dtype=float)
N = x.shape[0]

if np.log2(N) % 1 > 0:
N = x.shape[0]

# N_min here is equivalent to the stopping condition above,
# and should be a power of 2
N_min = min(N, 32)

# Perform an O[N^2] DFT on all length-N_min sub-problems at once
n = np.arange(N_min)
k = n[:, None]
M = np.exp(-2j * np.pi * n * k / N_min)
X = np.dot(M, x.reshape((N_min, -1)))

# build-up each level of the recursive calculation all at once
while X.shape[0] < N:
X_even = X[:, :X.shape[1] / 2]
X_odd = X[:, X.shape[1] / 2:]
factor = np.exp(-1j * np.pi * np.arange(X.shape[0])
/ X.shape[0])[:, None]
X = np.vstack([X_even + factor * X_odd,
X_even - factor * X_odd])

return X.ravel()

``````
``````

In [3]:

n = 9
t1 = np.zeros((n, 1))
t2 = np.zeros((n, 1))
t3 = np.zeros((n, 1))
for i in range(0, n):
N = 2 ** i
x = np.linspace(0, 2*np.pi, N)
y = np.sin(x)

#simular DFT
t0 = time.time()
f1 = DFT(y)
tf = time.time()
t1[i] = tf - t0

t0 = time.time()
f2 = FFT(y)
tf = time.time()
t2[i] = tf - t0

#simular FFTPACK
t0 = time.time()
f3 = np.fft.fft(y)
tf = time.time()
t3[i] = tf - t0

``````
``````

/home/danilo/.local/lib/python3.4/site-packages/ipykernel/__main__.py:34: DeprecationWarning: using a non-integer number instead of an integer will result in an error in the future
/home/danilo/.local/lib/python3.4/site-packages/ipykernel/__main__.py:35: DeprecationWarning: using a non-integer number instead of an integer will result in an error in the future

``````
``````

In [4]:

#graficar tempo de execução
plt.plot(t1*100, '+-', label='DFT')
plt.plot(t2*100, '+-', label='FFT')
plt.plot(t3*100, '+-', label='FFTPACK')
plt.title("Tempo de execução das transformadas de Fourier", fontsize = 24)
plt.ylabel('Tempo de execução (ms)', fontsize = 20)
plt.xlabel('Passos (\$2^n\$)', fontsize = 20)
plt.legend()
plt.show()

``````
``````

In [5]:

plt.plot(np.square(np.abs(f1/N)), '+-', label='DFT')
plt.plot(np.square(np.abs(f2/N)), '+-', label='FFT')
plt.plot(np.square(np.abs(f3/N)), '+-', label='FFTPACK')
plt.xlim(0, 2**(n-3))
plt.ylabel("\$|Y|^2\$", fontsize = 20)
plt.xlabel("Hz", fontsize = 20)
plt.legend()
plt.show()

``````
``````

In [6]:

n = 9
t1 = np.zeros((n, 1))
t2 = np.zeros((n, 1))
t3 = np.zeros((n, 1))
for i in range(0, n):
N = 2 ** i
x = np.linspace(0, 2*np.pi, N)
y = np.sin(x) + 2*np.sin(5*x) + 3*np.sin(15*x)

t0 = time.time()
f1 = DFT(y)
tf = time.time()
t1[i] = tf - t0

t0 = time.time()
f2 = FFT(y)
tf = time.time()
t2[i] = tf - t0

t0 = time.time()
f3 = np.fft.fft(y)
tf = time.time()
t3[i] = tf - t0

``````
``````

/home/danilo/.local/lib/python3.4/site-packages/ipykernel/__main__.py:34: DeprecationWarning: using a non-integer number instead of an integer will result in an error in the future
/home/danilo/.local/lib/python3.4/site-packages/ipykernel/__main__.py:35: DeprecationWarning: using a non-integer number instead of an integer will result in an error in the future

``````
``````

In [7]:

#graficar tempo de execução
plt.plot(t1*100, '+-', label='DFT')
plt.plot(t2*100, '+-', label='FFT')
plt.plot(t3*100, '+-', label='FFTPACK')
plt.title("Tempo de execução das transformadas de Fourier", fontsize = 24)
plt.ylabel('Tempo de execução (ms)', fontsize = 20)
plt.xlabel('Passos (\$2^n\$)', fontsize = 20)
plt.legend()
plt.xlim(0, n-1)
plt.show()

``````
``````

In [8]:

plt.plot(np.square(np.abs(f1/N)), '+-', label='DFT')
plt.plot(np.square(np.abs(f2/N)), '+-', label='FFT')
plt.plot(np.square(np.abs(f3/N)), '+-', label='FFTPACK')
plt.xlim(0, 2**(n-3))
plt.ylabel("\$|Y|^2\$", fontsize = 20)
plt.xlabel("Hz", fontsize = 20)
plt.legend()
plt.show()

``````
``````

In [9]:

n = 20
t2 = np.zeros((n, 1))
t3 = np.zeros((n, 1))
for i in range(0, n):
N = 2 ** i
x = np.linspace(0, 2*np.pi, N)
y = np.sin(x) + 2*np.sin(5*x) + 3*np.sin(15*x)

t0 = time.time()
f2 = FFT(y)
tf = time.time()
t2[i] = tf - t0

t0 = time.time()
f3 = np.fft.fft(y)
tf = time.time()
t3[i] = tf - t0

``````
``````

/home/danilo/.local/lib/python3.4/site-packages/ipykernel/__main__.py:34: DeprecationWarning: using a non-integer number instead of an integer will result in an error in the future
/home/danilo/.local/lib/python3.4/site-packages/ipykernel/__main__.py:35: DeprecationWarning: using a non-integer number instead of an integer will result in an error in the future

``````
``````

In [10]:

#graficar tempo de execução
plt.plot(t2*100, '+-', label='FFT')
plt.plot(t3*100, '+-', label='FFTPACK')
plt.title("Tempo de execução das transformadas de Fourier", fontsize = 24)
plt.ylabel('Tempo de execução (ms)', fontsize = 20)
plt.xlabel('Passos (\$2^n\$)', fontsize = 20)
plt.legend()
plt.xlim(0, n-1)
plt.show()

``````
``````

In [ ]:

``````