前回、行列積の法計算を行った際、いくつかの除算の計算量の評価については持ち越していましたので、今回の授業では、主な除算アルゴリズムの計算量について議論しました。まず、1変数多項式の除算の計算量を見積もり、それから、単精度整数の除算、多倍長整数の除算の計算量を確かめました。そして、中国剰余算法の計算量の見積もりを行いました。
次回からは、1変数多項式や整数の高速乗算法を紹介します。次回はカラツバ (Karatsuba) の乗算アルゴリズムを紹介する予定です。
授業サポートページ： https://www.math.tsukuba.ac.jp/~terui/compmath1-2018
0 件のコメント:
コメントを投稿