/*   Turn-in Homework 3 for CSE 141, Winter 2002. */

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#define N 800
#define M 256

int main()
{
  int i, j, trial;
  double a[N+10];
  double **b, sum;
  struct timeval t0, t1, t2;
  long times[5][2];
  void *ptr;
  ptr = NULL;

  for (i=0; i<N+9; i+=2) {a[i] = 1.0; a[i+1] = -1.0; }

  /* Note: we try each experiments several times to see
     how consistent the results are. The minimum time is 
     probably the best to consider. */   

  for (trial=0; trial<5; trial ++){

    gettimeofday(&t0,ptr);
    for (i=0; i<N; i++) {
      a[i] = ((((((a[i+0] + a[i+1]) + a[i+2]) + a[i+3])  
             + a[i+4]) + a[i+5]) + a[i+6]) + a[i+7];
    }
    gettimeofday(&t1,ptr);
    for (i=0; i<N; i++) {
      a[i] = ((a[i+0] + a[i+1]) + (a[i+2] + a[i+3])) 
             + ((a[i+4] + a[i+5]) + (a[i+6] + a[i+7]));
    }
    gettimeofday(&t2,ptr);

    times[trial][0] = (t1.tv_sec-t0.tv_sec)*1000000 + (t1.tv_usec-t0.tv_usec);
    times[trial][1] = (t2.tv_sec-t1.tv_sec)*1000000 + (t2.tv_usec-t1.tv_usec);
  }

  printf ("Times for the first loop: %d, %d, %d, %d, %d microsec\n",
	  times[0][0],times[1][0],times[2][0],times[3][0],times[4][0]);
  printf ("Times for the second loop: %d, %d, %d, %d, %d microsec\n",
	  times[0][1],times[1][1],times[2][1],times[3][1],times[4][1]);

   /* Output something so ambitious compilers won't eliminate code */
   printf(" a[%d] = %.3e\n", N-1, a[N-1]);

   /* Allocte and initialize a large 2-D array */
   b = (double **) malloc((size_t) M*sizeof(double *));
   if (b==NULL) {printf("Malloc failed - try another computer!\n");return(-1);}
   b[0] = (double *) malloc((size_t) M*M*sizeof(double));
   if (b[0]==NULL) {printf("Malloc failed - try reducing M.\n");return(-1);}
   for (i=1; i<M; i++) b[i] = b[i-1]+M;
   for (i=0; i<M; i++) 
     for (j=0; j<M; j++) b[i][j] = 1.0;

   sum = 0;

  for (trial=0; trial<5; trial ++){

    gettimeofday(&t0,ptr);

    for (i=0; i<M; i++)
      for (j=0; j<M; j++)
	sum += b[i][j];

    gettimeofday(&t1,ptr);

    for (j=0; j<M; j++)
      for (i=0; i<M; i++)
	sum += b[i][j];

    gettimeofday(&t2,ptr);

    times[trial][0] = (t1.tv_sec-t0.tv_sec)*1000000 + (t1.tv_usec-t0.tv_usec);
    times[trial][1] = (t2.tv_sec-t1.tv_sec)*1000000 + (t2.tv_usec-t1.tv_usec);
  }

  printf ("Times for the third loop: %d, %d, %d, %d, %d microsec\n",
	  times[0][0],times[1][0],times[2][0],times[3][0],times[4][0]);
  printf ("Times for the fourth loop: %d, %d, %d, %d, %d microsec\n",
	  times[0][1],times[1][1],times[2][1],times[3][1],times[4][1]);

   /* Output something so ambitious compilers won't eliminate code */
   printf(" sum = %.3e\n", sum);

  return(0);
}