# How to increase efficiency of matrix operation in C?

I have a N*N upper triangular matrix with property such that, all its diagonal elements are a1,a2,a3,...,aN. I want that a[i][j] (for all j>i) should be

``````(a[i][j-1] + a[i+1][j]) / 2.
``````

I have many test cases, and I have to apply this property every time to calculate the answer. What is the most optimal way to do this, so that for all test cases the overall running time is less? Test cases: Inputs are N and a1,a2,...,aN.

To calculate the answer, I need to do:

``````a[0][0] + a[0][2] + ... + a[0][n-1] + a[2][n-1] + a[4][n-1] + ... + a[n-1][n-1].
``````

My solution (which keeps getting timed out):

``````#include<stdio.h>
double a[2000][2000];
int main(){
int test;
scanf("%d",&test);
//int arr[2000];
while(test--){
int n,i,j;
//scanf("%d",&n);
scanf("%d",&n);
for(i=0;i<n;i++){
int num;
scanf("%d",&num);
if(n!=1)
a[i][i] = num*0.5;
else
a[i][i] = num;
}
for(j=1;j<n;j++){
int k=j;
for(i=0;i<n-j;i++,k++){
if(i==0 && k==n-1)
a[i][k] = (a[i+1][k]+a[i][k-1]);
else
a[i][k] = (a[i+1][k]+a[i][k-1])*0.5;
}
}
float sum=0.0;
for(i=0;i<n;i+=2){
if( i != n-1 )
sum+=a[0][i]+a[n-1-i][n-1];
else
sum+=a[0][i];
}
printf("%.3f\n",sum);
}
getch();
}
``````

Please provide some hints how to optimize the above code.

-

I suggest dropping the floating point and doing it fixed point. To do this I would make `a[][]` of type `int` or `short` (depending upon the input constraints) and instead of storing values x and x * 0.5, store 2x and x respectively. At the end of the summation you can then divide by 2 to get the true result.

The only issue this raises is that of integer overflow. You don't state any numerical constraints but the fixed size arrays (2000x2000) suggest overflow will not occur with `long long`. Alternatively the summation itself could be floating point while the array values remain integers. I notice that your current summation uses `float` which might well be slower than `double`.

Another minor point where you can improve the speed is in the input loop. You have the conditional

``````if(n!=1)
a[i][i] = num*0.5;
else
a[i][i] = num;
``````

As the loop variable `i` goes from 0 to `n`, if `n` is 1 then the loop only fills a[0][0] and so this conditional can be removed from the loop. But if n is small this will make little difference.

-