I made a program in C++ that converts real signal from the time domain into the frequency domain using FFT. I used a Euler’s formula to separate calculations for real and imaginary parts of signal. As the result i get odd outputs, where in addition to the correct harmonics, extra harmonics appear.

For example for the input {9, -2.82, -5, 2.82, 1, 2.82, -5, -2.82, 9, -2.82, -5, 2.82, 1, 2.82, -5, -2.82} with 16 elements the result is: {0,0,8,0,40,0,24,0,0,0,24,0,40,0,8,0} when it should be {0,0, 0,40,0,32,0,0,0,32,0,40,0,0,0}. I am stuck at this point. Please help.
Here’s my code:

// for example dn = {9, -2.82, -5, 2.82, 1, 2.82, -5, -2.82, 9, -2.82, -5, 2.82, 1, 2.82, -5, -2.82}, kn = 16 is the length of array
printf("n-----------------------------------------------------------Shifted Data--------------------------------------------------------------------------------------------------------n");
float* dm = (float*)malloc(kn * sizeof(float));

uint32_t rev = 0;
uint32_t n = 0;
int order = 0;
for (int i = 0; i < kn; i++) {
    n = i;
    if (!(n & (n - 1)))
        order++;
    for (int j = 0; j < log2(kn); j++) {  // shift input data 
        rev = rev << 1;
        rev = rev | (n & 1);
        n = n >> 1;
    }
//  printf("rev = %d, i = %d order = %dn", rev, i, order);
//  std::cout << "rev = " << std::bitset<9>(rev) << " i = " << std::bitset<9>(i) <<std::endl;
    dm[i] = dn[rev];
    printf("dm[%d] = %f d[%d] = %f, %dnn", i, dm[i], i, dn[i], rev);
    rev = 0;
}

int numselect = kn;
int selectcounter = 0;

while (numselect != 1) {
    numselect = numselect / 2;
    selectcounter++;
}

selectcounter--;
int tempval1 = 0;
int tempval2 = 0;
int tempvalcounter = 0;
int counter = 0;
double **ftnreal = new double* [log2(kn)]; // m*N array for real output
for (int i = 0; i < log2(kn); i++)
    ftnreal[i] = new double[kn];

selectcounter = 0;
for (int i = 0; i < log2(kn); i++) {
    for (int j = 0; j < kn; j++)
        ftnreal[i][j] = 0.0;
    if (i == 0) {
        for (int j = 0; j < kn / 2; j++) {
            ftnreal[i][j * 2] = dm[2 * j] + cos(2 * M_PI * i / 2) * dm[2 * j + 1]; //calculating data for the first column of elements
            ftnreal[i][j * 2 + 1] = dm[2 * j] - cos(2 * M_PI * i / 2) * dm[2 * j + 1];
            printf("ftnreal[%d][%d] = dm[%d] + cos(2 * %f*%d/2)*dm[%d]n", i, j*2,j*2,M_PI,i,2*j + 1);
            printf("ftnreal[%d][%d] = dm[%d] - cos(2 * %f*%d/2)*dm[%d]n", i, j * 2 + 1, j * 2, M_PI, i, 2 * j + 1);
        }
    }
    else {
        tempval1 = pow(2, i + 1);
        tempval2 = pow(2, i);
        counter = 0;
        tempvalcounter = 0;
        printf("i = %d, tempval1 = %d, tempval2 = %dn", i, tempval1, tempval2);
        for (int j = 0; j < kn / 2; j++) {
                ftnreal[i][counter] = ftnreal[i - 1][counter] + cos(2 * M_PI * (float(tempvalcounter) / float(tempval1))) * ftnreal[i - 1][counter + tempval2]; //calculating data for the rest of columns
                ftnreal[i][counter + tempval2] = ftnreal[i - 1][counter] - cos(2 * M_PI * (float(tempvalcounter) / float(tempval1))) * ftnreal[i - 1][counter + tempval2];
                printf("ftnreal[%d][%d] = ftnreal[%d][%d] + cos(2*%f*(%f/%f))*ftnreal[%d][%d]       / %f      %fn", i,counter,i - 1,counter,M_PI,float(tempvalcounter), float(tempval1),i - 1,counter + tempval2, float(tempvalcounter) / float(tempval1), cos(2 * M_PI * (float(tempvalcounter) / float(tempval1))));
                printf("ftnreal[%d][%d] = ftnreal[%d][%d] - cos(2*%f*(%f/%f))*ftnreal[%d][%d]       / %f      %fn", i, counter + tempval2, i - 1, counter, M_PI, float(tempvalcounter), float(tempval1), i - 1, counter + tempval2, float(tempvalcounter) / float(tempval1), cos(2 * M_PI * (float(tempvalcounter) / float(tempval1))));
                counter++;
                tempvalcounter++;
                if (tempvalcounter % tempval2 == 0) {
                    counter = counter + tempval2;
                    tempvalcounter = 0;
                }
        }
    }
    cout << endl;
}


double** ftnimag = new double* [log2(kn)]; // same goes for imaginary part
for (int i = 0; i < log2(kn); i++)
    ftnimag[i] = new double[kn];

for (int i = 0; i < log2(kn); i++) {
    for (int j = 0; j < kn; j++)
        ftnimag[i][j] = 0.0;
    if (i == 0) {
        for (int j = 0; j < kn/2; j++) {
            ftnimag[i][j * 2] = -sin(2 * M_PI * i / 2) * dm[2 * j + 1];
            ftnimag[i][j * 2 + 1] = sin(2 * M_PI * i / 2) * dm[2 * j + 1];
        }
    }
    else {
        tempval1 = pow(2, i + 1);
        tempval2 = pow(2, i);
        counter = 0;
        int tempvalcounter = 0;
        printf("i = %d, tempval1 = %d, tempval2 = %dn", i, tempval1, tempval2);
        for (int j = 0; j < kn / 2; j++) {
            ftnimag[i][counter] = ftnimag[i - 1][counter] - sin(2 * M_PI * (float(tempvalcounter) / float(tempval1))) * ftnimag[i - 1][counter + tempval2];
            ftnimag[i][counter + tempval2] = ftnimag[i - 1][counter] + sin(2 * M_PI * (float(tempvalcounter) / float(tempval1))) * ftnimag[i - 1][counter + tempval2];
            printf("ftnreal[%d][%d] = ftnimag[%d][%d] - sin(2*%f*(%f/%f))*ftnreal[%d][%d]       / %f     %fn", i, counter, i - 1, counter, M_PI, float(tempvalcounter), float(tempval1), i - 1, counter + tempval2, float(tempvalcounter) / float(tempval1), -sin(2*M_PI* (float(tempvalcounter) / float(tempval1))));
            printf("ftnreal[%d][%d] = ftnimag[%d][%d] + sin(2*%f*(%f/%f))*ftnreal[%d][%d]       / %f    %fn", i, counter + tempval2, i - 1, counter,M_PI, float(tempvalcounter), float(tempval1), i - 1, counter + tempval2, float(tempvalcounter) / float(tempval1), sin(2*M_PI* (float(tempvalcounter) / float(tempval1))));
            counter++;
            tempvalcounter++;
            if (tempvalcounter % tempval2 == 0) {
                counter = counter + tempval2;
                tempvalcounter = 0;
            }
        }
    }
    cout << endl;
}
printf("-----------------------------------------------------------Real--------------------------------------------------------------------------------------------------------n");

//printf("%d", selectcounter);
for (int i = 0; i < log2(kn); i++) {
    for (int j = 0; j < kn; j++) {
        cout << ftnreal[i][j] << " ";
    }
    cout << endl;
    cout << endl;
    cout << endl;
}

printf("-----------------------------------------------------------Imaginary--------------------------------------------------------------------------------------------------------n");

for (int i = 0; i < log2(kn); i++) {
    for (int j = 0; j < kn; j++) {
        cout << ftnimag[i][j] << " ";
    }
    cout << endl;
    cout << endl;
    cout << endl;
}

printf("-----------------------------------------------------------Abs--------------------------------------------------------------------------------------------------------n");

tempval1 = log2(kn) - 1;
printf("%dn", tempval1);
float* ftnabs = (float*)malloc(kn * sizeof(float));
for (int i = 0; i < kn; i++) {
    ftnabs[i] = sqrt(ftnreal[tempval1][i] * ftnreal[tempval1][i] + ftnimag[tempval1][i] * ftnimag[tempval1][i]);
    cout << ftnabs[i] << " ";
    cout << 2 * ftnabs[i] / kn << " ";
}