nomial

Nomial

Nomial is a TypeScript implementation of Cem Yuksel's extremely fast, robust, and simple root finding algorithm presented in the paper "High-Performance Polynomial Root Finding for Graphics" (2022). It can be used to find real roots of polynomials of degree 10 and higher. This package has no dependencies and is 1.5kb minified and 787B minified & gzipped.

Installation

npm install nomial

or using yarn

yarn add nomial

Usage

Importing

// as a ES module
import { Polynomial, polynomialRoots } from 'nomial';

// as a CommonJS module
const { Polynomial, polynomialRoots } = require('nomial');

Calling

The API is a single function that returns the roots given the polynomial coefficients.

// The coefficients are stored in order of increasing exponent so this polynomial corresponds to
// -7412 - 1505x - 20x^2 - 10x^3 + 2x^4 + x^5
const f = new Polynomial([-7412, -1505, -20, -10, 2, 1]);
const roots = polynomialRoots(f);

There are optional arguments to specify the start and end of the search interval and epsilon used to terminate root finding.

const startSearchInterval = -100;
const endSearchInterval = 100;
const epsilon = 1e-6;

const roots = polynomialRoots(f, startSearchInterval, endSearchInterval, epsilon);

Paper

Cem Yuksel. 2022. High-Performance Polynomial Root Finding for Graphics. Proc. ACM Comput. Graph. Interact. Tech. 5, 3, Article 7 (July 2022), 15 pages.