fast cumulative sum over array in C

user_9676649 0
Viewed 606

I am trying to write a fast method to calculate the cumulative sum over a one-dimensional array of type double, however my naive implementation is very slow and I'm not sure how I can speed up my method.

My first approach was to create an empty array of same dimensions and populate it with the respective cumulative sums in a for loop.

void cumsum_d(int size, double arr[size]) {
double* out = (double*)malloc(size*sizeof(double));
for (int i = 0; i < size; ++i) {
    double temp = 0;
    for (int j = 0; j < i+1; ++j) {
        temp += arr[j];
    }
    out[i] = temp;
}
for (int i = 0; i < size; ++i) {
    arr[i] = out[i];
}
free(out);}

My second attempt was to modify the array in place using recursion

void cumsum_d2(int size, double arr[size], int ind) {
if (ind == 0) {
    return;
}
double temp = 0;
for (int i = 0; i < ind+1; ++i) {
    temp += arr[i];
}
arr[ind] = temp;
cumsum_d2(size, arr, ind-1);}

For an array of length 1000 this has a runtime of approx. 1ms whereas e.g. the NumPy implementation NumPy.cumsum() only takes around 60μs.

Are there any tips/tricks for how I can speed up my code, or are there any major flaws?

c arrays algorithm
1 Answers

A already said in comments, this would be sufficient :

int main()
{
   double arr[10] =  {1., 2., 3., 4., 5., 6., 7., 8., 9., 10.};
   
   for (char i=1; i<10; i++) {
       arr[i] = arr[i] + arr[i-1]; 
       printf("%f\n", array[i]); 
   }
}
user_21645730
Related