# Why does the Discrete Fourier Transform and the Fast Fourier Transform give different results?

I have a function

$$f(t) = \begin{cases} a(1-a|t|) &\text{if } |t|<\dfrac{1}{a} \\[6pt] 0 &\text{if } |t|>\dfrac{1}{a} \end{cases}$$

Here is what the function looks like for $a=2$:

I wrote two scripts to evaluate the Fourier Transform of this function, $g(\omega)=\mathcal{F}[f(t)]$. One is simply a numerical integration of the standard Fourier Transform, and the other is an implementation of the Discrete Fourier Transform. Here are the results of running those two scripts, with the DFT on the top:

Since these two look largely the same, minus some differences in normalization, I'm convinced my implementations are working properly. However, if I run an FFT on $f(t)$, and plot the result vs. frequency, it looks completely different than what I get from either other method of computation:

Why is this? Shouldn't they look exactly the same? I mean the FFT is literally the DFT, just implemented in a cleverly optimized way. What am I doing wrong?

• One issue is that your FFT output appears to be in the range $[0,60]$, but you have plotted it as $[-30,30]$. You need to circularly shift it by 30 in order to put the peak at $w=0$. This isn't the only issue, however. We should expect the output to be nonnegative since the triangle is a convolution of two rectangles, so its Fourier transform should be the square of the FT of a rectangle, hence nonnegative. Can you reproduce the problem for a smaller data set (maybe just a few points), and include the actual numerical values of the input vector and the outputs given by the DFT and the FFT? – Bungo Oct 27 '16 at 17:39
• Numerical integration of the standard FT is not really the same thing as the ordinary DFT. – Ian Oct 27 '16 at 17:39
• Have you verified that the imaginary part of both the DFT and the FFT are zero? You might be getting a phase component depending on how you formed the input vector. – Bungo Oct 27 '16 at 17:46
• @Bungo Just checked, imaginary parts are all zero. I'll try a smaller dataset – user278703 Oct 27 '16 at 18:02
• @Bungo Also, how do you know the FFT is outputting a frequency range of [0,60]? For the DFT that I wrote, i explicitly use a certain input frequency range of [-30,30]. For the FFT, obviously all I do is call an fft() function with the input argument as the vector of function values $f(t)$. – user278703 Oct 27 '16 at 18:06

The FFT returns you a signal in the range $[0-2f_\text{max}]$ where $f_\text{max}=1/(2dt)$. Also it gives you a signal where the negative frequencies come after the positive. To resolve that issue use 'fftshift' after using 'fft', you will see that the spectrum will become symmetric as you want it since your original signal is real.