// Quick and dirty timings for various implementations of the matrix sum 
// S = A + B.  Based on code given in Considering Recursion by Arch Robison,
// Dr. Dobb's Journal, March 2000.
//
// CS 306, Computer Algorithms II
// Fall 2008

#include "episode-timer.h"


static void 
matrix_sum_loop(
  double s[], double a[], double b[], unsigned, unsigned, unsigned n) {

  for (unsigned r = 0; r < n; r++)
    for (unsigned c = 0; c < n; c++)
      s[r*n + c] = a[r*n + c] + b[r*n + c]
  }


static void col_by_col(
  double [], double [], double [], unsigned, unsigned, unsigned)


static void 
row_by_row(
  double s[], double a[], double b[], unsigned r, unsigned, unsigned n) {

  if (r < n) {
    col_by_col(s, a, b, r, 0, n)
    row_by_row(s, a, b, r + 1, 0, n)
    }
  }


static void 
col_by_col(
  double s[], double a[], double b[], unsigned r, unsigned c, unsigned n) {
  if (c < n) {
    s[r*n + c] = a[r*n +c] + b[r*n +c]
    col_by_col(s, a, b, r, c + 1, n)
    }
  }



static void 
matrix_sum_recursive(
  double s[], double a[], double b[], unsigned r, unsigned c, unsigned n) {
  if (n == 1)
    s[r*n + c] = a[r*n + c] + b[r*n + c]
  else {
    n /= 2
    matrix_sum_recursive(s, a, b, r, c, n)
    matrix_sum_recursive(s, a, b, r + n, c, n)
    matrix_sum_recursive(s, a, b, r, c + n, n)
    matrix_sum_recursive(s, a, b, r + n, c + n, n)
    }    
  }


typedef void (* sumfun)(double [], double [], double [], unsigned, unsigned, unsigned)

static void 
time(sumfun f, unsigned n, unsigned i, const char * const name) {

  double 
    * s = new double[n*n], 
    * a = new double[n*n], 
    * b = new double[n*n]
  episode_timer et

  f(s, a, b, 0, 0, n)

  for (unsigned j = 0; j < i; j++) {
    et.start()
    f(s, a, b, 0, 0, n)
    et.stop()
    }

  printf("%11s %9u usec total, %4.2g sec/sum (%4.2g).\n", 
	 name, et.total(), et.average()/1000000, et.stddev())
  }


int main() {

  unsigned 
    n = 1 << 11,
    i = 10

  time(matrix_sum_loop, n, i, "loop")
  time(row_by_row, n, i, "2 recursive")
  time(matrix_sum_recursive, n, i, "1 recursive")
  }


// $Log: matrix-sums.cc,v $
// Revision 1.1  2007-09-23 15:24:20  rclayton
// Created.
//