# The Fast Fourier Transform Algorithm

The last section on the divide-and-conquer design paradigm on the book Algorithms by S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani focuses on a very interesting and well known algorithm: The Fast Fourier Transform algorithm. The Fast Fourier Transform is an algorithm which takes a coefficient representation of a polynomial and changes it to its equivalent point-wise representation. It is widely used in a variety of tasks in computer science such as: getting rid of noise in data, pattern matching, digital filtering, and others.

The big idea in the Fast Fourier Transform algorithm is that a change in the mathematical representation of a problem can simplify and have efficiency benefits over others. To better understand this idea, let’s examine the following polynomial: `f(x) = 5 + 2x + x^2`. This polynomial has degree `2`, and `3` numbers represent it (its coefficients). In general, a polynomial of `n - 1` degree has `n` coefficients. Now, let's investigate what values does this polynomial has at `x` equals to `0`, `1`, and `2`.

The natural question is then, if `n` points are given, do these numbers define a polynomial of `n - 1` degree? Yes, we can solve a set of linear equations, and the answer will be equal to `f(x) = 5 + 2x + x^2`. So what does this mean? We have been able to show that a polynomial can be represented in two different ways:

• A coefficient representation
• A point-wise representation

The algorithmic steps of the Fast Fourier Transform algorithm takes (assume `n` is a power of 2):

Re-writes it as:

Then, define new polynomials (the divide step):

And finally, `A(w)` can be expressed as (the combine step):

The only issue though, is that the points which the algorithm needs to use to compute `A(w)` for an `n` (power of 2) need to be carefully chosen. The method the author suggests is using the complex nth-roots of unity. By using the complex nth-roots of unity for an `n` power of 2, then at successive levels of recursion tree we will have `(n/2^k)th` roots of unity for `k=0, 1, 2, 3, ...`.

### Conclusion

The Fast Fourier Transform algorithm is a really nice way to demonstrate how mathematical ingenuity plays a big role in the design and analysis of algorithms. Changing the representation of the data given to us for a specific task can bring great benefits to both the understanding of the overall process and the efficiency in the computations needed to produce the desired output.

Like what you read? Give Diego Castillo a round of applause.

From a quick cheer to a standing ovation, clap to show how much you enjoyed this story.