-1

My fast fourier transform is seg faulting and I have absolutely no idea as to why. The code below generates a sine wave, runs it through a FFT in an attempt to find the frequency of the sine wave, but it instead throws an error.

#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <vector>   
#include <complex>

# define M_PI 3.14159265358979323846

using namespace std;
using namespace std::complex_literals;

/*
int main()
{
    ofstream outfile;
    outfile.open("data.dat",ios::trunc | ios::out);
    for(int i=0;i<201;i++)
    {
        float rads = M_PI/180;
        outfile << (float)(3276*sin(1.8*i*rads)+32767) << endl;
    }
    outfile.close();
    return 0;
*/
/*
y[t] = AMPLITUDE * sin (2 * M_PI * 0.15 * t + 0) + ZERO_OFFSET;
f = 15 cycles / NUM_POINTS = 0.15 Hz
To have one full-cycle, loop from y[0:t) where t 
is the time or number of points it takes to have a full cycle (i.e. wavelength)*/

vector<float> FFT (vector<float> p) {

    int n = p.size();
    if (n == 1) { // n is a power of 2
        return p;
    }
    //cout << p.size() << ",";
    //for (auto &z:p) {
        //cout << z << ",";
    //}
    // -1 represents i
    std::complex<double> complex(M_PI*2, 1);
    float w = exp(complex.real()/double(n)); // eulers number raised to argument
    
    vector<float> PE; // evens & odds
    vector<float> PO;

    for (int i = 0; i < p.size(); i++) {
        if (int(p[i]) % 2 == 0) {
            PE.push_back(p[i]);
        } else {
            PO.push_back(p[i]);
        }
    }
    if (PE.size() == 0) {
        vector<float> PE = {0};
    }
    if (PO.size() == 0) {
        vector<float> PO = {0};
    }

    vector<float> YE,YO = FFT(PE), FFT(PO);
    
    vector<float> y(n,0);

    for (int j = 0; j < n/2; j++) {
        y[j] = YE[j] + pow(w,j) * YO[j];
        y[j + n/2] = YE[j] - pow(w, j) * YO[j];
    }

    return y;
}

vector<float> get_frequencies(vector<float> vec, int SR){
    vector<float> frequencies = FFT(vec);

    return frequencies;
}

int main() {

    /*vector<int> vec(500, 0);

    int i = 0;
    for (i; i < 100; i+=10) {
        vec[i] = 10;
    }

    for (i; i < 200; i+=20) {
        vec[i] = 10;
    }

    for (i; i < 300; i+=5) {
        vec[i] = 10;
    }

    for (i; i < 400; i+=2) {
        vec[i] = 10;
    }

    for (i; i < 500; i+=7) {
        vec[i] = 10;
    }*/
    vector<float> vec;
    
    int base_freq = 100;

    #define NB_OF_SAMPLES 10
    #define OFFSET        50
    #define AMPLITUDE     5000


    double angle = 0.0;

    for(int i=0; i < NB_OF_SAMPLES; i++)
    {
        angle += (2 * M_PI * base_freq / NB_OF_SAMPLES);
        vec.push_back(AMPLITUDE * sin(angle) + OFFSET);
    }

    //cout << "RAW:\n";
    //for (auto &z:vec) {
        //cout << z << ",";
        //if (i != vec.size()) {
            //cout << ",";
        //}
    //}
    vector<float> frequencies = get_frequencies(vec, NB_OF_SAMPLES);
    //vector<float> frequencies = {1,0,1,0,1,0,1,0,1,0};
    cout << "\nFREQUENCIES:\n";
    for (auto &s:frequencies) {
        cout << s << ",";
        
    }
    return 0;
}

It should be noted that I do not have a background in mathematics, so a step by step explanation would be most helpful.

Assistance would be much appreciated, NoStepOnSnek

  • 1
    I believe that `M_PI` does not require being re-defined. But C++20 added some mathematical constants, including pi. But aside from that, it's actually really easy to see when code fails. Just execute it in a debugger, and then look at the backtrace. That's your starting point, and if you're unable to identify the issue from that, you at least have a starting point for proper debugging. – sweenish Aug 12 '23 at 04:00
  • I'd also reconsider the macro constants for actual constants. – sweenish Aug 12 '23 at 04:01
  • Segmentation fault usually means you are accessing a bad index in some array, like negative index or index which is equal or greater than the size of the array. Try printing the array in the given index before you actually do something with it and you might discover what it is. – Daniel Aug 12 '23 at 04:07
  • Not the cause of the segv, but a bug nonetheless: You are passing vectors by copy. Pass const references instead. – Cris Luengo Aug 12 '23 at 04:43
  • 3
    Obviously the issue is that the FFT code assumes `n` is a power of two, but your example data has `n=10`, which is not a power of two. There are some other issues, like the code under `if (PE.size() == 0)` has no effect (idem for the odd array). – Cris Luengo Aug 12 '23 at 04:49
  • 1
    `if (n == 1) { // n is a power of 2` interesting way of testing a power of two. An unsigned value has a power of two if only one bit of its value is set. Don't you mean : `if (pop_count(n) == 1)` ? See : [std::pop_count](https://en.cppreference.com/w/cpp/numeric/popcount) – Pepijn Kramer Aug 12 '23 at 05:59
  • see [How to compute Discrete Fourier Transform?](https://stackoverflow.com/a/26355569/2521214) for some inspiration in the sublinks there are my C++ implementations you can crosscheck however your version seem too much unoptimized. You know using `push_back(p[i]);` without preallocation slow things down considerably ... – Spektre Aug 12 '23 at 07:49
  • 2
    Also, why does your code produce a real-valued output? The DFT is complex-valued. What you multiply the odd component with should be a complex exponential with norm 1, you use some real value. – Cris Luengo Aug 12 '23 at 14:25

0 Answers0