Discrete Fourier transform
From ScienceZero
The DFT has no restrictions on array size (n) and is hard to get wrong. It is a very expensive transform that takes O*n2 operations.
'Complex Forward transform For i = 0 To n - 1 arg = -(2 * PI * i) / n For k = 0 To n - 1 cosarg = Cos(k * arg) sinarg = Sin(k * arg) dataOutR(i) = dataOutR(i) + (dataInR(k) * cosarg - dataInI(k) * sinarg) dataOutI(i) = dataOutI(i) + (dataInR(k) * sinarg + dataInI(k) * cosarg) Next k dataOutR(i) = dataOutR(i) / n dataOutI(i) = dataOutI(i) / n Next i
'Real Forward transform For i = 0 To n - 1 arg = -(2 * PI * i) / n For k = 0 To n - 1 dataOutR(i) = dataOutR(i) + (dataInR(k) * Cos(k * arg) + (dataInR(k) * Sin(k * arg)) Next k dataOutR(i) = dataOutR(i) / n Next i
'Complex Reverse transform For i = 0 To n - 1 arg = (2 * PI * i) / n For k = 0 To n - 1 cosarg = Cos(k * arg) sinarg = Sin(k * arg) dataOutR(i) = dataOutR(i) + (dataInR(k) * cosarg - dataInI(k) * sinarg) dataOutI(i) = dataOutI(i) + (dataInR(k) * sinarg + dataInI(k) * cosarg) Next k Next i
'Real Reverse transform For i = 0 To n - 1 arg = (2 * PI * i) / n For k = 0 To n - 1 dataOutR(i) = dataOutR(i) + (dataInR(k) * Cos(k * arg) + (dataInR(k) * Sin(k * arg)) Next k Next i