Problem $2$:

The Fast Fourier Transform $($FFT$)$ is an efficient algorithm to compute the Discrete Fourier Transform $($DFT$){?}^1$ and its inverse. DFT transforms a sequence of complex numbers in the time domain to a sequence of complex numbers in the frequency domain. By using FFT$,$ you can perform signal analysis, image processing, and much more efficiently.

Tasks:

Create a Complex Number Class:

Define a Complex class that includes the real and imaginary parts of the complex number.

Implement methods for basic operations, such as addition, multiplication, modulus, $...$ etc.

Implement the FFT Method:

Write a recursive method called fft that takes an array of Complex numbers as input. The method should:

Split the input array into even and odd indexed elements $($this is the "divide" step$).$

Recursively compute the FFT for both subarrays.

Combine the results from the recursive calls to produce the FFT for the original array $($this is the "conquer" step$).$

Note: You will need to use the formula for the FFT:

where:

$x_k={\displaystyle \underset{n=0}{\overset{N-1}{}}}{x}_n*e^{-2i\frac{k}{N^n}}$

$x[k]$ is the k$-$th output frequency component $($where $k=0,1,$dots,$N-1).$

$x[n]$ is the input sequence of complex numbers.

$,N$ is the total number of samples $($i$.$e$.$ the length of the sequence$).$

$e$ is the base of the natural logarithm.

$i$ is the imaginary unit.

Hint: $e^{ix}=cos(x)+i*sin(x)$

Create a Main Method:

The main method should:

Prompt the user to enter a file name containing a sequence of complex numbers.

Call the fft method to compute the Fourier Transform.

Display the transformed frequencies.

Call the inverse$\_$fft to compute the inverse FFT

Display the resulted frequencies.

Verify that the result of the inverse FFT matches the original input.

Experiment with Input Data:

Test the FFT implementation with various sets of complex numbers.

Verify the output through the inverse FFT to check if you can recover the original input. You will need to use the formula for the inverse FFT:

$x_n=\frac{1}{N}{\displaystyle \underset{n=0}{\overset{N-1}{}}}{x}_k*e^{2i\frac{k}{N}n}$

Assume the following input $($left$)$ was given to your code, where $4$ in the first line is the number of complex numbers in the sequence. From line $2$ to line $5,$ the left value is the real part of the complex number and the right value is the imaginary part. The output of your code will be as shown on the right of this figure.Figure $1$: Sample Input and Output for Problem $2$