Playing with Discrete Fourier Transform Algorithm in JavaScript

TL;DR

You may find Discrete Fourier Transform algorithm in JavaScript Algorithms repository.

Discrete Fourier Transform

Even though Discrete Fourier Transform or DFT is probably not the thing you work with daily it might still be a very interesting algorithm to play with. Not because it is quite complex but because of its interesting meaning.

This algorithm allows you to split the input signal that is spread in time into the number of frequencies of certain length, amplitudes and phases so that all those frequencies together will form the original signal. So it actually converts the domain of time into domain of frequencies and backwards.

It may sound complicated so let’s think about it from another angle.

Smoothie Example

Imagine you have smoothie. DFT then will allow you to split smoothie into its ingredients! Imagine that you provide the bottle of smoothie as an input for DFT function and it splits it out to three smaller bottles of pure carrot, apple and orange juices! This is what DFT does — it splits the whole input into its ingredients.

Paints Example

Or imagine that you want to paint the fence and you’ve mixed several paints up so that it started to be of homogenous color. DFT function then will be able to split your mixed paint into several pure colors that will together form that initial color! Isn’t is sound like a magic, is it?

The Algorithm

All algorithm beauty and complexity is hidden in the following formula:

You may find direct and simple implementation of this formula in JavaScript Algorithms repository. This is just a simple and not really efficient O(n2) implementation of the transform. But the purpose of those functions are just to scratch the surface of such a complex, deep and magic topic as Fourier Transform.

There is a really good article about this topic. I suggest you to read it if you’re interesting in learning more since there are many visual and interactive Fourier Transform examples and explanations.

I hope you found this Fourier thing interesting. Have fun with algorithms!