雨谷の日和

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

行列式計算改良(先頭アドレスのみコピー)ポインタ版

先日書いたように、しばらく行列式計算のアルゴリズムの改良を試みようと思う。
前提条件は以下とする。

  • 誤差を極力避けるため、整数値の加減算と乗算のみを用いる。
  • アルゴリズムの改良度合いの比較のため、データ内容に依存する改良(枝刈りなど)は後回しにする。
  • JavaでもCでも、どちらでも良いが、可能であればいずれでも同じものを作成して比較する。



それではまずは、kp氏から2004-06-24付け「おまけ」で提示されている改良案を、私の環境で実測してみよう。
kp氏の記述には枝刈り処理が含まれているので、とりあえずはそれを取り除いたものを測っておきたい。
以下のようになるだろうか。(1行削るだけ)

#include 
#include 
 
long expand(long **array,int dim) {
  int i,j,l;
  long **subarray;
  long value = 0;
  
  if(dim<2)return **array;
  subarray = malloc( ( dim - 1) * sizeof(long *));
  for(i = 0; i < dim; i++){
    l = 0;
    for(j = 0; j < dim; j++){
      if(i != j){
        subarray[l] = array[j]+1;
        l++;
      }
    }
    if(i%2){
      value += (*array[i]*expand(subarray,dim-1));
    }
    else{
      value -= (*array[i]*expand(subarray,dim-1));
    }
  }
  free(subarray);
  return value;
}
 
int main(void)
{
  int i;
  long value;
  long **p_array;
  
  long array[ ]={
    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, 
  };

  p_array = malloc(sizeof(long*)*11);
  for(i = 0; i < 11; i++){
    p_array[i] = &array[11*i];
  }

  value = expand(p_array,11);

  printf("result:%ld\n",value);

  free(p_array);
  return 0;
}

次回、これを実測した結果を掲載する。