all-roots
▸ function allRoots
(p: number[], lb?: number, ub?: number): number[]
Defined in roots/naive/all-roots.ts:52
Find and return all roots of the given polynomial in the given interval.
an empty array is returned for a constant or the zero polynomial
non-exact: roots are found 'naively' using double-precision arithmetic and accuracy will thus depend on the condition number around the root - use allRootsCertifiedSimplified or allRootsCertified instead if certified root bounds are required (it is about 3x slower, but still very fast!)
close (where the definition of closeness depends on the condition number) or multiple even roots can be returned as 0, 1 or more close roots, whereas close or multiple odd roots are guaranteed to return at least 1 root
optimized for polynomials of degree 1 to about 30
roots are refined using the celebrated Brent's Method (and evaluated using Horner's Method) until a root interval is found with width
<= eps * max(1, 2^⌈log₂r⌉), whereeps = Number.EPSILONandris a rootordered: the returned roots are ordered from lowest to highest
Parameters:
| Name | Type | Default value | Description |
|---|---|---|---|
p | number[] | - | a polynomial with coefficients given densely as an array of double floating point numbers from highest to lowest power, e.g. [5,-3,0] represents the polynomial 5x^2 - 3x |
lb | number | Number.NEGATIVE_INFINITY | defaults to Number.NEGATIVE_INFINITY; lower bound of roots to be returned |
ub | number | Number.POSITIVE_INFINITY | defaults to Number.POSITIVE_INFINITY; upper bound of roots to be returned |
Returns: number[]