DFT.cc

#include <iostream>
#include <complex>
#include <cmath>
#include <vector>
using namespace std;
using cplx=complex<double>;

template<typename T>
constexpr T pi(){
  return 3.141592653589793238463L;
}

enum FToption{
  IDFT=-1,
  DFT=1
};

void FT_DataShift(vector<cplx> &data){
  int size=data.size();
  for(int i=0;i<size/2;i++){
    auto swap_tmp=data[i];
    data[i]=data[i+size/2];
    data[i+size/2]=swap_tmp;
  }
}


void FourierTransform(vector<cplx> &data,FToption option){
  FT_DataShift(data);
  int size=data.size();
  vector<cplx> buf(size);
  if(option==IDFT){
    for(int i=0;i<size;i++){
      data[i]/=size;
    }
  }
  for(int i=0;i<size;i++){
    for(int j=0;j<size;j++){
      buf[i]+=data[j]*exp(cplx(0,-2.0*pi<double>()*i*j/size*(int)option));
    }
  }
  for(int i=0;i<size;i++){
    data[i]=buf[i];
  }
  FT_DataShift(data);
}


int main(){
  const int size=128;
  vector<cplx> data(size);
  int i=0;
  
  for(int i=0;i<size;i++){
    data[i].imag(0);
    if(i==size/2)data[i].real(255.0);
  }
  FourierTransform(data,DFT);
  for(int i=0;i<size;i++){
    cout<<data[i]<<endl;
  }

  FourierTransform(data,IDFT);
  for(int i=0;i<size;i++){
    cout<<data[i]<<endl;
  }

}