// 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 2007

#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.
//