fast_fourier_transform.cpp File Reference

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 <iostream>
#include <vector>

Include dependency graph for fast_fourier_transform.cpp:

Namespaces
namespace	numerical_methods
	for assert

Functions
std::complex< double > *	numerical_methods::FastFourierTransform (std::complex< double > *p, uint8_t n)
	FastFourierTransform is a recursive function which returns list of complex numbers.
static void	test ()
	Self-test implementations.
int	main (int argc, char const *argv[])
	Main function.

Detailed Description

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).

Author

Ameya Chawla

Function Documentation

main()

int main	(	int	argc,
		char const *	argv[] )

Main function.

Parameters

argc	commandline argument count (ignored)
argv	commandline array of arguments (ignored) calls automated test function to test the working of fast fourier transform.

Returns

0 on exit

                                       {
    test();  //  run self-test implementations
             //  with 2 defined test cases
    return 0;
}

Here is the call graph for this function:

test()

static void test ( )

static

Self-test implementations.

Declaring two test cases and checking for the error in predicted and true value is less than 0.000000000001.

Returns

void

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

                   {
    /* 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";
}

Here is the call graph for this function: