雨谷の日和

過去19年で2,600を超えるアニメの第1話だけは見続けた僕のお勧めアニメがハズレなはずがない

Cの行列式計算(allocaでの実装)

kp氏の指摘では、gccの可変長行列の実装はallocaでの実装に近いはずだというだった。
なのでまずはその検証を行っておこう。
以下のように、mallocでのメモリ確保部分をallocaに変える。この場合、freeでの解放処理は必要ない(allocaの場合、スタック領域にメモリを割り付けるので、スタック解放のタイミングで自動に解放が行われるため)。

#include
#include

long expand(long array[], int dim) {
  int i, j, k, l;
  long value = 0;
  long *subarray;
  if(dim < 2)return array[0];
  subarray = (long *)alloca( (dim - 1) * (dim - 1) * sizeof(long));
  for(i = 0; i < dim; ++i) {
    l = 0;
    for(j = 0; j < dim; ++j){
      if(j != i){
        for(k = 1; k < dim; ++k)subarray[(l * (dim - 1)) + k - 1] = array[(j * dim) + k];
        ++l;
      }
    }
    if(i % 2 == 0){
      value += (array[i * dim] * expand(subarray, (dim - 1)));
    }else{
      value -= (array[i * dim] * expand(subarray, (dim - 1)));
    }
  }
  return value;
}

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;
}

次回はこれの結果を見てみよう。