Imprecise average at run time

Question

I am trying to solve a problem and I've run into a bit of an issue.
I have to find the running average of a series of numbers.
Example:

input 4 2 7 
output 4 3 4.3333

Now here's the problem although I get the answer, it is not the precise answer.

Accepted Output: accuracy difference shown in the image

 290.6666666667
 385.4000000000
 487.8333333333
 477.4285714286
 496.4444444444
 ...
 523.8571166992
 506.0454406738
 495.3043518066

I can't find whats wrong. Some help would be highly appreciated.

#include<stdio.h>

main(){
  int n;
  printf("set:");
  scanf("%d",&n);
  float arr[n+1],resarr[n+1];
  float sum=0;

  for(int i=1; i<=n; i++){
    scanf("%f",&arr[i]);
    sum=arr[i]+sum;

    float res= sum/(float)i;
    resarr[i]=res;
  }
  int i=1;
  while(i<=n) {
    printf("%0.10f\n",resarr[i]);
    i++;
  }

  return 0;
}

You seem to have forgotten that array indexes are *zero based*. I.e. an array of `n` elements, have indexes from `0` to `n - 1` (inclusive). — Some programmer dude, Jan 05 '19 at 08:54
And what have "max running time" (your title) to do with your problem? — Some programmer dude, Jan 05 '19 at 08:55
@Someprogrammerdude im sorry entirely my fault , i mean average at run time — pfn, Jan 05 '19 at 12:12
You do know that `float` have a quite limited precision? What happens if you use `double` instead? Also, please read [Is floating point math broken?](https://stackoverflow.com/questions/588004/is-floating-point-math-broken) — Some programmer dude, Jan 05 '19 at 12:21

score 0 · Answer 1 · answered Jan 05 '19 at 08:55

0

Here

for(int i=1; i<=n; i++){ }

you are trying to access out of bound array elements, this certainly causes undefined behavior as let's assume if n is 5 then you are accessing arr[5] also which doesn't exist.

C doesn't perform array boundary condition check, its programmer responsibility to not to access out of bound elements else it causes UB.

In C array index starts from 0 not from 1. So better start rotating loop from 0 to n. For e.g

for(int i=0; i<n; i++) { 
   scanf("%f",&arr[i]);
   /* some code */
}

answered Jan 05 '19 at 08:55

Achal

11,821
2
15
37

1

i'm using i to divide as well so instead of iterating 0 to n , i changed size of array to n+1 but my accuracy issue is still there – pfn Jan 05 '19 at 12:09
@pfn Well, nothing prevents you from using the more idiomatic range and then calculate the average as `double avg = (double)sum / (i + 1);` – Bob__ Jan 05 '19 at 13:19
"you are trying to access out of bound array elements," --> No. code is not accessing outside the array `arr[i]` as it was defined with `arr[n+1]`. – chux - Reinstate Monica Jan 05 '19 at 14:57
@Bob__ Casting `sum` is insufficient as the running sum saved also needs to be `double sum` to insure precision with `sum=arr[i]+sum;`. – chux - Reinstate Monica Jan 05 '19 at 15:20

chux - Reinstate Monica · Answer 2 · 2019-01-05T15:25:28.120

Code fails to achieve the desired accuracy as it is using float rather than double. @Some programmer dude

Typical float is precise to 1 part in 2²³. For printing to 0.0000000001, better to use double which is typically precise to 1 part in 2⁵³.

#include<stdio.h>

int main(void) {
  //float arr[n + 1], resarr[n + 1];
  //float sum = 0;
  double arr[n + 1], resarr[n + 1];
  double sum = 0;
  ...

    // scanf("%f", &arr[i]);
    scanf("%lf", &arr[i]);

    ...
    // float res = sum / (float) i;
    double res = sum / i;  // cast not needed as `sum` is `double`
  ...
}

Iterating from 1 is not idiomatic in C. More common to iterate starting at 0.

size_t is best for array sizing and indexing. int may be too narrow. Of course with small arrays, it makes scant difference.

#include<stdio.h>

int main(void) {
  printf("set:");
  size_t n;
  scanf("%zu", &n);
  double arr[n], resarr[n];
  double sum = 0;

  for (size_t i = 0; i < n; i++) {
    scanf("%lf", &arr[i]);
    sum = arr[i] + sum;

    double res = sum / (i+1);
    resarr[i] = res;
  }

  for (size_t i = 0; i < n; i++) {
    printf("%0.10f\n", resarr[i]);
  }

  return 0;
}

More robust code would check the input from the user it insure it is valid, allocate rather than use a VLA if n is allowed to be large, flush output before reading, etc.

Note that array arr[] is not needed, just a single double for the input and sum.

Imprecise average at run time

2 Answers2