Loading...
Searching...
No Matches
A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). More...
#include <cassert>#include <cmath>#include <complex>#include <cstdint>#include <iostream>#include <vector>
Go to the source code of this file.
std::complex< double > * numerical_methods::FastFourierTransform (std::complex< double > *p, uint8_t n) FastFourierTransform is a recursive function which returns list of complex numbers.A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT).
This algorithm has application in use case scenario where a user wants to find points of a function in a short time by just using the coefficients of the polynomial function. It can be also used to find inverse fourier transform by just switching the value of omega. Time complexity this algorithm computes the DFT in O(nlogn) time in comparison to traditional O(n^2).
Definition in file fast_fourier_transform.cpp.
◆ main()Main function calls automated test function to test the working of fast fourier transform.
Definition at line 161 of file fast_fourier_transform.cpp.
161 {
163
164 return 0;
165}
static void test()
Self-test implementations.
◆ test()Self-test implementations.
Declaring two test cases and checking for the error in predicted and true value is less than 0.000000000001.
Test case 1
Test case 2
True Answer for test case 1
True Answer for test case 2
Temporary variable used to delete memory location of o1
Temporary variable used to delete memory location of o2
Comparing for both real and imaginary values for test case 1
Comparing for both real and imaginary values for test case 2
Definition at line 105 of file fast_fourier_transform.cpp.
105 {
106
107
108 auto *t1 = new std::complex<double>[2];
109 auto *t2 = new std::complex<double>[4];
110
111 t1[0] = {1, 0};
112 t1[1] = {2, 0};
113 t2[0] = {1, 0};
114 t2[1] = {2, 0};
115 t2[2] = {3, 0};
116 t2[3] = {4, 0};
117
118 uint8_t n1 = 2;
119 uint8_t n2 = 4;
120 std::vector<std::complex<double>> r1 = {
121 {3, 0}, {-1, 0}};
122
123 std::vector<std::complex<double>> r2 = {
124 {10, 0}, {-2, -2}, {-2, 0}, {-2, 2}};
125
127 std::complex<double> *t3 =
128 o1;
130 std::complex<double> *t4 =
131 o2;
132 for (uint8_t i = 0; i < n1; i++) {
133 assert((r1[i].real() - o1->real() < 0.000000000001) &&
134 (r1[i].imag() - o1->imag() <
135 0.000000000001));
137 o1++;
138 }
139
140 for (uint8_t i = 0; i < n2; i++) {
141 assert((r2[i].real() - o2->real() < 0.000000000001) &&
142 (r2[i].imag() - o2->imag() <
143 0.000000000001));
145 o2++;
146 }
147
148 delete[] t1;
149 delete[] t2;
150 delete[] t3;
151 delete[] t4;
152 std::cout << "All tests have successfully passed!\n";
153}
std::complex< double > * FastFourierTransform(std::complex< double > *p, uint8_t n)
FastFourierTransform is a recursive function which returns list of complex numbers.
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4