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 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);

Resources

This is a great video intro: https://youtu.be/CoGo_3C7xR0?t=7092

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

Changelog

• 1.0.11 - Add cubic deflation. Don't use Math.pow in Polynomial.evaluate. 16x faster!
• 1.0.10 - First public release