C++ code that convolves a data file for smoothing random data curves of microcanonical ensemble graphs I am new to this, I have a convolution program that takes in a data file, convolves it and outputs another file. I am attaching the code here.

#include&lt;bits/stdc++.h&gt;
using namespace std

void convolute()
{
    ifstream fin;
    ofstream fout;

    int count = 0;
    double a=0,b=0;

    string input_file_string = "maxclus_500000node_3M_5000ens_666.dat";

    string output_file_string = "1convolute_"+input_file_string;

    fin.open(input_file_string.c_str());

    while(fin) //to know the size of array to initialize
    {
        fin&gt;&gt;a&gt;&gt;b;
        count++;

    }

    fin.close();

    double* c = NULL;
    c = new double[count+1];
    double* d = NULL;
    d = new double[count+1];

    for(int i=0;i&lt;count+1;i++)
    {
        c[i] = 0;
        d[i] = 0;
    }

    fin.open(input_file_string.c_str());

    int n = 1;

    while(fin) //takes in data
    {
        fin&gt;&gt;a&gt;&gt;b;
        c[n] = a;
        d[n] = b;
        n++;
    }

    fin.close();

    double* binom = NULL;
    binom = new double[count];

    double* summ = NULL;
    summ = new double[count+1];

    for(int i=0;i&lt;count+1;i++) summ[i] = 0;

    for(int i=0;i&lt;count;i++) binom[i] = 0;

    //here the main convolution of data takes place
    for(int j=1;j&lt;count;++j) 
    {
        double prob = j*1.0/(count-1);
        binom[j] = 1;

        for(int i=j+1;i&lt;count;++i)
        binom[i] = binom[i-1]*((count-1)-i+1)*1.0/i*prob/(1-prob);

        for(int i=j-1;i&gt;=0;--i)
        binom[i] = binom[i+1]*(i+1)*1.0/((count-1)-i)*(1-prob)/prob;

        double sum = 0;

        for(int i=0;i&lt;count;++i) sum += binom[i];
        for(int i=0;i&lt;count;++i) binom[i] /= sum;

        sum = 0;

        for(int i=1;i&lt;count;++i) sum += d[i]*binom[i];

        summ[j] = sum;

        if(j%1000==0)// just to make the process faster and check progress
        cout&lt;&lt;count-1&lt;&lt;'\t'&lt;&lt;j&lt;&lt;endl;

    }

    cout&lt;&lt;"writing to file "&lt;&lt;endl;

    fout.open(output_file_string.c_str());

    for(int i=1;i&lt;count;i++) fout&lt;&lt;c[i]&lt;&lt;'\t'&lt;&lt;summ[i]&lt;&lt;endl;

    fout.close();

    delete [] c;
    c = NULL;
    delete [] d;
    d = NULL;

    delete [] binom;
    binom = NULL;

    delete [] summ;
    summ = NULL;

}

int main()
{
     convolute();

     return 0;
}


The main convolution takes place inside the 'j' loop, i have marked it inside the code, the data file it handles, the smallest one is with 1499994 points (all 'double' points, 2columns), it takes over 15++ hours to finish the whole program, badly in need of help to optimize it, so that it still does the same thing, but wayyyyyy faster! 
p.s. i am also using gcc optimization flags, -Ofast -march=native -funroll-loops etc but still no improvement.
Algorithm takes \$O(n^2)\$ time

Fundamentally, your algorithm takes \$O(n^2)\$ time because it used two nested loops.  On a large input such as 1.5 million items, you must perform at a minimum somewhere around \$2.25 * 10^{12}\$ operations, which will definitely take some time.

However, there are at least two main ways I can think of to speed up your program:


Use multithreading to take advantage of your computer's multiple cores.  Since your program is just doing a massive computation, you can split the work so that each of N cores does 1/N of the work.  Assuming you had a 4 core computer, you could reasonably expect to get a 4x speedup in your program.  It is beyond the scope of my review to present a multithreaded solution, but you could research how to do this on your own.
You can improve the main loop.  I noticed a few things that you could do to speed up your main loop, which I will present in the following sections.


Remove the division loop

The first thing I noticed is that you have a division loop, but it isn't necessary.  Look here:


    double sum = 0;

    for(int i=0;i&lt;count;++i) sum += binom[i];
    for(int i=0;i&lt;count;++i) binom[i] /= sum;  // &lt;-- This loop

    sum = 0;

    for(int i=1;i&lt;count;++i) sum += d[i]*binom[i];

    summ[j] = sum;



Notice how you compute the sum of the binom array, divide each of the binom[i] entries by the total, and then add up the total of d[i] * binom[i].  Mathematically, if you skipped the division loop and just divided by the total at the end, you would get the same answer.  In other words, you could rewrite the above like this:

    double total = 0;

    for(int i=0;i&lt;count;++i) total += binom[i];

    double sum = 0;

    for(int i=1;i&lt;count;++i) sum += d[i]*binom[i];

    summ[j] = sum / total;


Note that the division loop was the costliest of the three loops, since division is slower than addition and multiplication.

No need for binom array

The next thing you could do is to compute the sum on the fly instead of storing your intermediate results into a binom array.  The binom array isn't really needed except to compute the final sum.  So you could just add to sum as you compute the binom values instead of creating an array and adding up the array at the end.  So I rewrote your main loop to look like this:

    //here the main convolution of data takes place
    for (int j=1;j&lt;count;++j) {
        double prob     = (double) j / (count-1);
        double factor   = 0;
        double binom    = 0;
        double prev     = 0;
        double binomTot = 1;
        double sum      = d[j];

        factor = prob / (1-prob);
        prev   = 1;
        for (int i=j+1;i&lt;count;++i) {
            binom     = prev * ((count-1)-i+1)/i*factor;
            binomTot += binom;
            sum      += d[i] * binom;
            prev      = binom;
        }

        factor = (1-prob)/prob;
        prev   = 1;
        for (int i=j-1;i&gt;=0;--i) {
            binom     = prev * (i+1) / (count-1-i) * factor;
            binomTot += binom;
            sum      += d[i] * binom;
            prev      = binom;
        }

        summ[j] = sum / binomTot;

        if(j%1000==0)// just to make the process faster and check progress
        cout&lt;&lt;count-1&lt;&lt;'\t'&lt;&lt;j&lt;&lt;endl;
    }


With this modified loop, the program ran 2x faster than the original program, on a test case of 20000 random floats.

Cache reused values

Finally, you can speed up your loop even more by caching the values that are reused on each loop.  I noticed that these values:

((count-1)-i+1)/i
(i+1) / (count-1-i)


are used in your inner loops, and they only depend on i and count.  So instead of doing the computation over and over again, we can precompute these values once and then just use the precomputed values in the inner loops.  This avoids costly division operations.

Here is a rewrite using cached values:

double *factor1 = new double[count];
double *factor2 = new double[count];

for (int i=0;i&lt;count;++i) {
    factor1[i] = (double) ((count-1)-i+1) / i;
    factor2[i] = (double) (i+1) / (count-1-i);
}

//here the main convolution of data takes place
for (int j=1;j&lt;count;++j) {
    double prob     = (double) j / (count-1);
    double factor   = 0;
    double binom    = 0;
    double prev     = 0;
    double binomTot = 1;
    double sum      = d[j];

    factor = prob / (1-prob);
    prev   = 1;
    for (int i=j+1;i&lt;count;++i) {
        binom     = prev * factor1[i] * factor;
        binomTot += binom;
        sum      += d[i] * binom;
        prev      = binom;
    }

    factor = (1-prob)/prob;
    prev   = 1;
    for (int i=j-1;i&gt;=0;--i) {
        binom     = prev * factor2[i] * factor;
        binomTot += binom;
        sum      += d[i] * binom;
        prev      = binom;
    }

    summ[j] = sum / binomTot;

    if(j%1000==0)// just to make the process faster and check progress
    cout&lt;&lt;count-1&lt;&lt;'\t'&lt;&lt;j&lt;&lt;endl;
}
delete [] factor1;
delete [] factor2;


This rewrite was about 4x faster than the original version, on a test case of 20000 random floats.  However, on a test case of 100000 random floats, it was 14x faster.  My guess is that the original program scaled badly with larger inputs because of the temporary binom array polluting the cache.  I would advise testing this version for yourself on your own computer with various sized inputs to see how it performs.