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

Include dependency graph for inverse_fast_fourier_transform.cpp:

Go to the source code of this file.

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.
static void	test ()
	Self-test implementations.
int	main ()
	Main function calls automated test function to test the working of fast fourier transform.

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

Definition in file inverse_fast_fourier_transform.cpp.

Function Documentation

main()

int main

(

void

)

Main function calls automated test function to test the working of fast fourier transform.

Returns

0 on exit

Definition at line 155 of file inverse_fast_fourier_transform.cpp.

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

test()

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

Definition at line 101 of file inverse_fast_fourier_transform.cpp.

                   {
    /* descriptions of the following test */
 
    auto *t1 = new std::complex<double>[2];  
    auto *t2 = new std::complex<double>[4];  
 
    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}};  
 
    std::vector<std::complex<double>> r2 = {
        {1, 0}, {2, 0}, {3, 0}, {4, 0}};  
 
    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));  
    }
 
    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));  
    }
 
    delete[] t1;
    delete[] t2;
    delete[] o1;
    delete[] o2;
    std::cout << "All tests have successfully passed!\n";
}