そういえば去年の今ごろは行列式の計算のプログラムをちまちまちまちまと作ってみていて、最後の方に「行列式計算の色々なアルゴリズム2」とか言いつつ、そのまま色々と忙しくなってしまって放り出してしまっているわけですが。
ということで、割り算をしない、情報落ちを心配しなくていいそれなりに速いアルゴリズムにもそれなりの需要はあるんじゃないでしょうか。
という部分については色々とその後も考えてみてはいました。
ただ、掃き出し法による行列式計算は、誤差は出るもののかなり高速に計算結果が出てくるので、情報落ちをしないアルゴリズムの高速化をごちゃごちゃ考えてもあまり実りはないなぁという結論に、個人的には落ち着いています。
ところで、掃き出し法の計算は通常、浮動小数点型(doubleとか)で行うんですが、これを分数で行うことも理論上は可能ではあります。
ということで、そういう分数での計算のプログラムをちまちまと作ってみる日記をこれから休み休みやってみようかなぁと思っていたり思っていなかったりで。
今回はC言語との比較とかそういう話ではなくて、Java のプログラムをちまちま作る様を何気につらつら書くということを目的とします。
そんな日記何の役に立つのであろうかとかいう疑問はこの際放置ということで。
まずは、ここに載っているC言語でのプログラムを参考に、double型での掃き出し法による行列式計算のプログラムを書いてみました。
こんな感じ→ソースコード
詳しい解説はまあ、元ネタのサイト方を読んで頂ければ良いとして、これを実際に実行してみると以下のような感じの結果になります。
result: 4.892616779999999E8 Flat profile of 0.09 secs (6 total ticks): main Interpreted + native Method 16.7% 1 + 0 java.lang.String.hashCode 16.7% 1 + 0 Total interpreted Thread-local ticks: 50.0% 3 Class loader 33.3% 2 Compilation Global summary of 0.10 seconds: 100.0% 8 Received ticks 12.5% 1 Compilation 37.5% 3 Class loader
ちなみに同じ環境で、以前のベタなソースコード(をちょっと改変したもの)を実行してみると、こんな感じに。
result: 489261678 Flat profile of 17.55 secs (903 total ticks): main Interpreted + native Method 0.1% 1 + 0 java.lang.String.hashCode 0.1% 1 + 0 Total interpreted Compiled + native Method 99.6% 899 + 0 org.dmwp.math.DeterminantTestExpand.calcExpand 99.6% 899 + 0 Total compiled Thread-local ticks: 0.2% 2 Class loader 0.1% 1 Compilation Flat profile of 0.02 secs (1 total ticks): DestroyJavaVM Thread-local ticks: 100.0% 1 Blocked (of total) Global summary of 17.57 seconds: 100.0% 905 Received ticks 0.1% 1 Compilation 0.2% 2 Class loader
以前より遅くなっているのは、テスト環境が変わっているからで、以下のような構成での実測です。
まあ、要するに掃き出し法とベタな展開とだと、200倍くらいの性能差が出てくるわけでして。
さて、今後は掃き出し法のアルゴリズムを分数を使ったものに書き換えて行くわけですが、しかしまずは分数をどうやって取り扱ったら良いのかという、そこら辺から考えていくことになるんではないかと思っていたりします。
気の長い話になるかも。まあ、休み休み書いていきます。