お気楽さんすう屋さんateruiの小技とお知らせのまとめです。
"easy arithmetician" aterui's spot for tips and announcements.
今回は、授業の最終回でしたが、中国剰余定理を紹介し、ついで、定理に現われる連立線形合同式の解を拡張Eucild互除法を用いて解く解法について説明しました。
これで一連の講義が終わりましたが、今年は、講義を初めて担当したこともあり、講義内容にやや偏りが生じたのは反省点だったと思います。多倍長数の演算に時間をかけ過ぎてしまい、他のトピックに割り当てる時間が足りなくなりました。もし次回担当する機会がありましたら、多倍長数の演算の時間を短縮し、数論に関する話題を追加してみたいと思います（その際、多倍長数に関するより詳しい解説を聞きたい場合は、今年の講義の録画が役に立つことでしょう）。
反省点はありますが、今回の講義で、現実に計算を行うための数学の知識や方法論に対する理解が深まれば幸いです。また、皆さんの中には、中学校や高校で教職に就く人もいるかもしれませんが、これから数学を学ぶ生徒さん達にも、折に触れて、こういった、数学の一つの姿を伝えていってもらえればと思います。
授業サポートページ：https://www.math.tsukuba.ac.jp/~terui/compmath1-2015
今回は、拡張Euclid互除法の応用の一つとして「法逆元計算」を取り上げました。これは、剰余環のある元が単元である（＝乗法の逆元をもつ）際に、その逆元を計算する方法で、拡張Euclid互除法で計算する余因子が求める逆元となります。今回は、その性質を述べた定理と、計算例として、素数を法とする整数の剰余環（体）、および、有理数体に既約な1変数代数方程式の根を添加した拡大体において、逆元の計算を行いました。
この授業も次回が最終回ですが、次回は中国剰余定理と、拡張Euclid互除法を用いた中国剰余算法を取り上げ、授業の締めくくりにしたいと思います。
授業サポートページ：https://www.math.tsukuba.ac.jp/~terui/compmath1-2015
今回は、前回のEuclid互除法で残ったアルゴリズム自体の説明を行ってから、拡張Euclid互除法の説明を行いました。拡張Euclid互除法の根拠となる定理の証明は、時間の都合で、最も重要な「余因子の存在と計算手順」の部分のみを行いましたが、それ以外の証明も、一通り、講義ノートに記録しています。
この授業も残すところあとわずかですが、残りの時間は、（拡張）Euclidの互除法に関連する話題に充てる予定です。今回は、連分数展開の計算について説明しました。正則連分数の計算の際、Euclidの互除法が用いられます。これに関連し、ある条件を満たす無理数が、循環する連分数に展開されることも説明し、その計算も行いました。実は、連分数展開からもとの有理数や無理数を計算するのも（拡張）Euclidの互除法と関連性がありますが、こちらの方は時間の都合で割愛しました。
次回以降は、法逆元の計算と、これに関連して、中国剰余定理を（時間があれば）扱う予定です。
授業サポートページ：https://www.math.tsukuba.ac.jp/~terui/compmath1-2015
今回は、整数と1変数多項式の剰余つき除算について説明したのち、Euclidの互除法に入りました。その前に、可換環のイデアルや剰余環などの概念については、各自の復習に任せました（講義テキストにも一通り説明があります）。
Euclid互除法では、その根拠となる定理を説明したところで時間になりましたが、整数に対するEuclid互除法の場合、剰余を計算する回数の上界の一つとして黄金比が用いられることを紹介しました。
次回は「拡張Euclid互除法」について説明した後、Euclidの互除法の応用に進みます。
授業サポートページ：https://www.math.tsukuba.ac.jp/~terui/compmath1-2015
出張で1週間空けましたが、今回は、主に多倍長整数と1変数多項式に対する乗算のアルゴリズムについて説明しました。
多倍長整数の乗算については、単精度演算を単位とした計算量の見積もりを行いましたが、多項式の乗算については、見積もりが繁雑になるため、今回は、係数上の四則演算の回数を単位とした計算量の見積もりのみを行いました。
この時間の最後に、剰余つき除算の説明に入りました。次回は剰余つき除算を説明し、拡張ユークリッドの互除法に進む予定です。
授業サポートページ：https://www.math.tsukuba.ac.jp/~terui/compmath1-2015
今回は、1変数多項式に対するHorner法の応用の一つとして、数の2進・10進変換の効率的な方法を紹介しました。2進・10進変換は、2進数を10進数に、あるいは10進数を2進数に変換する計算です。
非負整数の2進・10進変換は、比較的多くの資料が出回っていると思いますが、循環小数（2進）や有理数（10進）の2進・10進変換、そして、負の10進数を2の補数で表す変換については、原理は他の変換と同様、それ程難しくはありませんが、計算例はさほど多くなさそうですので、参考になるかもしれません。
来週は私の出張のため休講にするので、レポート課題を出しました。課題は授業テキストの演習問題の抜粋ですが、例題を用いて基本的な解法を説明しました。
次回は再来週、1変数多項式や多倍長整数の乗算と除算を扱う予定です。
授業サポートページ：https://www.math.tsukuba.ac.jp/~terui/compmath1-2015
今回は、まず、前回に引き続き、1変数多項式の加算を取り上げ、そのアルゴリズムと計算量の見積もりについて説明しました。
次に、1変数多項式の評価を行う「ホーナー (Horner) 法」について説明しました。これは、高校の数学でも「組立除法」として紹介されている方法で、国立国会図書館の電子展示会「江戸の数学」でも紹介されています。
次回は、Horner法の応用例として、10進数と2進数の間の効率的な変換法を紹介します。
授業サポートページ：https://www.math.tsukuba.ac.jp/~terui/compmath1-2015
今回の授業では、まず、アルゴリズムの計算量を見積もる上で必要な「漸近表示」の説明を行い、次に、それを用いて、多倍長整数の加算の計算量を見積もりました。
それから、「2の補数」を用いた、符号つきの多倍長整数の表現について触れた後（減算のアルゴリズムは演習問題）、1変数多項式の話題に入り、多項式の術語と、1変数多項式の表現について説明しました。
次回は1変数多項式の加算から説明する予定です。
授業サポートページ：https://www.math.tsukuba.ac.jp/~terui/compmath1-2015
今回の授業では、多倍長整数の加算のアルゴリズムについて説明しました。そのため、アルゴリズムの基本的な特徴（要件）についても解説しました。（今回述べた「アルゴリズムの特徴」は、D. Knuth, The Art of Computer Programming, Section 1.1によります。）
次回は、多倍長整数の加算のアルゴリズムの計算量を調べますが、そのために、アルゴリズムの計算量を見積もるための漸近表示の説明から始める予定です。
授業サポートページ：https://www.math.tsukuba.ac.jp/~terui/compmath1-2015
今回の授業では、まず、前回の続きで、浮動小数演算における誤差として「桁落ち誤差」と「情報落ち」について説明し、引き続き、多倍長整数の構成について説明しました。
次回は、多倍長整数の加算について説明します。
授業サポートページ：https://www.math.tsukuba.ac.jp/~terui/compmath1-2015
今回の授業では、浮動小数の導入と一般的な定義を行った後、現在よく使われている浮動小数点の規格の一つとして、IEEE 754 浮動小数点規格のうち、単精度の浮動小数点規格を紹介しました。
IEEE 754 単精度浮動小数点規格の説明の中で、∞（無限大）とNaN（非数）を表現する際の指数部の値としてE=127と説明しましたが、授業後に指摘を受けて確認したところ、これは誤りで、正しくはE=128でしたので訂正します。ご指摘に感謝します。
授業では、時間の都合でIEEE 754は単精度の規格のみ紹介しましたが、講義ノートには倍精度の規格についても記載しましたので、興味のある人はご参照ください。
引き続いて、浮動小数演算における誤差の説明に入りましたが、「丸め誤差」の説明の後「桁落ち誤差」の説明の途中で時間になりました。次回は「桁落ち誤差」の説明から始め、多精度（多倍長）整数の表記と加算の説明に進みたいと思います。
授業サポートページ：https://www.math.tsukuba.ac.jp/~terui/compmath1-2015
今回は、前回に引き続き、コンピュータの基本構成の残りの部分を説明し、その後、整数の表現として、符号なし整数と、2の補数を用いた符号つき整数について説明しました。
コンピュータの基本構成では、前回の「メモリ」の説明に続き、「ワード」の概念とCPUの「レジスタ」を説明し、「ワード」のモデルとして、2進数の「そろばん」の例を挙げました。2進数のそろばんは、もちろん実物は持っていませんが、ワードを単位として計算を扱う際に、今後も例として使おうかと思います。
整数の表現に引き続いて、浮動小数点数の説明に入ったところで、今回は時間切れとなりました。次回は浮動小数点数について説明する予定です。
授業サポートページ：https://www.math.tsukuba.ac.jp/~terui/compmath1-2015
今年度は、数学類専門科目（標準履修年次：3年次）の「計算機数学I」を初めて担当することになりました。
この授業では、主に代数計算、特にEuclidの互除法を軸にしながら、構成的な計算について説明します。授業では、アルゴリズム、データの表現、計算量の議論もしながら進めていきます。
今回は、授業のガイダンスの後、準備として、コンピュータの基本構成を説明しました。その際、実際にタワー型パソコンのケースを開けて、中の構成部品を拡大投映しながら説明しました。今回の授業の履修者は約50人ですが、この時に尋ねたところ、パソコンのケースを開けたことがある人が10人前後、実際に内部の部品を交換したことのある人が2, 3人でした。また、ノートパソコンの部品を交換したことがある人も2, 3人でした。
実際にパソコンの内部がどのように見えるかを知っている人は全員というわけではなかったようですので、授業で出てくる内容を、実際に自分が使うようなパソコンの内部部品と対応づけるという意味では意義があるのでないかと思います。
今年も、毎回の講義の講義ノートをwebの授業サポートページに掲載するとともに、講義の模様を録画して公開していきます。次回は、コンピュータの基本構成の続きから、数値の表現に入っていきたいと思います。
授業サポートページ：https://www.math.tsukuba.ac.jp/~terui/compmath1-2015