雨谷の日和

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

分数での掃き出し法による行列式計算13

ここまでのFraction の実装で、掃き出し法での行列式の計算を行う事は可能なので、実際に実装してみることにします。
double での実装を元に、それをFraction に書き換えてみます。
ソースコード

  public static Fraction calcFraction(
    Fraction[] array, int dim
  ) throws Exception {
    Fraction value = Fraction.ONE;
    for(int i = 0; i < dim; ++i){
      Fraction pivot = array[i * dim + i];
      if(pivot.isZero())return Fraction.ZERO;
      value = value.multiply(pivot);
      for(int j = 0; j < dim; ++j){
        array[i * dim + j] = array[i * dim + j].divide(pivot);
      }
      for(int k = i + 1; k < dim; ++k){
        Fraction erase = array[k * dim + i];
        for(int j = i; j < dim; ++j){
          array[k * dim + j] = array[k * dim + j].subtract(
            erase.multiply(array[i * dim + j])
          );
        }
      }      
    }
    return value;
  }

上記に、以下のような行列式を投入してみます。

 1, 2, 3, 4, 6, 1,
 5, 1, 5, 7, 7, 3,
 7, 6, 4, 8, 4, 6,
 6, 5, 1, 0, 1, 5,
 2, 3, 1, 1, 5, 8,
 3, 1, 0, 3, 2, 9,

実行結果は以下。

result: 3969/1

Flat profile of 0.08 secs (5 total ticks): main

  Interpreted + native   Method
 20.0%     0  +     1    org.dmwp.math.Fraction.add
 20.0%     1  +     0    java.lang.String.hashCode
 40.0%     1  +     1    Total interpreted

  Thread-local ticks:
 40.0%     2             Class loader
 20.0%     1             Compilation


Flat profile of 0.08 secs (1 total ticks): DestroyJavaVM

  Thread-local ticks:
100.0%     1             Blocked (of total)


Global summary of 0.16 seconds:
100.0%     6             Received ticks
 33.3%     2             Class loader

問題無さそうですね……とは言い切れないんですね。実は。
速度比較をするのに、6×6 の行列式では差が出ないのですが、いつも使っていた11×11 の行列式だと、Fraction による計算結果が0になってしまうんです。
多分、計算途中にlong の桁あふれか何かでおかしくなってしまっているんだとは思うのですが……。
とりあえず、桁数の少ない行列式なら問題なく計算できるということで。
なお、このままだと個人的に納得行かないので、long よりも桁の大きな整数の扱えるBigInteger でFraction を実装し直してみようと思っています。