feat: Implemented Fast Fourier Transform algorithm (TheAlgorithms#1700)

* feat ; Implemented Fast Fourier Transform * feat : Implemented Fast Fourier Transform * fix : added comments to header * Fixing Code Formatter errors * fix : updated the documentation * fix : removed bad practice of using namespace td * Update numerical_methods/fast_fourier_transform.cpp Co-authored-by: David Leal <halfpacho@gmail.com> * Update numerical_methods/fast_fourier_transform.cpp Co-authored-by: David Leal <halfpacho@gmail.com> * Update numerical_methods/fast_fourier_transform.cpp Co-authored-by: David Leal <halfpacho@gmail.com> * Update numerical_methods/fast_fourier_transform.cpp Co-authored-by: David Leal <halfpacho@gmail.com> * Update numerical_methods/fast_fourier_transform.cpp Co-authored-by: David Leal <halfpacho@gmail.com> * Update numerical_methods/fast_fourier_transform.cpp Co-authored-by: David Leal <halfpacho@gmail.com> * updating DIRECTORY.md * fix : fixed the integer values with their appropriate size * Fixed errors * Update fast_fourier_transform.cpp * Update fast_fourier_transform.cpp * Fixed many errors * fix : fixed array errors * fix: fixing memory leak errors * fix: using delete instead of free as mentioned in errors * fix : using delete[ ] instead of delete * fix : fixing errors for memory leaks * Update fast_fourier_transform.cpp * Update numerical_methods/fast_fourier_transform.cpp Co-authored-by: David Leal <halfpacho@gmail.com> * Update numerical_methods/fast_fourier_transform.cpp Co-authored-by: David Leal <halfpacho@gmail.com> * Update numerical_methods/fast_fourier_transform.cpp Co-authored-by: David Leal <halfpacho@gmail.com> * Update numerical_methods/fast_fourier_transform.cpp Co-authored-by: David Leal <halfpacho@gmail.com> * clang-format and clang-tidy fixes for a6594c8 * fix : updated documentation * fix : added time complexity in documentation * Update numerical_methods/fast_fourier_transform.cpp Co-authored-by: David Leal <halfpacho@gmail.com> * Update numerical_methods/fast_fourier_transform.cpp Co-authored-by: David Leal <halfpacho@gmail.com> * Update numerical_methods/fast_fourier_transform.cpp Co-authored-by: David Leal <halfpacho@gmail.com> * Update numerical_methods/fast_fourier_transform.cpp Co-authored-by: David Leal <halfpacho@gmail.com> * fix : update code as per the namespace numerical_methods * fix : use of auto keyword to reduce complexity * fix : updated documentation * fix : fixed segmentation fault error * fix : fixing clang-tidy errors * fix : fixing clang-tidy errors * Update fast_fourier_transform.cpp * Update fast_fourier_transform.cpp * Update fast_fourier_transform.cpp * Update fast_fourier_transform.cpp * Update fast_fourier_transform.cpp * Update fast_fourier_transform.cpp * Update fast_fourier_transform.cpp * fix : updated documentation * fix : fixing warnings * Update fast_fourier_transform.cpp * Update fast_fourier_transform.cpp * Update numerical_methods/fast_fourier_transform.cpp Co-authored-by: David Leal <halfpacho@gmail.com> * Update numerical_methods/fast_fourier_transform.cpp Co-authored-by: David Leal <halfpacho@gmail.com> * Update numerical_methods/fast_fourier_transform.cpp Co-authored-by: David Leal <halfpacho@gmail.com> * Update numerical_methods/fast_fourier_transform.cpp Co-authored-by: David Leal <halfpacho@gmail.com> * clang-format and clang-tidy fixes for 198b429 * Update fast_fourier_transform.cpp * Update numerical_methods/fast_fourier_transform.cpp Co-authored-by: David Leal <halfpacho@gmail.com> * Update numerical_methods/fast_fourier_transform.cpp Co-authored-by: David Leal <halfpacho@gmail.com> * Update numerical_methods/fast_fourier_transform.cpp Co-authored-by: David Leal <halfpacho@gmail.com> * Update numerical_methods/fast_fourier_transform.cpp Co-authored-by: David Leal <halfpacho@gmail.com> * Update numerical_methods/fast_fourier_transform.cpp Co-authored-by: David Leal <halfpacho@gmail.com> * Update numerical_methods/fast_fourier_transform.cpp Co-authored-by: David Leal <halfpacho@gmail.com> * Update numerical_methods/fast_fourier_transform.cpp Co-authored-by: David Leal <halfpacho@gmail.com> * a * Apply suggestions from code review * fix : updating leak memeory * Update fast_fourier_transform.cpp Co-authored-by: David Leal <halfpacho@gmail.com> Co-authored-by: github-actions <${GITHUB_ACTOR}@users.noreply.github.com>
ShuN6211 · Nov 2, 2021 · b4b0864 · b4b0864
1 parent 8a6f205
commit b4b0864
Show file tree

Hide file tree

Showing 2 changed files with 166 additions and 0 deletions.
diff --git a/DIRECTORY.md b/DIRECTORY.md
@@ -225,6 +225,7 @@
   * [Brent Method Extrema](https://github.com/TheAlgorithms/C-Plus-Plus/blob/master/numerical_methods/brent_method_extrema.cpp)
   * [Durand Kerner Roots](https://github.com/TheAlgorithms/C-Plus-Plus/blob/master/numerical_methods/durand_kerner_roots.cpp)
   * [False Position](https://github.com/TheAlgorithms/C-Plus-Plus/blob/master/numerical_methods/false_position.cpp)
+  * [Fast Fourier Transform](https://github.com/TheAlgorithms/C-Plus-Plus/blob/master/numerical_methods/fast_fourier_transform.cpp)
   * [Gaussian Elimination](https://github.com/TheAlgorithms/C-Plus-Plus/blob/master/numerical_methods/gaussian_elimination.cpp)
   * [Golden Search Extrema](https://github.com/TheAlgorithms/C-Plus-Plus/blob/master/numerical_methods/golden_search_extrema.cpp)
   * [Lu Decompose](https://github.com/TheAlgorithms/C-Plus-Plus/blob/master/numerical_methods/lu_decompose.cpp)

diff --git a/numerical_methods/fast_fourier_transform.cpp b/numerical_methods/fast_fourier_transform.cpp
@@ -0,0 +1,165 @@
+/**
+ * @file
+ * @brief [A fast Fourier transform
+ * (FFT)](https://medium.com/@aiswaryamathur/understanding-fast-fouriertransform-from-scratch-to-solve-polynomial-multiplication-8018d511162f)
+ * is an algorithm that computes the
+ * discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT).
+ * @details
+ * 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).
+ * @author [Ameya Chawla](https://github.com/ameyachawlaggsipu)
+ */
+
+#include <cassert>   /// for assert
+#include <cmath>     /// for mathematical-related functions
+#include <complex>   /// for storing points and coefficents
+#include <iostream>  /// for IO operations
+#include <vector>    /// for std::vector
+
+/**
+ * @namespace numerical_methods
+ * @brief Numerical algorithms/methods
+ */
+namespace numerical_methods {
+/**
+ * @brief FastFourierTransform is a recursive function which returns list of
+ * complex numbers
+ * @param p List of Coefficents in form of complex numbers
+ * @param n Count of elements in list p
+ * @returns p if n==1
+ * @returns y if n!=1
+ */
+std::complex<double> *FastFourierTransform(std::complex<double> *p, uint8_t n) {
+    if (n == 1) {
+        return p;  /// Base Case To return
+    }
+
+    double pi = 2 * asin(1.0);  /// Declaring value of pi
+
+    std::complex<double> om = std::complex<double>(
+        cos(2 * pi / n), sin(2 * pi / n));  /// Calculating value of omega
+
+    auto *pe = new std::complex<double>[n / 2];  /// Coefficients of even power
+
+    auto *po = new std::complex<double>[n / 2];  /// Coefficients of odd power
+
+    int k1 = 0, k2 = 0;
+    for (int j = 0; j < n; j++) {
+        if (j % 2 == 0) {
+            pe[k1++] = p[j];  /// Assigning values of even Coefficients
+
+        } else
+            po[k2++] = p[j];  /// Assigning value of odd Coefficients
+    }
+
+    std::complex<double> *ye =
+        FastFourierTransform(pe, n / 2);  /// Recursive Call
+
+    std::complex<double> *yo =
+        FastFourierTransform(po, n / 2);  /// Recursive Call
+
+    auto *y = new std::complex<double>[n];  /// Final value representation list
+
+    k1 = 0, k2 = 0;
+
+    for (int i = 0; i < n / 2; i++) {
+        y[i] =
+            ye[k1] + pow(om, i) * yo[k2];  /// Updating the first n/2 elements
+        y[i + n / 2] =
+            ye[k1] - pow(om, i) * yo[k2];  /// Updating the last n/2 elements
+
+        k1++;
+        k2++;
+    }
+
+    if(n!=2){
+
+        delete[] pe;
+        delete[] po;
+
+    }
+
+    delete[] ye;  /// Deleting dynamic array ye
+    delete[] yo;  /// Deleting dynamic array yo
+    return y;
+}
+
+}  // namespace numerical_methods
+
+/**
+ * @brief Self-test implementations
+ * @details
+ * Declaring two test cases and checking for the error
+ * in predicted and true value is less than 0.000000000001.
+ * @returns void
+ */
+static void test() {
+    /* descriptions of the following test */
+
+    auto *t1 = new std::complex<double>[2];  /// Test case 1
+    auto *t2 = new std::complex<double>[4];  /// Test case 2
+
+    t1[0] = {1, 0};
+    t1[1] = {2, 0};
+    t2[0] = {1, 0};
+    t2[1] = {2, 0};
+    t2[2] = {3, 0};
+    t2[3] = {4, 0};
+
+    uint8_t n1 = 2;
+    uint8_t n2 = 4;
+    std::vector<std::complex<double>> r1 = {
+        {3, 0}, {-1, 0}};  /// True Answer for test case 1
+
+    std::vector<std::complex<double>> r2 = {
+        {10, 0}, {-2, -2}, {-2, 0}, {-2, 2}};  /// True Answer for test case 2
+
+    std::complex<double> *o1 = numerical_methods::FastFourierTransform(t1, n1);
+    std::complex<double> *t3=o1;  /// Temporary variable used to delete memory location of o1
+    std::complex<double> *o2 = numerical_methods::FastFourierTransform(t2, n2);
+    std::complex<double> *t4=o2; /// Temporary variable used to delete memory location of o2
+    for (uint8_t i = 0; i < n1; i++) {
+        assert((r1[i].real() - o1->real() < 0.000000000001) &&
+               (r1[i].imag() - o1->imag() <
+                0.000000000001));  /// Comparing for both real and imaginary
+                                   /// values for test case 1
+        o1++;
+    }
+
+    for (uint8_t i = 0; i < n2; i++) {
+        assert((r2[i].real() - o2->real() < 0.000000000001) &&
+               (r2[i].imag() - o2->imag() <
+                0.000000000001));  /// Comparing for both real and imaginary
+                                   /// values for test case 2
+        o2++;
+    }
+
+
+    delete[] t1;
+    delete[] t2;
+    delete[] t3;
+    delete[] t4;
+    std::cout << "All tests have successfully passed!\n";
+}
+
+/**
+ * @brief Main function
+ * @param argc commandline argument count (ignored)
+ * @param argv commandline array of arguments (ignored)
+ * calls automated test function to test the working of fast fourier transform.
+ * @returns 0 on exit
+ */
+
+int main(int argc, char const *argv[]) {
+    test();  //  run self-test implementations
+              //  with 2 defined test cases
+    return 0;
+}