お気楽さんすう屋さんateruiの小技とお知らせのまとめです。
"easy arithmetician" aterui's spot for tips and announcements.
今回は、本授業科目の最後の授業でしたが、1変数多項式の高速乗算アルゴリズムの一つとして、高速フーリエ変換 (FFT) を用いた乗算法を紹介しました。2つのn次の1変数多項式の乗算にかかる計算量は、古典的なアルゴリズムで O(n^2), 前回紹介したKaratsubaのアルゴリズムでは O(n^(log 3)) ですが、今回のFFTを用いたアルゴリズムでは O(n log n) となります。
以上が本授業の内容で、この授業では、拡張Euclid互除法を軸に、主に代数的なアルゴリズムを紹介しました。この授業科目は、本学で数学の教員免許を取得するための必修科目にも位置付けられていますが、この授業が、数学の代数分野における構成的な計算を学んだり考えたりするきっかけの一つになればと思います。
授業サポートページ： https://www.math.tsukuba.ac.jp/~terui/compmath1-2018
今回は、高速乗算法の一つとして、整数や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
前回、行列積の法計算を行った際、いくつかの除算の計算量の評価については持ち越していましたので、今回の授業では、主な除算アルゴリズムの計算量について議論しました。まず、1変数多項式の除算の計算量を見積もり、それから、単精度整数の除算、多倍長整数の除算の計算量を確かめました。そして、中国剰余算法の計算量の見積もりを行いました。
次回からは、1変数多項式や整数の高速乗算法を紹介します。次回はカラツバ (Karatsuba) の乗算アルゴリズムを紹介する予定です。
授業サポートページ： https://www.math.tsukuba.ac.jp/~terui/compmath1-2018
今回は、まず、モジュラ算法について紹介しました。これは、多倍長数を用いるアルゴリズムに中国剰余算法を適用することで、計算の効率化を図るものです。今回は、モジュラ算法の例として、行列積の法計算のアルゴリズムを紹介しました。
これまでの授業では、多倍長数や1変数多項式の除算の計算量についてあまり触れてきませんでしたが、次回は、これらの除算の計算量を観察した上で、今回のモジュラ算法の計算量の見積もりについて議論したいと思います。
授業サポートページ： https://www.math.tsukuba.ac.jp/~terui/compmath1-2018
今回は、前回証明した「部分終結式の基本定理」を用いて、多項式剰余列における係数膨張を防ぐアルゴリズムとして、「縮小多項式剰余列 (PRS)アルゴリズム」および「部分終結式PRSアルゴリズム」を紹介しました。
今回は、拡張Euclid互除法を用いて、有理数を再構成する計算について説明しました。1つは、剰余環に有理数の演算を埋め込み、計算結果から有理数を再構成するもの、もう1つは、有理数の（10進）循環小数による近似値から、既約な有理数を復元するものです。
次回は、剰余環上の計算と中国剰余定理を組み合わせた「モジュラ算法」について説明します。
授業サポートページ： https://www.math.tsukuba.ac.jp/~terui/compmath1-2018