C++ Program to Compute Discrete Fourier Transform using Fast Fourier Transform Approach

This is a C++ Program to perform Fast Fourier Transform. A fast Fourier transform (FFT) is an algorithm to compute the discrete Fourier transform (DFT) and its inverse. Fourier analysis converts time (or space) to frequency and vice versa; an FFT rapidly computes such transformations by factorizing the DFT matrix into a product of sparse (mostly zero) factors.

Here is source code of the C++ Program to Compute Discrete Fourier Transform Using the Fast Fourier Transform Approach. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

1. `#include <iostream>`
2. `#include <complex>`
3. `#include <cmath>`
4. `#include <iterator>`
5. `using namespace std;`
6. ` `
7. `unsigned int bitReverse(unsigned int x, int log2n)`
8. ` `
9. `{`
10. `    int n = 0;`
11. `    int mask = 0x1;`
12. `    for (int i = 0; i < log2n; i++)`
13. ` `
14. `    {`
15. `        n <<= 1;`
16. `        n |= (x & 1);`
17. `        x >>= 1;`
18. `    }`
19. `    return n;`
20. `}`
21. `const double PI = 3.1415926536;`
22. `template<class Iter_T>`
23. `void fft(Iter_T a, Iter_T b, int log2n)`
24. `{`
25. `    typedef typename iterator_traits<iter_t>::value_type complex;`
26. `    const complex J(0, 1);`
27. `    int n = 1 << log2n;`
28. `    for (unsigned int i = 0; i < n; ++i)`
29. `    {`
30. `        b[bitReverse(i, log2n)] = a[i];`
31. `    }`
32. ` `
33. `    for (int s = 1; s <= log2n; ++s)`
34. ` `
35. `    {`
36. `        int m = 1 << s;`
37. `        int m2 = m >> 1;`
38. `        complex w(1, 0);`
39. `        complex wm = exp(-J * (PI / m2));`
40. `        for (int j = 0; j < m2; ++j)`
41. ` `
42. `        {`
43. `            for (int k = j; k < n; k += m)`
44. ` `
45. `            {`
46. `                complex t = w * b[k + m2];`
47. `                complex u = b[k];`
48. `                b[k] = u + t;`
49. `                b[k + m2] = u - t;`
50. `            }`
51. `            w *= wm;`
52. `        }`
53. `    }`
54. `}`
55. `int main(int argc, char **argv)`
56. `{`
57. `    typedef complex cx;`
58. `    cx a[] = { cx(0, 0), cx(1, 1), cx(3, 3), cx(4, 4), cx(4, 4), cx(3, 3), cx(`
59. `            1, 1), cx(0, 0) };`
60. `    cx b[8];`
61. `    fft(a, b, 3);`
62. `    for (int i = 0; i < 8; ++i)`
63. `        cout << b[i] << "\n";`
64. ` `
65. `}`

Output:

```\$ g++ FFT.cpp
\$ a.out

(16,16)
(-4.82843,-11.6569)
(0,0)
(-0.343146,0.828427)
(0,0)
(0.828427,-0.343146)
(0,0)
(-11.6569,-4.82843)```

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.