数式処理と多倍長演算

1. 記号計算 (数式処理)

   式の内部表現、多項式演算・補間・GCD・結式、各種因数分解、p-adic、グレブナー基底、書き換えシステム、記号微分・積分・極限・総和、厳密線形代数、代数的数、微分代数、CAD、計算代数幾何、形式的べき級数 (全 27 章)

2. 多倍長整数演算

   整数の表現と基本演算、高速乗算 (Karatsuba / Toom-Cook / NTT) と高速除算 (BZ / Newton)、モジュラー算術 (Montgomery / Barrett / CRT)、GCD、素数判定、因数分解、Block Lanczos、数論関数 (全 13 章)

3. 多倍長浮動小数演算

   浮動小数の表現と演算、平方根と N 次根、高精度初等関数 ($\exp$ / $\log$ / $\sin$ / $\cos$)、数学定数 ($\pi$ / $e$ / $\gamma$)、Binary Splitting と超幾何級数 (全 10 章)

Part I — 記号計算 (全 27 章)

1. 第1章数式処理入門

   数式処理とは何か、CASの歴史 (MACSYMA〜SymPy)、式の木構造表現、正準形と正規形、計算量の考え方

2. 第2章式の内部表現 — 木・DAG・ハッシュコンシング

   式木の詳細実装、n 項演算の平坦化、DAG による共通部分式の共有、ハッシュコンシング、主要 CAS の内部表現比較

3. 第3章多項式の表現

   密表現と疎表現、再帰表現と分配表現、項順序の選択、多変数多項式の構造

4. 第4章多項式の基本演算

   加減乗除、Horner 法による評価、長除法、擬除算、記号微分、Newton 基底・Bernstein 基底

5. 第5章多項式補間

   Lagrange 補間、Newton の分割差分、Neville のアルゴリズム、FFT ベース高速補間、Chinese Remainder 補間

6. 第6章多項式の GCD 計算

   式膨張問題、部分終結式アルゴリズム、モジュラ GCD、疎モジュラ GCD、多変数 GCD

7. 第7章結式と部分終結式

   Sylvester 行列式、共通根の判定、Euclid 互除法と結式、部分終結式 PRS、Collins-Brown-Traub、陰関数消去

8. 第8章有理関数の部分分数分解

   未定係数法、Heaviside カバーアップ、Hermite 簡約、Horowitz のアルゴリズム、記号積分の前処理

9. 第9章因数分解 (有限体上)

   無平方分解、相異次数分解、Cantor-Zassenhaus、Berlekamp、Kaltofen-Shoup

10. 第10章因数分解 (整数・有理数上)

    Hensel 持ち上げ、Zassenhaus、因子結合問題、LLL 格子基底簡約、van Hoeij のアルゴリズム

11. 第11章代数体上の因数分解

    代数体 $\mathbb{Q}(\alpha)$ 上の因数分解、norm の利用、Trager のアルゴリズム、Tschirnhaus 変換

12. 第12章p-adic 計算と Hensel 持ち上げ

    p-adic 数、p-adic 絶対値、Hensel の補題、単一・複数因子持ち上げ、Dixon の p-adic 線形代数

13. 第13章グレブナー基底

    多項式イデアル、S 多項式、Buchberger のアルゴリズム、sugar strategy、F4・F5 アルゴリズム

14. 第14章グレブナー基底の応用

    連立方程式の求解、変数消去、イデアル演算、幾何定理の自動証明、ロボティクス

15. 第15章式の書き換えシステム

    項書き換えシステム、合流性と停止性、Knuth-Bendix 完備化、パターンマッチング、AC マッチング

16. 第16章式の簡約化と正規形

    項書き換え系、三角関数の簡約化、ゼロ判定問題、Richardson の定理

17. 第17章記号微分

    chain rule の形式化、式木の再帰的変換、高階微分、多変数偏微分、Faà di Bruno の公式、自動微分との対比

18. 第18章記号積分

    Liouville の定理、Hermite 簡約、Risch アルゴリズム (対数部・指数部)、heuristic 手法

19. 第19章記号的極限計算

    L'Hôpital 則の限界、Hardy 体、Gruntz アルゴリズム、MrvSet と level、特殊関数への拡張

20. 第20章記号的総和と超幾何級数

    Gosper のアルゴリズム、Zeilberger のアルゴリズム、WZ 理論、ホロノミック系

21. 第21章差分方程式と q-超幾何

    線形差分方程式、Petkovšek アルゴリズム、q-差分、q-超幾何級数、q-版の総和アルゴリズム

22. 第22章厳密線形代数

    Bareiss のアルゴリズム、Hermite 標準形、Smith 標準形、Dixon の p-adic 法、LLL 格子基底簡約

23. 第23章代数的数と体拡大

    最小多項式、根の分離、代数的数の四則演算、代数拡大体、Trager の因数分解、ガロア群

24. 第24章微分代数と ODE の記号解法

    微分体、Picard-Vessiot 理論、微分ガロア群、Kovacic のアルゴリズム、Liouvillian 解

25. 第25章量化子除去と CAD

    Tarski-Seidenberg 定理、Collins の CAD、射影と持ち上げ、partial CAD、QEPCAD と Redlog

26. 第26章計算代数幾何

    イデアルの根基、一次分解、Hilbert 関数、特異点検出、次元の計算

27. 第27章形式的べき級数と D-finite 関数

    打ち切りべき級数の演算、Brent-Kung の合成、微分方程式のべき級数解、D-finite 関数

Part II — 多倍長整数演算 (全 13 章)

1. 第1章多倍長整数入門

   64 bit の壁、多倍長整数が必要な場面、表現の選択肢、メモリ管理、主要ライブラリの概観

2. 第2章多倍長整数の表現

   リム配列、符号絶対値と 2 の補数、エンディアン、SBO、calx の設計選択

3. 第3章多倍長整数の基本演算

   加減乗除のスクールブック実装、キャリー伝播、比較、文字列変換

4. 第4章高速乗算アルゴリズム

   Karatsuba、Toom-Cook 3/4/6/8、NTT、5-smooth NTT、squaring 最適化、閾値の設計

5. 第5章高速除算アルゴリズム

   Knuth Algorithm D、Burnikel-Ziegler、Newton 逆数反復、Exact Division、calx の実装

6. 第6章モジュラー算術

   Barrett 還元、Montgomery 乗算、CRT、高速冪剰余、定時間実装

7. 第7章整数 GCD アルゴリズム

   古典 Euclid、Binary GCD (Stein)、Lehmer、HGCD、Extended GCD、モジュラー逆元

8. 第8章不均衡 Toom-Cook 乗算

   Toom-4,2 / Toom-8、pre-pad + addmul_1、unbalanced な invert_approx への応用

9. 第9章NTT 実装比較

   Prime NTT、Small Prime NTT、Goldilocks NTT、Double FFT、5-smooth NTT、AVX2 バタフライ

10. 第10章素数判定

    Miller-Rabin、Fermat、Baillie-PSW、APRCL、AKS、実用的な組み合わせ戦略

11. 第11章整数因数分解

    試し割り、Pollard rho/Brent、Pollard p-1、Fermat、ECM、SIQS、GNFS

12. 第12章Block Lanczos

    GF(2) 疎行列ソルバ、Coppersmith の Block 化、CSR 形式、GNFS の最終段階

13. 第13章数論関数

    Möbius $\mu$、Euler totient $\phi$、約数関数 $\sigma_k$、Jacobi 記号、Dirichlet 畳み込み、Möbius 反転

Part III — 多倍長浮動小数演算 (全 10 章)

1. 第1章多倍長浮動小数点数入門

   IEEE 754 の限界、誤差解析、条件数、多倍長 Float が必要な場面、主要ライブラリ (MPFR, calx, mpmath)

2. 第2章多倍長浮動小数点数の表現

   仮数・指数・符号、正規化、特殊値 (inf, nan)、effective_bits、丸めモード

3. 第3章多倍長浮動小数点演算

   加減乗除、正しい丸め、Kahan summation、FloatOps 3 引数 API、buffer 再利用

4. 第4章Float 平方根と逆数平方根

   Newton 法による平方根、逆数平方根テーブル、精度倍増、初期近似の構築

5. 第5章高精度初等関数

   $\exp$, $\log$, $\sin$, $\cos$, $\tan$, $\arctan$、引数削減、Taylor 級数、AGM、正しい丸めの保証

6. 第6章数学定数の計算

   $\pi$ (Chudnovsky, Gauss-Legendre, BBP)、$e$、$\gamma$ (Brent-McMillan)、$\ln 2$、Catalan 定数、キャッシュ

7. 第7章Zimmermann 再帰平方根

   sqrtrem の再帰分割統治、dc_sqrtrem、3 層の isSquare フィルター

8. 第8章N 次根の精度倍増 Newton 法

   $x^n = a$ の Newton 反復、精度倍増、収束次数、多倍長での実装

9. 第9章N 次根の初期近似

   double 初期値の精度確保、根抽出の前段階、exponent 正規化

10. 第10章Binary Splitting と超幾何級数

    BS の $O(M(n) \log^2 n)$、Chudnovsky $\pi$、Brent-McMillan $\gamma$、4-way 並列、NTT 連携の限界