One of the more interesting routines in my code arsenal is the FFT, which I have included below. The accompanying image shows it being used to process a picture of delicious cake, but it can be used for a variety of other purposes.
Code:
void forwardFFT(float *real, float *imag, int size)
{
int j = size / 2;
for(int i = 1; i <= size - 2; i++)
{
if(i < j)
{
const float tr = real[j];
const float ti = imag[j];
real[j] = real[i];
imag[j] = imag[i];
real[i] = tr;
imag[i] = ti;
}
int k = size / 2;
while(k <= j)
{
j -= k;
k /= 2;
}
j += k;
}
for(int k = 1; k <= (int)(logf(size) / logf(2)); k++)
{
const int le = (int)(powf(2, k));
const int le2 = le / 2;
float ur = 1;
float ui = 0;
float sr = cosf(M_PI / le2);
float si = -sinf(M_PI / le2);
for(int j = 1; j <= le2; j++)
{
for(int i = j - 1; i < size; i += le)
{
const int ip = i + le2;
const float tr = real[ip] * ur - imag[ip] * ui;
const float ti = real[ip] * ui + imag[ip] * ur;
real[ip] = real[i] - tr;
imag[ip] = imag[i] - ti;
real[i] += tr;
imag[i] += ti;
}
const float tr = ur;
ur = tr * sr - ui * si;
ui = tr * si + ui * sr;
}
}
}
void inverseFFT(float *real, float *imag, int size)
{
for(int k = 0; k < size; k++)
imag[k] = -imag[k];
forwardFFT(real, imag, size);
for(int i = 0; i < size; i++)
{
real[i] = real[i] / size;
imag[i] = -imag[i] / size;
}
}
)