Computer Algebra & Arbitrary-Precision Arithmetic

1. Symbolic Computation (Computer Algebra)

   Internal representation of expressions, polynomial operations/interpolation/GCD/resultants, factorization, p-adic, Gröbner bases, rewriting systems, symbolic differentiation/integration/limits/summation, exact linear algebra, algebraic numbers, differential algebra, CAD, computational algebraic geometry, formal power series (27 chapters)

2. Multiprecision Integer Arithmetic

   Integer representation and basic operations, fast multiplication (Karatsuba / Toom-Cook / NTT) and fast division (BZ / Newton), modular arithmetic (Montgomery / Barrett / CRT), GCD, primality testing, factorization, Block Lanczos, number-theoretic functions (13 chapters)

3. Multiprecision Float Arithmetic

   Float representation and operations, square root and N-th root, high-precision elementary functions ($\exp$ / $\log$ / $\sin$ / $\cos$), mathematical constants ($\pi$ / $e$ / $\gamma$), Binary Splitting and hypergeometric series (10 chapters)

Part I — Symbolic Computation (27 chapters)

1. Chapter 1Introduction to Computer Algebra

   What computer algebra is, history of CAS (MACSYMA to SymPy), tree representation of expressions, canonical vs normal forms, complexity notions

2. Chapter 2Internal Representation — Trees, DAGs, Hash Consing

   Detailed tree implementation, flattening of n-ary operations, DAG sharing of common subexpressions, hash consing, comparison of major CAS representations

3. Chapter 3Polynomial Representation

   Dense vs sparse, recursive vs distributive, choice of term order, structure of multivariate polynomials

4. Chapter 4Basic Polynomial Operations

   Add/sub/mul/div, Horner evaluation, long division, pseudo-division, symbolic differentiation, Newton and Bernstein bases

5. Chapter 5Polynomial Interpolation

   Lagrange interpolation, Newton's divided differences, Neville's algorithm, FFT-based fast interpolation, Chinese Remainder interpolation

6. Chapter 6Polynomial GCD

   Expression swell, subresultant algorithm, modular GCD, sparse modular GCD, multivariate GCD

7. Chapter 7Resultants and Subresultants

   Sylvester determinant, common-root test, Euclidean algorithm and resultants, subresultant PRS, Collins-Brown-Traub, implicit elimination

8. Chapter 8Partial Fraction Decomposition

   Undetermined coefficients, Heaviside cover-up, Hermite reduction, Horowitz's algorithm, preprocessing for symbolic integration

9. Chapter 9Factorization over Finite Fields

   Square-free decomposition, distinct-degree factorization, Cantor-Zassenhaus, Berlekamp, Kaltofen-Shoup

10. Chapter 10Factorization over Integers and Rationals

    Hensel lifting, Zassenhaus, factor combination problem, LLL lattice reduction, van Hoeij's algorithm

11. Chapter 11Factorization over Algebraic Number Fields

    Factorization over $\mathbb{Q}(\alpha)$, use of the norm, Trager's algorithm, Tschirnhaus transformation

12. Chapter 12p-adic Computation and Hensel Lifting

    p-adic numbers, p-adic absolute value, Hensel's lemma, single- and multi-factor lifting, Dixon's p-adic linear algebra

13. Chapter 13Gröbner Bases

    Polynomial ideals, S-polynomials, Buchberger's algorithm, sugar strategy, F4 and F5 algorithms

14. Chapter 14Applications of Gröbner Bases

    Solving systems of equations, variable elimination, ideal operations, automatic proof of geometric theorems, robotics

15. Chapter 15Expression Rewriting Systems

    Term rewriting systems, confluence and termination, Knuth-Bendix completion, pattern matching, AC matching

16. Chapter 16Simplification and Normal Forms

    Term rewriting systems, trigonometric simplification, zero-equivalence problem, Richardson's theorem

17. Chapter 17Symbolic Differentiation

    Formalizing the chain rule, recursive tree transformation, higher-order derivatives, multivariate partial derivatives, Faà di Bruno's formula, comparison with automatic differentiation

18. Chapter 18Symbolic Integration

    Liouville's theorem, Hermite reduction, Risch algorithm (logarithmic and exponential parts), heuristic methods

19. Chapter 19Symbolic Limit Computation

    Limitations of L'Hôpital's rule, Hardy fields, Gruntz algorithm, MrvSet and levels, extension to special functions

20. Chapter 20Symbolic Summation and Hypergeometric Series

    Gosper's algorithm, Zeilberger's algorithm, WZ theory, holonomic systems

21. Chapter 21Difference Equations and q-Hypergeometric

    Linear difference equations, Petkovšek algorithm, q-differences, q-hypergeometric series, q-version of summation algorithms

22. Chapter 22Exact Linear Algebra

    Bareiss's algorithm, Hermite normal form, Smith normal form, Dixon's p-adic method, LLL lattice reduction

23. Chapter 23Algebraic Numbers and Field Extensions

    Minimal polynomial, root separation, arithmetic of algebraic numbers, algebraic extensions, Trager factorization, Galois groups

24. Chapter 24Differential Algebra and Symbolic ODE Solving

    Differential fields, Picard-Vessiot theory, differential Galois groups, Kovacic's algorithm, Liouvillian solutions

25. Chapter 25Quantifier Elimination and CAD

    Tarski-Seidenberg theorem, Collins's CAD, projection and lifting, partial CAD, QEPCAD and Redlog

26. Chapter 26Computational Algebraic Geometry

    Radicals of ideals, primary decomposition, Hilbert function, singularity detection, dimension computation

27. Chapter 27Formal Power Series and D-finite Functions

    Truncated power series arithmetic, Brent-Kung composition, power series solutions of differential equations, D-finite functions

Part II — Multiprecision Integer Arithmetic (13 chapters)

1. Chapter 1Introduction to Multiprecision Integers

   The 64-bit wall, use cases, representation choices, memory management, overview of major libraries

2. Chapter 2Multiprecision Integer Representation

   Limb arrays, sign-magnitude vs two's complement, endianness, SBO, calx design choices

3. Chapter 3Basic Integer Operations

   Schoolbook add/sub/mul/div, carry propagation, comparison, string conversion

4. Chapter 4Fast Multiplication Algorithms

   Karatsuba, Toom-Cook 3/4/6/8, NTT, 5-smooth NTT, squaring optimization, threshold design

5. Chapter 5Fast Division Algorithms

   Knuth's Algorithm D, Burnikel-Ziegler, Newton reciprocal iteration, Exact Division, calx implementation

6. Chapter 6Modular Arithmetic

   Barrett reduction, Montgomery multiplication, CRT, fast modular exponentiation, constant-time implementations

7. Chapter 7Integer GCD Algorithms

   Classical Euclid, Binary GCD (Stein), Lehmer, HGCD, Extended GCD, modular inverse

8. Chapter 8Unbalanced Toom-Cook Multiplication

   Toom-4,2 / Toom-8, pre-pad + addmul_1, application to unbalanced invert_approx

9. Chapter 9NTT Implementation Comparison

   Prime NTT, Small Prime NTT, Goldilocks NTT, Double FFT, 5-smooth NTT, AVX2 butterflies

10. Chapter 10Primality Testing

    Miller-Rabin, Fermat, Baillie-PSW, APRCL, AKS, practical combined strategies

11. Chapter 11Integer Factorization

    Trial division, Pollard rho/Brent, Pollard p-1, Fermat, ECM, SIQS, GNFS

12. Chapter 12Block Lanczos

    GF(2) sparse matrix solver, Coppersmith blocking, CSR format, final stage of GNFS

13. Chapter 13Number-Theoretic Functions

    Möbius $\mu$, Euler totient $\phi$, divisor functions $\sigma_k$, Jacobi symbol, Dirichlet convolution, Möbius inversion

Part III — Multiprecision Float Arithmetic (10 chapters)

1. Chapter 1Introduction to Multiprecision Float

   Limits of IEEE 754, error analysis, condition number, use cases for multiprecision float, major libraries (MPFR, calx, mpmath)

2. Chapter 2Multiprecision Float Representation

   Mantissa, exponent, sign, normalization, special values (inf, nan), effective_bits, rounding modes

3. Chapter 3Multiprecision Float Arithmetic

   Add/sub/mul/div, correct rounding, Kahan summation, three-arg FloatOps API, buffer reuse

4. Chapter 4Float Square Root and Reciprocal Square Root

   Newton's method for square roots, reciprocal square root tables, precision doubling, construction of initial approximations

5. Chapter 5High-Precision Elementary Functions

   $\exp$, $\log$, $\sin$, $\cos$, $\tan$, $\arctan$; argument reduction, Taylor series, AGM, guaranteed correct rounding

6. Chapter 6Computation of Mathematical Constants

   $\pi$ (Chudnovsky, Gauss-Legendre, BBP), $e$, $\gamma$ (Brent-McMillan), $\ln 2$, Catalan's constant, caching

7. Chapter 7Zimmermann's Recursive Square Root

   Recursive divide-and-conquer sqrtrem, dc_sqrtrem, three-layer isSquare filters

8. Chapter 8N-th Root via Precision-Doubling Newton

   Newton iteration for $x^n = a$, precision doubling, order of convergence, multiprecision implementation

9. Chapter 9Initial Approximations for N-th Roots

   Ensuring precision of double-based initial values, pre-stage of root extraction, exponent normalization

10. Chapter 10Binary Splitting and Hypergeometric Series

    $O(M(n) \log^2 n)$ BS, Chudnovsky $\pi$, Brent-McMillan $\gamma$, 4-way parallelism, limitations of NTT integration