IITKESO207A_1P_1  Implement FFT and its inverse
The problem asks you to write code to implement the recursive FFT algorithm and Inverse FFT algorithm. Your program should first take an input 'T' which is the number of test cases. Each test case contains two lines.The first line contains two integers 'op' and 'n' . If 'op' = 0 , perform FFT , otherwise perform Inverse FFT. , 'n' denotes the degree bound of the input polynomial. The next line contain 'n' elements . If op = 0 ,the input will be of the form a_0, b_0, a_1, b_1, ..., a_n1, b_n1. Here, 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 op=1, the input that follows is y_0, z_0, y_1, z_1, ... y_n1, z_n1. 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.
Update 1 (17/08/2017)
Make sure you output the numbers using this format , "%.6lf %.6lf\n" ,(num.real_part,num.imaginary_part) . Note that the output below contains "0.000000". This happens when you use the given format.
Use double instead of float. Use pi = acos(1.0) for better precision.
We are now ingoring errors <=10^3. Please submit your code again.
Constraints
Test cases = 100
n <= 2^14
100 <= a,b,y,j <= 100
Example Input :
2
0 4
0 0 1.0 0 2.0 0 3.0 0
1 4
6.0 0 2 2 2 0 2 2
Example output:
6.000000 0.000000
2.000000 2.000000
2.000000 0.000000
2.000000 2.000000
0.000000 0.000000
1.000000 0.000000
2.000000 0.000000
3.000000 0.000000
The next 4 lines of the output is the result of the inverse DFT algorithm. Input = [6, 2  2i, 2, 2 + 2i] , Output = x + 2x^2 + 3x^3
hide comments
Programming Club, IITK:
20170830 15:31:58
@dhruvbh : No, whitespaces don't matter. Read update given on 17/08/2017 carefully, there are enough hints to get through most common mistakes.


vipulbjj:
20170830 15:13:48
Will time and memory be considered in grading? 

dhruvbh:
20170830 14:52:19
Is it possible that my code is judged as Wrong because the output I am getting is 6.000000 0.000000


Programming Club, IITK:
20170830 10:06:19
@shashikg : no 

shashikg:
20170830 07:29:27
is there is any marks for comments or indentations?? 

Programming Club, IITK:
20170829 17:54:33
@lightstark1 : yes, n is always a power of 2


chitrak:
20170829 16:28:54
The status of submission says accepted. Will there be more test cases on which the code will be checked on in the future?


lightstark1:
20170829 15:54:56
Do we know anything about 'n', is it always a power of 2? 

Programming Club, IITK:
20170825 19:53:17
@robsr : there are no blank lines before or in between the inputs. Something else is wrong with your code.


ubarsaiyan:
20170825 19:28:12
can n be zero for an input?

Added by:  Programming Club, IITK 
Date:  20170817 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 