# What to look for in a discrete fourier transform

I was attempting to do a discrete Fourier transform through a computer program on a list of numbers. Before doing that I decided to test it by running through a list of 1000 numbers which I created by summing 20 sine waves which were created by the formula sin(2*pi*integer between 1 and 1000/ desired frequency). Based upon my understanding of the DFT I should have got a 0 for all values except for my twenty desired frequencies of 8, 13, 13, 14, 18, 23, 25, 32, 33, 38, 41, 48, 51, 64, 73, 79, 82, 85, 91, and 100. Some of my first outputs were:

0 : (-140.00101976200014-0j)
1 : (-140.50548903670193-3.1117640585553277j)
2 : (-142.0510770346883-6.33051372898894j)
3 : (-144.74035295772114-9.776661681575883j)
4 : (-148.76670548437778-13.601419744876273j)
5 : (-154.45783389980753-18.014310511371548j)
6 : (-162.3639888189583-23.333771555566614j)


From this program in python 3.2:

import cmath

def compute_dft(input):

n = len(input)
output =  * n
for k in range(n):
s = 0
for t in range(n):
s += input[t] * cmath.exp(-1j * 2 * cmath.pi * t * k / n)
output[k] = -s
return output


print(answer.index(item), ":", item)


I then went and checked the program on some examples of a DFT online and found that the answers it spit out were the same as the examples answers, which led me to wonder if my expectations of the output was wrong.

Any advice on resolving my problem would be much appreciated.

• That depends. What formula (including the normalization) for the DFT are you using? – J. M. Jun 17 '13 at 1:07

Your input is not the sum of sine functions. I think if you print out the values of s, you'll find that it has complex values. Replace

cmath.exp(-1j * 2 * cmath.pi * t * k / n)


with

cmath.sin(2 * cmath.pi * t * k / n)


and you should be set.

Also, due to finite precision arithmetic, you may see some tiny terms outside the 20 frequencies you expect to see.