# Implementing Discrete Fourier Transform

I am trying to implement Discrete Fourier Transform (by definition, in quadratic time).

I wrote this http://jsfiddle.net/uunsm/12/

My result function really goes through discrete points, but it is too "wavy".

When I inserted a sine wave:

var nums = [0.000, 0.707, 1.000, 0.707, 0.000, -0.707, -1.000, -0.707]


I was expecting to get a smooth sine, but again, there are too many "waves". Am I doing anything wrong?

BTW. I found this implementation http://home.fuse.net/clymer/graphs/dft.html which is much smoother. Is it still Fourier transform? Where can I find any info about that algorithm?

-
This is more related to programming I guess. Now what is the question? errors in your code? or if your code is correct? – Seyhmus Güngören Sep 5 '12 at 19:49
I wanted to know if it is the correct behavior, or if I have any errors. – Ivan Kuckir Sep 5 '12 at 19:56
The behavior that you are seeing is correct. It is called Gibbs Phenomenon (see en.wikipedia.org/wiki/Gibbs_phenomenon). It is a natural artifact of trying to represent a non-continuous function (i.e. step) with a set of continuous functions (i.e. sinusoids). – Tpofofn Sep 6 '12 at 2:31

That's the expected behavior. In your first example, where var nums = [2, 2, 2, 2, -2, -2, -2, -2];, you're essentially trying to replicate a square wave with a series of sines and cosines. You cannot do that with so few terms; in fact, you cannot eliminate the waviness, only make it arbitrarily close (and then you have ringing phenomena, etc).
var nums = [2, -2, 2, -2, 2, -2, 2, -2];
@IvanKuckir Yes, this is essentially a Fourier series approximation. However, notice how the coefficients are conditioned by examining the output: every term is zero, except the term that corresponds to $\sin x$. If you view the source of that site, you can see how the coefficients are conditioned to achieve such a condition. The algorithm there is essentially the same as yours, with some additional steps outside the initial loop. Also, notice that code loops over $0 \le i \le n/2$. – Emily Sep 5 '12 at 20:18