Today is a really happy night for me, after alot of searching and learning programming I have developed a bit reversing program written in C++ and directed towards implementation of FFT. The program inputs the data as vectors and then stores all the vectors at even places as real vectors and all vectors at imaginary places as imaginary vectors. This means the real part of the vector occupies position f(0), f(2), f(4) and so on. Similarly for imaginary parts of the vectors.
Once we have input the data I exploit the symmetry called the mirror symetry that the top half portion of the numbers to be bit reversed is the image of the bottom half numbers to be bit reversed or vice versa.
Hence one way to make the algorithm fast is to divide it in top and bottom and do the bit reversing for both in the same step, treating it as the mirror image of the another. One can work out the steps of algorithm by hand first to see that they give the proper answer. I had been searching alot on internet but could not find much help directly and in bits n pieces as a newbie to C++ I developed the first version of my program. There will be improvments in it every day till it is perfect but for the kodak moment that it is for me I could not resist the tempation of helping others out by giving them a handy program just to be copied and run by g++!.
Here is the code
#include < iostream >
#include < fstream >
#include < cmath >
#include < complex >
#include < vector >
#define swap(a,b) {temp=a;a=b;b=temp;}
using std::cout;
using std::cin;
using std::endl;
using std::ofstream;
using std::ifstream;
using std::complex;
using std::vector;
int main()
{
ofstream file ("swap.dat");
//complex < double > I = complex < double >(0,1);
int x,i,j,k,n,m;
const int N=16;
double temp;
vector < float > realdata(N);
vector < float > imagdata(N);
n=N/2;
for(x=0;x < n;x++){
realdata[2*x]=x; imagdata[2*x+1]=x;
}
j=0;
for(i=2;i
while(j>=m){
j-=m;
m>>=1;
}
j+=m;
if(j>i){
swap(realdata[j],realdata[i]);
swap(imagdata[j+1],imagdata[i+1]);
if(j < n)
{
swap(realdata[N-j-2],realdata[N-i-2]);
swap(imagdata[N-j-1],imagdata[N-i-1]);
}
}
}
for(i=0;i< n;i++){
file << realdata[2*i]<< " "<< imagdata[2*i+1] << endl;
}
return 0;
}
Enjoy!!
