今回は、高速乗算法の一つとして、整数や1変数多項式に対するカラツバ(Karatsuba)の高速乗算アルゴリズムを紹介しました。n桁の整数どうしの乗算の計算量は、古典的な方法ですと O(n^2) ですが、Karatsubaのアルゴリズムですと、これが O(n^(log 3)) となります。
次回はこの授業の最終回ですが、高速フーリエ変換 (Fast Fourier Transform, FFT) およびそれを用いた1変数多項式の高速乗算法を紹介します。
追記（2018年8月5日）：動画2個目「Karatsuba乗算の計算量」の説明に修正が生じましたので、動画を改訂しました。
授業サポートページ： https://www.math.tsukuba.ac.jp/~terui/compmath1-2018
0 件のコメント:
コメントを投稿