IITKESO207SPA1 - FFT and inverse FFT
The problem asks you to write code to implement the recursive FFT algorithm and FFT inverse algorithm. Your program should first take an input 0 or 1.
If input is 0, the following input must be accepted and the FFT algorithm must be run. The input will be of the form n, a_0, b_0, a_1, b_1, ..., a_n-1, b_n-1. Here, n denotes the degree bound of the input polynomial, and the pair a_j, b_j will denote the complex number c_j = a_j + ib_j as the coefficient of x^j of the input polynomial. Note that n will be an integer, and a_j, b_j will be floating point numbers.
If the first input is 1, the inverse FFT algorithm must be run. The input that follows is n, y_0, z_0, y_1, z_1, ... y_n-1, z_n-1. The pair y_j, z_j specifies the complex number y_j + iz_j to be A(w^j) for some polynomial A, that is, it is the jth coordinate of a given DFT.
Once the input is specified, your program should compute the FFT or the inverse FFT as requested and present the output in vector form.
Example Input :
0 4 0 0 1.0 0 2.0 0 3.0 0
Example output:
4 6.0 0 -2.0 -2.0 -2.0 0 -2.0 2.0
That is, the DFT of x + 2x^2 + 3x^3 is the vector [6, -2 - 2i, -2, -2 + 2i]
Example Input :
1 4 6.0 0 -2.0 -2.0 -2.0 0 -2.0 2.0
Example output:
4 0 0 1.0 0 2.0 0 3.0 0
That is, the inverse DFT of the vector [6, -2 - 2i, -2, -2 + 2i] is the polynomial x + 2x^2 + 3x^3
Added by: | Programming Club, IITK |
Date: | 2017-06-02 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |