A quick and dirty implementation of Discrete Fourier transform (DFT) in Haskell. The algorithm is implemented using the simplified version of Cooley–Tukey FFT algorithm. The implementation is here.
DFT, Inverse DFT and underlying FFT algorithm are tested by simply checking whether the composition of inverse dft and dft produces the same result as the provided input. The test implementation is here. Polynomial Multiplication Algorithm was also used to test underlying DFT algorithm here.
DFT algorithm can be conveniently applied to polynomial multiplication. The result is O(n log n) polynomial multiplication algorithm. The implementation is here. This application was also used to test the FFT implementation, and test cases are here.
In order to build dft from the source, you will need a Haskell stack.
Build:
- Clone the project
- Run stack build in the root of the repository
- This should automatically pull dependencies, compile and build
Run in interactive mode: Run stack ghci in the app folder of the repository
Test: Run stack test in the root of the repository