Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

I wrote this

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 which is much smoother. Is it still Fourier transform? Where can I find any info about that algorithm?

share|cite|improve this question
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 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).

With your example above, you're trying to represent one low-frequency oscillation with a sum of several higher frequency oscillations. Again, you cannot do that perfectly, so you will get some waviness.

If you want a nice smooth wave, your data has to change with the same frequency as your components. Try this and see what happens.

var nums = [2, -2, 2, -2, 2, -2, 2, -2];

share|cite|improve this answer
Thakn you very much! I thought that it is expected, but I was not sure. BTW. I added another link to my question, can you tell me something about it? – Ivan Kuckir Sep 5 '12 at 20:04
@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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.