今回は、まず、モジュラ算法について紹介しました。これは、多倍長数を用いるアルゴリズムに中国剰余算法を適用することで、計算の効率化を図るものです。今回は、モジュラ算法の例として、行列積の法計算のアルゴリズムを紹介しました。
これまでの授業では、多倍長数や1変数多項式の除算の計算量についてあまり触れてきませんでしたが、次回は、これらの除算の計算量を観察した上で、今回のモジュラ算法の計算量の見積もりについて議論したいと思います。
授業サポートページ: https://www.math.tsukuba.ac.jp/~terui/compmath1-2018
0 件のコメント:
コメントを投稿