CSI3108-01 Programming HW#3 (Divide-and-Conquer)

Description

Implement FFT in the textbook for polynomial multiplication using Java. Input
to your program is an arbitary polynomial A(x) in the coefficient representation.
For evaluation, implement the function FFT in Figure 2.9. Assume that all the
coefficients of a polynomial are integers.
Use the following equation for implementation of ω.
,
where 𝑖=√(−1), and the circular constant 𝜋 have to be matched by 3.141592.
2
Input
The first line has the number of test cases. From the second line, each test case is given in a
single line by ordering coefficients from the constant to the highest degree. Note that the
highest degree of a polynomial is 63.
Output
For each test case, print ‘#test case number’ in the first line. And then print n values; one value
per line in the form of ‘real part imaginary part’, where n is the number of points.
Sample Input
20 // the no of test cases = 20
2 1 2 3 // highest deg=2, 1 + 2𝑥 + 3𝑥2
5 -6 -5 -4 -3 -2 -1 // hightest deg=5, -6 – 5𝑥 – 4𝑥2 – 3𝑥3 – 2𝑥4 – 𝑥5
7 0 1 2 3 4 5 6 7 // example in your text book
…
Sample Output
#1
6.000000 0.000000
-2.000000 2.000000
2.000000 0.000000
-2.000000 -2.000000
#2
-21.000000 0.000000
-4.707108 -8.949747
-4.000000 -3.000000
-3.292894 -0.949748
-3.000000 0.000000
-3.292892 0.949747
-4.000000 3.000000
-4.707106 8.949748
#3
28.000000, 0.000000
-4.000001 -9.656854
-4.000000 -4.000000
-4.000001 -1.656854
-4.000000 0.000000
-3.999999 1.656854
-4.000000 4.000000
-3.999999 9.656854
#4
…