お気楽さんすう屋さんateruiの小技とお知らせのまとめです。
"easy arithmetician" aterui's spot for tips and announcements.
今回は、前回の内容に関連する内容として、除算のアルゴリズムと計算量に関する補足説明を行いました。
前回「行列積の法計算」では、中国剰余算法を用いて整数を成分にもつ行列の乗算の効率化を図る手順を紹介しましたが、その中で、中国剰余算法の計算量に触れました。そこで、今回は、これに関連して、1変数多項式の除算の計算量、多倍長数を単精度数で割る除算のアルゴリズムとその計算量について紹介し、中国剰余算法の計算量の導出を行いました。
以上、春学期の授業を通して、多倍長数や1変数多項式の四則演算のアルゴリズムと計算量や、拡張Euclid互除法のアルゴリズムとその応用を中心に紹介してきました。代数的な計算のアルゴリズムへの理解を深めていただければと思います。
授業サポートページ： https://www.math.tsukuba.ac.jp/~terui/compmath1-2017
今回は、前回に引き続き、数式処理に関連するいくつかのテーマを取り上げました。
まず、ある履修者の人が現在取り組んでいるという、openFrameworksというC++のツールキットについて紹介してもらいました（現在、openFrameworksを使った映像制作を行っているようです）。
次に、学類3年で私の学類の授業を履修している人ですが、Haskellで、多変数多項式の演算と、Groebner (グレブナー)基底を計算するBuchberger（ブッフバーガー）アルゴリズムを実装したというので、紹介してもらいました。
最後に、私の話題で、1階述語論理式の量化子消去 (QE) を用いた大学入試問題の解法について、その概要を紹介しました。
今回は、モジュラー算法 (modular algorithm) の一例として、「行列積の法計算」を紹介しました。
「モジュラー算法」は、ある特徴をもつアルゴリズムの総称ですが、計算途中に多倍長数が現れるアルゴリズムを、いくつかの互いに素な、より小さい数を法とする剰余環上で計算し、最後に中国剰余定理を用いて、整数上の解答の係数を計算するものです。今回は、行列積の計算を例に取り上げ、モジュラー算法によって計算の効率化が図られることを紹介しました。
授業サポートページ： https://www.math.tsukuba.ac.jp/~terui/compmath1-2017
今回は、数式処理に関する種々の話題から、私の専門分野である「数式・数値融合計算」を取り上げ、近似最大公約子 (GCD) のアルゴリズム研究の経過や動向について解説しました。
次回も、数式処理に関する種々の話題から、テーマを取り上げて解説する予定です。
今回は、拡張Euclid互除法の応用の一つとして、有理数の再構成を紹介しました。具体的な応用方法は2種類あり、1つは、有理数演算を剰余環に埋め込んで計算し、計算結果から有理数の計算結果を復元するもの、もう1つは、小数で近似された有理数からもとの有理数の既約分数表現を求めるものです。
授業サポートページ： https://www.math.tsukuba.ac.jp/~terui/compmath1-2017