matrix_div_conquer.cpp

#include <cstdio>
#include <cstdlib>
#include "benchmark_base/matrix_div_conquer.h"

namespace comparison_benchmarks {
namespace base {
namespace matrix_div_conquer {

void multiply_naive(size_t size, blocked_matrix_view &result, blocked_matrix_view &a, blocked_matrix_view &b) {
  for (size_t i = 0; i < size; i++) {
    for (size_t j = 0; j < size; j++) {
      result.at(i, j) = 0;
    }
    for (size_t j = 0; j < size; j++) {
      for (size_t k = 0; k < size; k++) {
        result.at(i, j) += a.at(i, k) * b.at(k, j);
      }
    }
  }
}

void blocked_matrix_view::fill_default_data() {
  for (size_t row = 0; row < size_; row++) {
    for (size_t column = 0; column < size_; column++) {
      at(row, column) = row;
    }
  }
}

std::vector<size_t> blocked_matrix_view::BLOCK_LOOKUPS;
size_t blocked_matrix_view::BLOCK_LOOKUPS_SIZE;

void blocked_matrix_view::fill_block_lookup(size_t size, std::vector<size_t> &BLOCK_LOOKUP) {
  if (size <= 1) {
    BLOCK_LOOKUP[block_lookup_at(0, 0)] = 0;
    return;
  }

  fill_block_lookup(size / 2, BLOCK_LOOKUP);

  size_t elements_per_quarter = (size / 2) * (size / 2);
  for (size_t row = 0; row < size / 2; row++) {
    for (size_t column = 0; column < size / 2; column++) {
      BLOCK_LOOKUP[block_lookup_at(row, size / 2 + column)] =
          BLOCK_LOOKUP[block_lookup_at(row, column)] + elements_per_quarter;
      BLOCK_LOOKUP[block_lookup_at(size / 2 + row, column)] =
          BLOCK_LOOKUP[block_lookup_at(row, column)] + 2 * elements_per_quarter;
      BLOCK_LOOKUP[block_lookup_at(size / 2 + row, size / 2 + column)] =
          BLOCK_LOOKUP[block_lookup_at(row, column)] + 3 * elements_per_quarter;
    }
  }
}

void blocked_matrix_view::init_block_lookup(size_t max_size) {
  if (BLOCK_LOOKUPS.size() < max_size) {
    BLOCK_LOOKUPS = std::vector<size_t>(max_size * max_size);
    BLOCK_LOOKUPS_SIZE = max_size;
    fill_block_lookup(max_size, BLOCK_LOOKUPS);
  }
}

}
}
}