# 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, ...`

.

### The Fast Fourier Transform Algorithm

#### Pseudocode:

#### Implementation:

#### Tests:

### 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.