#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <sys/resource.h>
#include <math.h>

#define n (1000)

int a[n][n],b[n][n],c[n][n],d[n][n],e[n][n];

float elapsedCPU()
{
struct rusage rusage;
getrusage(RUSAGE_SELF,&rusage);
return rusage.ru_utime.tv_sec+rusage.ru_utime.tv_usec/1000000.0
  + rusage.ru_stime.tv_sec+rusage.ru_stime.tv_usec/1000000.0;
}

int generateRandom(minRange,maxRange)
int minRange,maxRange;
{
/* returns integer in range minRange <= x <= maxRange*/
return minRange+abs(random()) % (maxRange-minRange+1);
}

void byRows(int a[n][n],int b[n][n],int c[n][n])
// Everyday matrix multiply.
{
int i,j,k;

for (i=0; i<n; i++)
  for (j=0; j<n; j++)
  {
    c[i][j] = 0;
    for (k=0; k<n; k++)
      c[i][j] += a[i][k]*b[k][j];
  }
}

void byColumns1(int a[n][n],int b[n][n],int c[n][n])
// Computes matrix multiply going down columns of output matrix.
{
int i,j,k;

for (j=0; j<n; j++)
  for (i=0; i<n; i++)
  {
    c[i][j] = 0;
    for (k=0; k<n; k++)
      c[i][j] += a[i][k]*b[k][j];
  }
}

void byColumns2(int a[n][n],int b[n][n],int c[n][n])
// Computes matrix multiply going down columns of output matrix.
// Column of second matrix is copied to take advantage of cache.
{
int i,j,k;
int bColumn[n];

for (j=0; j<n; j++)
{
  for (k=0; k<n; k++)
    bColumn[k] = b[k][j];
  for (i=0; i<n; i++)
  {
    c[i][j] = 0;
    for (k=0; k<n; k++)
      c[i][j] += a[i][k]*bColumn[k];
  }
}
}

main()
{
float startCPU,stopCPU;
int i,j;

srandom(666);
for (i=0;i<n;i++)
  for (j=0;j<n;j++)
  {
    a[i][j]=generateRandom(-5,5);
    b[i][j]=generateRandom(-5,5);
  }

startCPU=elapsedCPU();
byRows(a,b,c);
stopCPU=elapsedCPU();
printf("byRows() used %f CPU\n",stopCPU-startCPU);

startCPU=stopCPU;
byColumns1(a,b,d);
stopCPU=elapsedCPU();
printf("byColumns1() used %f CPU\n",stopCPU-startCPU);

startCPU=stopCPU;
byColumns2(a,b,e);
stopCPU=elapsedCPU();
printf("byColumns2() used %f CPU\n",stopCPU-startCPU);

// Check results
for (i=0;i<n;i++)
  for (j=0;j<n;j++)
    if (c[i][j]!=d[i][j] || c[i][j]!=e[i][j])
    {
      printf("Bonk!\n");
      exit(0);
    }
}