今回は、主に1変数多項式や多倍長整数の乗算のアルゴリズムとその計算量について説明しました。
内容としては、まず、1変数多項式の乗算のアルゴリズムと演算回数の見積もりを行い、ついで多倍長整数と単精度整数の乗算、そして多倍長整数どうしの乗算のアルゴリズムと計算量の見積もりを行いました。これらの応用により、1変数多項式の乗算についても、係数の大きさ（長さ）から計算量を見積もることができるようになると思いますが、この部分は各自での考察を促したいと思います。
次回は、主に1変数多項式に対する剰余つき除算を説明した後で、テキスト第4章のEuclid互除法に進む予定です。
授業サポートページ：https://www.math.tsukuba.ac.jp/~terui/compmath1-2016
0 件のコメント:
コメントを投稿