計算機数学I (2019) 第13回：除算の計算量

前回の授業で、モジュラー算法の計算量を行った際、除算や中国剰余算法の計算はまだ出ていませんでした。そこで今回は、1変数多項式の除算や中国剰余算法の計算量の評価を行いました。

次回から1変数多項式の高速乗算法に関する説明に入ります。次回はカラツバ (Karatsuba) による高速乗算法の紹介を行います。