Polynomial.js

Polynomial.js is a TypeScript library for parsing and computing univariate polynomials. It supports real, rational, complex, quaternion, modular, and custom coefficient fields.

The library provides immutable arithmetic operations, derivatives, integrals, Euclidean division, greatest common divisors, reciprocal polynomials, and Horner evaluation. It does not calculate roots, but it can construct a polynomial from known roots.

Installation

npm install polynomial

Polynomial.js requires Node.js 20 or newer when used in Node.js.

Quick Start

import Polynomial from 'polynomial';

Polynomial.setField('R');

const polynomial = Polynomial.fromRoots([1, 2, 3]);

console.log(polynomial.toString());          // x^3-6x^2+11x-6
console.log(polynomial.eval(2));             // 0
console.log(polynomial.derive().toString()); // 3x^2-12x+11

Every polynomial is an instance of the Polynomial class and must be constructed with new. Arithmetic methods return new instances and do not mutate the receiver.

const left = new Polynomial('3x^2');
const sum = left.add('-x^2');

console.log(left.toString()); // 3x^2
console.log(sum.toString());  // 2x^2

CommonJS is supported as well:

const Polynomial = require('polynomial');

Inputs

The constructor and arithmetic methods accept polynomial strings, numbers, coefficient arrays, coefficient maps, and other Polynomial instances.

new Polynomial('23x^4+98x^2+4');
new Polynomial(55);
new Polynomial([1, 2, 3]);       // 3x^2+2x+1
new Polynomial({ 3: 4, 5: 9 });  // 9x^5+4x^3

String exponents must be non-negative integers. Whitespace is ignored. Coefficients may contain multiplication and division, while nested polynomial expressions and parentheses are not parsed.

new Polynomial('2 * 3x^2 + 4/5x - 1');

The selected field parses each coefficient, enabling field-specific forms such as fractions, repeating decimals, and complex numbers.

Polynomial.setField('Q');
console.log(new Polynomial('5/3x^3+4/3x').toString());

Polynomial.setField('C');
console.log(new Polynomial('23ix^4+98x^2+i').toString());

Coefficient Fields

The built-in fields are:

Name	Coefficients	Implementation
`R`	Real numbers	JavaScript numbers
`Q`	Rational numbers	Fraction.js
`C`	Complex numbers	Complex.js
`H`	Quaternions	Quaternion.js
`Zp`	Integers modulo `p`	Built in, for example `Z7`

Polynomial.setField() selects the default field for future instances. Each instance captures that field when it is constructed, so changing the default does not alter existing polynomials or their subsequent operations.

Polynomial.setField('Q');
const rational = new Polynomial('1/3x');

Polynomial.setField('R');
console.log(rational.add('1/3x').toString()); // 0.(6)x

Division in Zp requires the divisor to have a multiplicative inverse. Use a prime modulus when all non-zero coefficients must be invertible.

Custom Fields

A custom field can be installed as the default with setField() or passed directly to the constructor. Passing it to the constructor avoids shared configuration and keeps the field local to that polynomial and all results derived from it.

import Polynomial, { type PolynomialField } from 'polynomial';

const field: PolynomialField<number> = {
  add: (left, right) => left + Number(right),
  sub: (left, right) => left - Number(right),
  mul: (left, right) => left * Number(right),
  div: (left, right) => left / Number(right),
  parse: value => Number(value),
  empty: value => value === undefined || value === 0,
  pow: (base, exponent) => base ** exponent,
  equals: (left, right) => left === Number(right),
  characteristic: 0,
  magnitude: value => Math.abs(value),
  sqrt: value => value < 0 ? null : Math.sqrt(value),
};

const polynomial = new Polynomial('x^2+2x+1', field);

API

Construction and Configuration

new Polynomial(input?, field?) creates a polynomial.
Polynomial.fromRoots(roots, field?) creates a monic polynomial with the given roots.
Polynomial.quotient(modulus, field?) creates the quotient ring defined by a non-constant modulus polynomial.
Polynomial.enumerate(maxDegree, maxElements?) or Polynomial.enumerate(maxDegree, field, maxElements?) enumerates polynomials over a finite prime field.
Polynomial.cyclicCodeGenerators(length, dimension, maxGenerators?) or Polynomial.cyclicCodeGenerators(length, dimension, field, maxGenerators?) finds all generator polynomials for a cyclic code.
Polynomial.setField(field) selects R, Q, C, H, Zp, or a custom field as the default for future instances.

Arithmetic

add(value) returns the sum.
sub(value) returns the difference.
mul(value) returns the product.
addmul(left, right) adds the product of two values.
div(value) returns the quotient of polynomial long division.
mod(value) returns the remainder of polynomial long division.
gcd(value) returns the monic greatest common divisor.
lcm(value) returns the monic least common multiple.
isDivisibleBy(value) reports whether polynomial division has zero remainder.
factor() returns the leading unit followed by monic irreducible factors with multiplicity.
isIrreducible() reports whether a positive-degree polynomial is irreducible.
cyclicCodeBasis(length) returns the shifted basis generated by a divisor of $x^n-1$.
compare(value) compares finite-field polynomials in coefficient order.
successor() returns the next polynomial in that order.
pow(exponent) raises the polynomial to a non-negative integer power.
neg() negates every coefficient.
reciprocal() reverses the coefficient order relative to the degree.
monic() divides every coefficient by the leading coefficient.
dispersion(maxShift?) returns the greatest non-negative integer k for which gcd(p(x), p(x+k)) is non-constant.
sqrt() returns a polynomial g satisfying g² = p, or null when no polynomial square root exists.

For R, Q, and C, dispersion() derives a finite search bound from the coefficients. A custom field can provide magnitude() and an optional characteristic to enable the same behavior. Otherwise, pass an explicit non-negative maxShift. Non-constant polynomials over a field with positive characteristic have infinite dispersion because shifts by multiples of the characteristic leave the polynomial unchanged.

Polynomial.setField('Q');

const polynomial = new Polynomial('x^3-7x^2+10x'); // roots: 0, 2, 5
console.log(polynomial.dispersion());               // 5
console.log(polynomial.dispersion(4));              // 3

sqrt() uses the root with the principal leading coefficient. Its negation is the second square root. Exact roots are supported over Q and prime fields, while R also permits irrational coefficients and C uses the principal complex coefficient root. Custom fields must provide sqrt(value). Quaternion coefficients are not supported because the coefficient recurrence assumes commutative multiplication.

const square = new Polynomial('9x^4+6x^3-11x^2-4x+4');
const root = square.sqrt();

console.log(root?.toString());           // 3x^2+x-2
console.log(root?.mul(root).toString()); // 9x^4+6x^3-11x^2-4x+4

Calculus and Evaluation

derive(order = 1) returns the requested derivative.
integrate(order = 1) returns the requested antiderivative with zero integration constants.
eval(value) evaluates the polynomial using Horner's method.
compose(value) substitutes a polynomial for the indeterminate using Horner's method.
result(value) is a deprecated alias for eval(value).

const polynomial = new Polynomial('2x^3-3x+5');
console.log(polynomial.compose('x^2+1').toString()); // 2x^6+6x^4+3x^2+4

Quotient Rings

Polynomial.quotient(modulus, field?) constructs $K[x]/(m)$. Every element is reduced to its canonical representative of degree less than modulus.degree(). A ring created from an existing polynomial retains that polynomial's coefficient field.

Polynomial.setField('Z2');

const ring = Polynomial.quotient('x^3+x+1');
const alpha = ring.create('x');

console.log(alpha.pow(3).toString());    // x+1
console.log(alpha.pow(7).toString());    // 1
console.log(alpha.inverse().toString()); // x^2+1

The ring provides create(value), zero(), one(), and its monic modulus. evaluate(polynomial, value) evaluates a polynomial at a residue class using Horner's method, while isRoot(polynomial, value) tests whether that value is a root. Residue classes provide add, sub, mul, div, neg, pow, inverse, equals, and isZero. Division and inversion throw RangeError when the divisor is not a unit. Residues from different quotient-ring instances cannot be combined.

Polynomial.setField('Z2');

const ring = Polynomial.quotient('x^3+x+1');
const alpha = ring.create('x');

console.log(ring.evaluate('x^2+x+1', alpha).toString()); // x^2+x+1
console.log(ring.isRoot('x^3+x+1', alpha));              // true

Unlike Polynomial.eval(), which returns a coefficient-field value, ring.evaluate() returns a residue class. Evaluation is defined for every quotient ring and does not require the modulus to be irreducible. Values already belonging to another quotient-ring instance are rejected.

When the coefficient field is Zp and the modulus is irreducible, the quotient is the finite field $\text{GF}(p^n)$. isField() checks this condition, and order() returns $p^n$. The ring can enumerate its elements(), primitiveElements(), and primitivePolynomials(). A residue class provides additiveOrder(), additiveSubgroup(), multiplicativeOrder(), multiplicativeSubgroup(), isPrimitive(), and minimalPolynomial().

Polynomial.setField('Z2');

const field = Polynomial.quotient('x^4+x+1');
const alpha = field.create('x');
const beta = alpha.pow(5);

console.log(field.order());                        // 16
console.log(alpha.multiplicativeOrder());          // 15
console.log(alpha.isPrimitive());                  // true
console.log(beta.multiplicativeSubgroup().map(String));
// ['1', 'x^2+x', 'x^2+x+1']
console.log(beta.minimalPolynomial().toString()); // x^2+x+1
console.log(field.primitivePolynomials().map(String));
// ['x^4+x+1', 'x^4+x^3+1']

primitivePolynomials() returns the distinct minimal polynomials of the primitive elements, ordered by finite-field coefficient order. Frobenius conjugates are deduplicated, so each primitive polynomial occurs exactly once.

The subgroup methods list the identity first, followed by successive multiples or powers of the residue. Their optional limit defaults to one million elements. elements(maxElements?), primitiveElements(maxElements?), and primitivePolynomials(maxElements?) use the same default and throw RangeError before enumeration if the field is larger. Multiplicative operations and minimal polynomials require an irreducible modulus; ordinary quotient-ring arithmetic does not.

Finite-Field Factorization

factor() and isIrreducible() operate over prime coefficient fields Zp. Factorization uses square-free decomposition, Frobenius roots for inseparable polynomials, and Berlekamp's algorithm. Repeated factors occur repeatedly in the returned array.

Polynomial.setField('Z2');

const polynomial = new Polynomial('x^5+x^2+x+1');
console.log(polynomial.factor().map(String));
// ['x+1', 'x+1', 'x^3+x+1']

For a non-monic polynomial, the leading unit is the first factor, so multiplying all returned factors reconstructs the input. The factorization of 1 is empty, while factoring the zero polynomial throws RangeError. Fields of characteristic zero and composite modular rings are rejected.

Cyclic Codes

If $g$ divides $x^n-1$ over a prime field, g.cyclicCodeBasis(n) returns the standard basis $g,xg,\ldots,x^{k-1}g$, where $k=n-\deg g$.

Polynomial.setField('Z2');

const generator = new Polynomial('x^4+x^3+x^2+1');
console.log(generator.cyclicCodeBasis(7).map(String));
// ['x^4+x^3+x^2+1', 'x^5+x^4+x^3+x', 'x^6+x^5+x^4+x^2']

The generator is normalized to monic form. Invalid lengths, the zero polynomial, and generators that do not divide $x^n-1$ are rejected.

Polynomial.cyclicCodeGenerators(n, k) returns every monic divisor of $x^n-1$ having degree $n-k$. Each result therefore generates a cyclic $[n,k]$ code and can be passed to cyclicCodeBasis(n).

Polynomial.setField('Z2');

const generators = Polynomial.cyclicCodeGenerators(7, 4);
console.log(generators.map(String));
// ['x^3+x^2+1', 'x^3+x+1']

console.log(generators[0].cyclicCodeBasis(7).length); // 4

Repeated irreducible factors are retained when the characteristic divides the code length. Dimensions from zero through $n$ are accepted: $k=0$ returns $x^n-1$, while $k=n$ returns $1$. An empty array means that no divisor has the required degree. The optional result limit defaults to one million generators.

Finite-Field Enumeration

compare() and successor() use base-$p$ coefficient order with the constant coefficient as the least significant digit. Polynomial.enumerate(d) returns all $p^{d+1}$ polynomials of degree at most $d$ in that order.

Polynomial.setField('Z2');

console.log(Polynomial.enumerate(1).map(String));
// ['0', '1', 'x', 'x+1']

console.log(new Polynomial('x+1').successor().toString()); // x^2

Enumeration defaults to at most one million results. Pass the limit as the second argument when using the active field, or as the third argument when providing a custom field.

Inspection and Formatting

degree() returns the polynomial degree, or -Infinity for the zero polynomial.
lc() returns the leading coefficient, or undefined for the zero polynomial.
lm() returns the leading monomial.
equals(value) compares normalized coefficients in the current field.
isZero() reports whether the polynomial is zero.
isMonic() reports whether the leading coefficient is one.
toArray(width?) returns coefficients in ascending exponent order, optionally padded with zeros.
clone() returns an independent polynomial with the same coefficients and field.
toString() returns the plain-text representation.
toLatex() returns a LaTeX representation.
toHorner() returns a Horner-scheme representation.
coeff exposes the coefficient map indexed by exponent.

const polynomial = new Polynomial('23x^4+98x^2+4');

console.log(polynomial.coeff[4]); // 23
console.log(polynomial.degree()); // 4
console.log(polynomial.toArray()); // [4, 0, 98, 0, 23]

Division Trace

Set Polynomial.trace to true before division to retain the subtracted terms and final remainder. The property is replaced with an array of polynomial instances.

Polynomial.trace = true;

new Polynomial('x^4+3x^3+2x^2+6x').div('x+3');
console.log(Polynomial.trace.map(step => step.toString()));
// ['x^4+3x^3', '2x^2+6x', '0']

Polynomial.trace = null;

Browser Usage

The browser builds include all built-in coefficient implementations. No separate Fraction.js, Complex.js, or Quaternion.js scripts are required.

Use the global IIFE build directly:

<script src="https://unpkg.com/polynomial@2.0.0/dist/polynomial.min.js"></script>
<script>
  Polynomial.setField('C');
  console.log(new Polynomial('x-i').mul('x+i').toString());
</script>

Or import the standalone browser ES module:

import Polynomial from 'https://unpkg.com/polynomial@2.0.0/dist/polynomial.min.mjs';

AMD loaders receive the class as an anonymous module from polynomial.min.js.

TypeScript

The package ships declarations for ESM and CommonJS. ESM exposes the class as both the default and named Polynomial export, together with BuiltInField, PolynomialField, CoefficientMap, PolynomialInput, PolynomialQuotientRing, PolynomialResidue, and PolynomialResidueInput types.

CommonJS namespace aliases are available as Polynomial.FieldName, Polynomial.Field<C>, Polynomial.Coefficients<C>, Polynomial.Input<C>, Polynomial.QuotientRing<C>, Polynomial.Residue<C>, and Polynomial.ResidueInput<C>.

Errors

Malformed polynomial syntax throws SyntaxError. Invalid fields and exponents, division by zero, and non-invertible modular coefficients throw RangeError or TypeError as appropriate.

Development

npm install
npm test

npm test performs a strict TypeScript build, checks ESM and CommonJS declaration consumers, and runs the Node.js and standalone browser tests.

License

Licensed under the MIT license.

Name		Name	Last commit message	Last commit date
dist		dist
examples		examples
scripts		scripts
src		src
tests		tests
.gitignore		.gitignore
LICENSE		LICENSE
README.md		README.md
context7.json		context7.json
package-lock.json		package-lock.json
package.json		package.json
tsconfig.build.json		tsconfig.build.json
tsconfig.json		tsconfig.json

Navigation Menu

Uh oh!

Repository files navigation

Polynomial.js

Installation

Quick Start

Inputs

Coefficient Fields

Custom Fields

API

Construction and Configuration

Arithmetic

Calculus and Evaluation

Quotient Rings

Finite-Field Factorization

Cyclic Codes

Finite-Field Enumeration

Inspection and Formatting

Division Trace

Browser Usage

TypeScript

Errors

Development

License

About

Releases

Packages

Used by

Contributors

Languages

Uh oh!

Latest commit

History

Folders and files

Repository files navigation

Polynomial.js

Installation

Quick Start

Inputs

Coefficient Fields

Custom Fields

API

Construction and Configuration

Arithmetic

Calculus and Evaluation

Quotient Rings

Finite-Field Factorization

Cyclic Codes

Finite-Field Enumeration

Inspection and Formatting

Division Trace

Browser Usage

TypeScript

Errors

Development

License

About

Topics

Resources

Stars

Watchers

Forks

Releases

Packages

Used by

Contributors

Languages