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++.

All JavaScript translations were made by Claude (Anthropic) from my original C++ code (with some corrections). The translations keep the structure and names of the C++ code where possible. Each page runs the same checks as the C++ main() to confirm the port behaves the same way.
MCA Chapter 3 & Section 5.9

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
ℚ[x]exact rationalsBigInt

Files

Pageeea/index.html
Translationeea/eea_poly.js
Open EEA & Padé
Cox–Little–O'Shea Ch. 2 · MCA Chapter 21

Grö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
ℚ[x₁,…,xₙ]exact rationalsBigInt

Files

Pagegroebner/index.html
Translationgroebner/buchberger.js
Open Buchberger
MCA Chapter 14

Polynomial 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
Fp[x]randomizedp < 2²⁶

Files

Pagefactorization/factorization.html
Translationinline in the page
Open factorization

About 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.