代数的数を作る 多項式の根と因数分解のアルゴリズム

BOOTHで販売中！

代数的数を作る 多項式の根と因数分解のアルゴリズム - だめぽラボ - BOOTH

電子版（PDF）：1000円

概要

代数的数（整数係数多項式の根として表される数）を実装するためのアルゴリズムを解説します。 代数的数を使うと、ルートを含むような数に関して、浮動小数点数の誤差に煩わされることなく正確な演算が行えます。 Haskellによるサンプルコードを掲載しています。

この本は、Web連載していた「週刊 代数的実数を作る」の書籍化です。 本文の加筆修正の他、「付録A ユークリッドの互除法と拡張された互除法」「付録B 部分分数分解」を追加しています。

目次

• 書籍化にあたって ii
• はじめに iii
  1. 0.1 計算機で扱える実数(よもやま話)..................... iii
  2. 0.2 基本的な方針:代数的実数の表し方.................... v
  3. 0.3 実装に使うプログラミング言語 ...................... v
  4. 0.4 必要な知識................................. viii
• 第 I 部 代数的実数とその演算 1
  1. #1 一変数多項式環 3
     1. 1.1 多項式の表し方............................... 3
     2. 1.2 和、差、積、スカラー倍.......................... 6
     3. 1.3 値の計算.................................. 6
     4. 1.4 合成..................................... 7
     5. 1.5 除算..................................... 7
     6. 1.6 最大公約元................................. 8
     7. 1.7 微分..................................... 9
     8. 1.8 無平方成分................................. 9
     9. 1.9 計算例 ................................... 10
  2. #2 実根の数え上げ 13
     1. 2.1 スツルムの定理............................... 13
     2. 2.2 根の限界 .................................. 16
     3. 2.3 実根の数え上げの実装 ........................... 17
     4. 2.4 代数的実数の実装 ............................. 19
     5. 2.5 実行例 ................................... 24
  3. #3 代数的数の演算と終結式 29
     1. 3.1 代数的数の四則演算 ............................ 29
     2. 3.2 シルベスター行列と終結式......................... 30
     3. 3.3 終結式による代数的数の加減乗除 ..................... 34
     4. 3.4 終結式の実装................................ 36
     5. 3.5 代数的数の四則演算の実装にあたっての課題 ............... 37
  4. #4 擬除算と多項式剰余列 39
     1. 4.1 整域係数多項式の終結式の計算 ...................... 39
     2. 4.2 ユークリッドの互除法再論......................... 43
  5. #5 区間演算と計算可能実数 49
     1. 5.1 区間演算 .................................. 49
     2. 5.2 計算可能実数................................ 56
     3. 5.3 代数的実数と計算可能実数......................... 59
  6. #6 代数的数の演算まとめ 61
     1. 6.1 判別式と根の分離 ............................. 61
     2. 6.2 代数的実数の演算の実装.......................... 64
     3. 6.3 遊んでみよう................................ 71
• 第II部 多項式の因数分解 75
  1. #7 整域と整数係数多項式 77
     1. 7.1 可換環 ................................... 77
     2. 7.2 整数係数へ........................ ......... 86
  2. #8 多項式の因数分解 その 1 Kronecker の方法と無平方分解 91
     1. 8.1 Kroneckerの方法 .................... ......... 91
     2. 8.2 無平方分解........................ ......... 97
     3. 8.3 モジュラーな方法へ ............................ 102
  3. #9 有限体 103
     1. 9.1 有限体ことはじめ ............................. 103
     2. 9.2 Haskellにおける有限体の実装....................... 111
  4. #10 多項式の因数分解 その 2 Cantor-Zassenhaus の方法 115
     1. 10.1 Cantor-Zassenhausのアルゴリズム.................... 115
     2. 10.2 次数別因数分解(DDF) .......................... 116
     3. 10.3 等次数因数分解(EDF)........................... 118
     4. 10.4 実装..................................... 121
  5. #11 多項式の因数分解 その 3 Berlekamp の方法 127
     1. 11.1 Berlekampのアルゴリズム ........................ 127
     2. 11.2 計算例 ................................... 129
     3. 11.3 実装..................................... 131
     4. 11.4 実装を使う................................. 134
  6. #12 多項式の因数分解 その 4 整数係数の因数分解と代数的数の最小多項式 137
     1. 12.1 係数の上限................................. 137
     2. 12.2 整数係数の因数分解 (big prime版)................... 140
     3. 12.3 最小多項式の計算 ............................. 150
  7. #13 多項式の因数分解 その 5 Hensel の補題 157
     1. 13.1 Henselの補題 ............................... 158
     2. 13.2 Henselの補題を使った因数分解アルゴリズム............... 164
• 第III部 実閉体と代数閉体 173
  1. #14 代数的実数を係数とする代数方程式 175
     1. 14.1 代数的実数を係数とする代数方程式.................... 175
     2. 14.2 実閉体 ................................... 187
  2. #15 虚根の数え上げ、そして代数閉体へ(前編) 189
     1. 15.1 代数的数の表し方と四則演算 ....................... 189
     2. 15.2 代数的数を係数とする多項式の根 ..................... 192
  3. #16 虚根の数え上げ、そして代数閉体へ(後編) 211
     1. 16.1 虚根の数え上げ:境界上に根がある場合.................. 211
     2. 16.2 実装..................................... 218
     3. 16.3 試す..................................... 232
     4. 16.4 最後に ................................... 234
• 付録 237
  1. 付録A ユークリッドの互除法と拡張された互除法 237
     1. A.1 ユークリッド除算 ............................. 237
     2. A.2 最大公約元(GCD)............................. 237
     3. A.3 ユークリッドの互除法........................... 238
     4. A.4 拡張されたユークリッドの互除法(EEA) ................. 239
     5. A.5 応用:mod 𝑚 での逆元の計算....................... 242
     6. A.6 他の応用.................................. 242
  2. 付録B 部分分数分解 243
     1. B.1 有理関数体................................. 243
     2. B.2 部分分数分解................................ 243
     3. B.3 部分分数分解の原理 ............................ 245
• 参考文献 253

サンプルコード

「はじめに」にも書きましたが、サンプルコードは GitHubのリポジトリー から入手できます。

GitとHaskell Stackを入れた状態で、

$ git clone https://github.com/minoki/algebraic-num-example.git
$ cd algebraic-num-example
$ stack repl

により試せます。

---

「だめぽラボ」のページトップへ