Implementations of some algorithms from Modern Computer Algebra in JavaScript
Interactive versions of C++ implementations of classic computer algebra algorithms, following von zur Gathen & Gerhard, Modern Computer Algebra, and Cox, Little & O'Shea, Ideals, Varieties, and Algorithms. Every page runs entirely in the browser. This is support material for the course Modern Computational Mathematics. I wrote earlier versions of the code in C++.
main() to confirm the port behaves the same way.Extended Euclidean algorithm & Padé approximants
The monic EEA in ℚ[x] computes every remainder ri together with cofactors si, ti with ri = sif + tig. Stopping it early gives rational reconstruction, which yields Padé approximants such as tan x ≈ (x − x3/14 − x5/630)/(1 − 17x2/42).
Algorithms
- Division with remainder
- Monic EEA (Algorithm 3.14)
- Padé approximation via the EEA of xn and f
On the page
- Full EEA table, with resizable columns
- Random f, g and a coefficient-growth chart
- Checks of Bézout identities and Padé conditions
Files
eea/index.htmleea/eea_poly.jsGröbner bases: Buchberger's algorithm
Computes a Gröbner basis of a polynomial ideal in ℚ[x1, …, xn] by reducing S-polynomials until every pair reduces to zero. The basis is then made minimal and reduced, which gives the unique reduced Gröbner basis. In addition to the S-polynomial check, an additional criterion (see Chapter 2 from Cox–Little–O'Shea, paragraph 10: Improvements on Buchberger's algorithm) is used. This can speed up things, but wasn't discussed in class.
Algorithms
- Multivariate division with remainder
- Buchberger's algorithm with product and chain criteria
- Minimal and reduced (auto-reduced) bases
On the page
- Lex and graded-lex monomial orders; polynomial input parser
- Pair log, plus a staircase diagram of the leading-term ideal in 2 variables
- Examples: twisted cubic, Enneper surface, cyclic 4
Files
groebner/index.htmlgroebner/buchberger.jsPolynomial factorization over Fp
Factors a random monic polynomial over a finite field Fp (p an odd prime) into monic irreducibles with multiplicities, then checks that the product of the factors gives back the input.
Algorithms
- Distinct-degree factorization (Algorithm 14.3)
- Equal-degree splitting and factorization (Algorithms 14.8, 14.10)
- Root finding and full factorization (Algorithm 14.13)
On the page
- Choose the seed, the prime p and the polynomial size
- Emulates glibc's
rand(), so a seed gives the same output as the C++ binary - Step-by-step output log and a product check
Files
factorization/factorization.htmlAbout the translations
The C++ code uses GMP (mpq_class) for exact rational arithmetic. In JavaScript, a small
Rational class built on BigInt numerators and denominators takes its place,
so all results are exact. The factorization code works modulo p with ordinary numbers, which is
why p is limited to 226: products then stay below 253.
Besides the line-by-line ports, the pages add input parsing, examples, visualizations and verification. None of that changes the algorithms themselves.