inverse_fast_fourier_transform.cpp File Reference

An inverse fast Fourier transform (IFFT) is an algorithm that computes the inverse fourier transform. More...

#include <cassert>
#include <cmath>
#include <complex>
#include <iostream>
#include <vector>

Include dependency graph for inverse_fast_fourier_transform.cpp:

Namespaces
namespace	numerical_methods
	for assert

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

Detailed Description

An inverse fast Fourier transform (IFFT) is an algorithm that computes the inverse fourier transform.

This algorithm has an application in use case scenario where a user wants find coefficients of a function in a short time by just using points generated by DFT. Time complexity this algorithm computes the IDFT 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

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] = {3, 0};
    t1[1] = {-1, 0};
    t2[0] = {10, 0};
    t2[1] = {-2, -2};
    t2[2] = {-2, 0};
    t2[3] = {-2, 2};
 
    uint8_t n1 = 2;
    uint8_t n2 = 4;
    std::vector<std::complex<double>> r1 = {
        {1, 0}, {2, 0}};  /// True Answer for test case 1
 
    std::vector<std::complex<double>> r2 = {
        {1, 0}, {2, 0}, {3, 0}, {4, 0}};  /// True Answer for test case 2
 
    std::complex<double> *o1 =
        numerical_methods::InverseFastFourierTransform(t1, n1);
 
    std::complex<double> *o2 =
        numerical_methods::InverseFastFourierTransform(t2, n2);
 
    for (uint8_t i = 0; i < n1; i++) {
        assert((r1[i].real() - o1[i].real() < 0.000000000001) &&
               (r1[i].imag() - o1[i].imag() <
                0.000000000001));  /// Comparing for both real and imaginary
                                   /// values for test case 1
    }
 
    for (uint8_t i = 0; i < n2; i++) {
        assert((r2[i].real() - o2[i].real() < 0.000000000001) &&
               (r2[i].imag() - o2[i].imag() <
                0.000000000001));  /// Comparing for both real and imaginary
                                   /// values for test case 2
    }
 
    delete[] t1;
    delete[] t2;
    delete[] o1;
    delete[] o2;
    std::cout << "All tests have successfully passed!\n";
}

Here is the call graph for this function: