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

Include dependency graph for fast_fourier_transform.cpp:

Go to the source code of this file.

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 ()
	Main function calls automated test function to test the working of fast fourier transform.

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

Definition in file 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 161 of file 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

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.

                   {
    /* descriptions of the following test */
 
    auto *t1 = new std::complex<double>[2];  
    auto *t2 = new std::complex<double>[4];  
 
    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}};  
 
    std::vector<std::complex<double>> r2 = {
        {10, 0}, {-2, -2}, {-2, 0}, {-2, 2}};  
 
    std::complex<double> *o1 = numerical_methods::FastFourierTransform(t1, n1);
    std::complex<double> *t3 =
        o1;  
    std::complex<double> *o2 = numerical_methods::FastFourierTransform(t2, n2);
    std::complex<double> *t4 =
        o2;  
    for (uint8_t i = 0; i < n1; i++) {
        assert((r1[i].real() - o1->real() < 0.000000000001) &&
               (r1[i].imag() - o1->imag() <
                0.000000000001));  
        o1++;
    }
 
    for (uint8_t i = 0; i < n2; i++) {
        assert((r2[i].real() - o2->real() < 0.000000000001) &&
               (r2[i].imag() - o2->imag() <
                0.000000000001));  
        o2++;
    }
 
    delete[] t1;
    delete[] t2;
    delete[] t3;
    delete[] t4;
    std::cout << "All tests have successfully passed!\n";
}