Instructions: The precise input-output format will be speci ed by Programming TAs for SPOJ. Problem 1. FFT
Write the following program. Input: Given a polynomial A(x) that is speci ed by providing
its degree n 1, and its n coe cients a0; a1; : : : ; an 1 in order. Let a be the n-dimensional vector of its coe cients. Output DFT (a; n). Recall that DFT (a; n) is de ned as
2
A(wn0)
3
DFT(a; n) =
A(wn1)
:
6
...
7
6
7
6
7
4
5
A(wnn 1)
Write the following program. Given an n-dimensional vector of complex numbers y = [y0; y1; : : : ; yn 1] output DFTn 1(y). See note 2 below.
Notes.
Note that the input coe cients for A(x) can be complex numbers.
Let Fn denote the n n DFT matrix. That is,
2
3
Fn = 6
1
1
1
: : :
1
1
!n
!2
: : :
!n 1
1
!n2
!n4
: : : !n2(n 1)7
6
n
n
..
..
..
7
6
.
.
.
7
6
7
6
7
6
7
4
5
!nn 1 !n2(n 1) : : : !n(n 1)2
Recall by taking inner-product of any two columns that Fn Fn = nI. Hence, Fn 1 = n1 Fn and therefore,
(DFT)n 1(y) = (1=n)Fn (y) :
We obtain two ways of computing DFTn 1. From de nition of Fn , we have that Fn is the same as that of Fn with !n replaced by !n = !n 1 = e 2 i=n. So, in the computation of Fny, if we replace the role of !n by !n 1 appropriately throughout, and divide by n, we should obtain DFT 1(y). The second method comes by observing the rows of Fn and relating them to rows of Fn.
2
1
!n
1
1
6
2
Fn =
1
!n.
6
..
6
6
1
n
1
6
!n
4
1
!n2
!n4
...
!n2(n 1)
