Ｃでの行列式計算（ループ、動的、malloc/free）

ということで、前回までの展開結果を元に、Ｃのソースを書いてみた。
以下のようになる。

#include
#include

long expand(long arraybase[], int dim){
  int j, k, l, index, d, flg;
  long **array;
  long *return_value;
  int *i;
  long result;

  array = (long **)malloc(dim * sizeof(long *));
  return_value = (long *)malloc(dim * sizeof(long));
  i = (int *)malloc(dim * sizeof(int));
  d = dim;
  flg = 0;

  array[dim - 1] = arraybase;
  for(index = 0; index < dim; index++)return_value[index] = 0;
  for(index = 0; index < dim; index++)i[index] = 0;

  do {
    if(d < 2){
      return_value[d - 1] = array[d - 1][0];
      d++;
      flg = 1;
    }else{
      if(flg == 0){
        if(i[d - 1] == 0){
          array[d - 2] = (long *)malloc( (d - 1) * (d - 1) * sizeof(long) );
          return_value[d - 1] = 0;
        }
        if(i[d - 1] < d){
          l = 0;
          for(j = 0; j < d; ++j){
            if(j != i[d - 1]){
            for(k = 1; k < d; ++k)array[d - 2][(l * (d - 1)) + k - 1] = array[d - 1][(j * d) + k];
              ++l;
            }
          }
          d--;
          i[d - 1] = 0;
        }
      }else{
        if(i[d - 1] < d){
          if(i[d - 1] % 2 == 0){
            return_value[d - 1] += (array[d - 1][i[d - 1] * d] * return_value[d - 2]);
          }else{
            return_value[d - 1] -= (array[d - 1][i[d - 1] * d] * return_value[d - 2]);
          }
          i[d - 1]++;
          flg = 0;
        }
        if(i[d - 1] == d){
          free(array[d - 2]);
          d++;
          flg = 1;
        }
      }
    }
  }while(d <= dim);
  result = return_value[dim - 1];
  free(i);
  free(return_value);
  free(array);
  return result;
}

int main() {
  long value;
  long array[11 * 11] = {
    1, 2, 3, 4, 6, 1, 7, 1, 9, 0, 0, 
    5, 1, 5, 7, 7, 3, 5, 3, 6, 1, 6, 
    7, 6, 4, 8, 4, 6, 1, 7, 1, 4, 8, 
    6, 5, 1, 0, 1, 5, 9, 1, 7, 5, 1, 
    2, 3, 1, 1, 5, 8, 4, 6, 3, 1, 5, 
    3, 1, 0, 3, 2, 9, 4, 8, 0, 3, 1, 
    3, 2, 8, 5, 0, 6, 3, 4, 4, 8, 5, 
    4, 9, 9, 4, 6, 1, 0, 1, 2, 1, 6, 
    9, 7, 6, 1, 6, 4, 5, 2, 9, 4, 4, 
    1, 2, 2, 2, 8, 3, 4, 9, 1, 2, 4, 
    6, 1, 6, 4, 4, 8, 6, 3, 4, 1, 4, 
  };
  value = expand(array, 11);
  printf("result: %d\n", value);
  return 0;
}

基本的にはJavaのそれと同じだが、mallocでのメモリの確保とfreeでのメモリの解放の記述が追加されている。
では、これを実行してみよう。

20:36:48
result: 489261678
20:37:34
result: 489261678
20:38:18

最適化無しで約46秒、最適化（-O3）有りで約44秒という結果となった。
2004.06.02の、以前までの実測のまとめの表を見て頂ければ分かるが、ほとんど速度に改善は無いという結果となった。
むしろ、単純に再帰でない関数に展開した場合の方が（微妙だが）速いようだ。


まあとりあえず、次回は他の場合の測定に進もう。
例によって、理由を考えるのは後からでも構わないと思う。