julenum/poly

Package for polynomials.

Index

Dense

jule

type Dense: []f64

Represents a polynomial by storing all coefficients from the constant term to the highest-degree term.

For a polynomial:

P(x) = a₀ + a₁*x + a₂*x² + ... + aₙ*xⁿ

the coefficient at index i is the coefficient of xⁱ.

For example:

3x² - 4x + 7 -> Dense{7, -4, 3}

The zero polynomial is represented by an empty slice.

Coefficients are stored in ascending order of exponent:

coefficients[0] = coefficient of x⁰
coefficients[1] = coefficient of x¹
...
coefficients[n] = coefficient of xⁿ

The last coefficient must be non-zero for a non-zero polynomial. Any corruption of this invariant is undefined behavior.

Capacity of the underlying slice is never changed for values; i.e. there are no 3-operand slice expressions. Any corruption of this rule is undefined behavior.

Set

jule

#disable boundary
fn Set(mut *self, coefficients: []f64, tol: f64)

Sets self to the given coefficients.

Coefficients are ordered by increasing exponent, where coefficients[i] is the coefficient of xⁱ.

Coefficients that are zero within tolerance are removed. Since Dense stores coefficients by exponent, removing an interior coefficient means setting it to zero, while trailing zero coefficients are removed from the representation.

The resulting polynomial is always in simplified canonical form.

If self has enough capacity, Set will reuse it to avoid allocation. If coefficients is empty, self will be zero-length but keeps its capacity.

Simplify

jule

fn Simplify(mut *self, &p: *Dense, tol: f64)

Sets self to simplified form of polynomial p.

Coefficients that are zero within tolerance are set to zero. Trailing zero coefficients are removed.

Result is stored in canonical Dense representation: the zero polynomial has length zero, and the highest-degree coefficient of a non-zero polynomial is non-zero.

If self has enough capacity, Simplify will use it to avoid making allocation. If length is zero, self will be zero-length but keeps its internal allocation.

LeadingCoef

jule

fn LeadingCoef(*self): f64

Returns the leading coefficient of the polynomial. Panics if polynomial is zero.

Zero

jule

fn Zero(*self, tol: f64): bool

Reports whether polynomial is zero within tolerance.

Degree

jule

fn Degree(*self): int

Returns the degree of the polynomial (highest exponent). Returns -1 for the zero polynomial.

Negate

jule

#disable boundary
fn Negate(mut *self, &x: *Dense)

Sets self to negated coefficients of the polynomial x. For example, (3x^2 - 4x + 1) becomes (-3x^2 + 4x - 1).

If self has enough capacity, Negate will use it to avoid making allocation. If length is zero, self will be zero-length. But keeps internal allocation.

Copy

jule

fn Copy(mut *self, &x: *Dense)

Copies polynomial x to self.

If self has enough capacity, Copy will use it to avoid making allocation. If length is zero, self will be zero-length. But keeps internal allocation.

Add

jule

#disable nilptr boundary
fn Add(mut *self, &x: *Dense, &y: *Dense, tol: f64)

Sets self to sum x+y.

If self has enough capacity, Add will use it to avoid making allocation. If length is zero, self will be zero-length. But keeps internal allocation.

Sub

jule

#disable nilptr boundary
fn Sub(mut *self, &x: *Dense, &y: *Dense, tol: f64)

Sets self to difference x-y.

If self has enough capacity, Sub will use it to avoid making allocation. If length is zero, self will be zero-length. But keeps internal allocation.

Scale

jule

#disable boundary
fn Scale(mut *self, &x: *Dense, k: f64, tol: f64)

Sets self to scaled coefficients of x by scalar k. For example, if k = 2, (3x^2 - x) becomes (6x^2 - 2x).

If self have enough capacity, Scale will use it to avoid making allocation. If length is zero, self will be zero-length. But keeps internal allocation.

Mul

jule

fn Mul(mut *self, &x: *Dense, &y: *Dense)

Sets self to product x*y.

It is equivalent to MulTol(x, y, tol), but determines tolerance dynamically. Dynamic tolerance value might not be suitable for some cases. Use MulTol with custom tolerance when needed, especially for precise and small coefficients like 1e-14.

For minimum rounding-errors, use MulNaive to force native algorithms. Naive algorithm is slower than FFT, but it is more accurate.

If self have enough capacity, Mul will use it to avoid making allocation. If length is zero, self will be zero-length. But keeps internal allocation.

MulNaive

jule

fn MulNaive(mut *self, &x: *Dense, &y: *Dense)

Sets self to product x*y.

Like Mul but forces the naive algorithm and never uses FFT. Provides more accurate results, but slower for large polynomials.

If self have enough capacity, MulNaive will use it to avoid making allocation. If length is zero, self will be zero-length. But keeps internal allocation.

MulTol

jule

fn MulTol(mut *self, &x: *Dense, &y: *Dense, tol: f64)

Sets self to product x*y.

Unlike Mul, this function takes custom tolerance and uses it for FFT. If the naive algorithm is selected, tolerance is not used.

The algorithm selects between naive multiplication and FFT depending on polynomial size.

If self have enough capacity, MulTol will use it to avoid making allocation. If length is zero, self will be zero-length. But keeps internal allocation.

MulFFT

jule

fn MulFFT(mut *self, &x: *Dense, &y: *Dense, tol: f64)

Sets self to product x*y.

Like MulTol but forces FFT and never uses the naive algorithm. Provides faster computations for large polynomials, but may introduce more floating-point rounding errors.

If self have enough capacity, MulFFT will use it to avoid making allocation. If length is zero, self will be zero-length. But keeps internal allocation.

DivMod

jule

fn DivMod(mut *self, &x: *Dense, &y: *Dense, mut &rem: *Dense)

Sets self to quotient x/y, sets rem to remainder x/y if it is not nil. Panics for divide by zero.

It uses naive division for small inputs and FFT division for larger inputs. FFT division may have larger floating-point rounding errors.

If self and rem have enough capacity, DivMod will use it to avoid making allocation. If length is zero, self will be zero-length. But keeps internal allocation.

DivModNaive

jule

fn DivModNaive(mut *self, &x: *Dense, &y: *Dense, mut &rem: *Dense, tol: f64)

Sets self to quotient x/y, sets rem to remainder x/y if it is not nil.

Like DivMod but forces naive polynomial division and never uses FFT.

If self and rem have enough capacity, DivModNaive will use it to avoid making allocation. If length is zero, self will be zero-length. But keeps internal allocation.

DivModFFT

jule

fn DivModFFT(mut *self, &x: *Dense, &y: *Dense, mut &rem: *Dense, tol: f64)

Sets self to quotient x/y, sets rem to remainder x/y if it is not nil. Panics for divide by zero.

Like DivMod but forces FFT division and never uses naive division. Provides faster computations for large polynomials, but may introduce more floating-point rounding errors, especially in the remainder.

If self and rem have enough capacity, DivModFFT will use it to avoid making allocation. If length is zero, self will be zero-length. But keeps internal allocation.

Deriv

jule

#disable boundary
fn Deriv(mut *self, &x: *Dense)

Sets self to the first derivative of polynomial x.

If x = ∑ᵢ [ aᵢ * xⁱ ], then self = ∑ᵢ [ (i*aᵢ)·xⁱ⁻¹ ] for i ≥ 1.

Constant terms (exp = 0) are omitted.

If self have enough capacity, Deriv will use it to avoid making allocation. If length is zero, self will be zero-length. But keeps internal allocation.

Integral

jule

#disable boundary
fn Integral(mut *self, &x: *Dense, C: f64)

Sets self to the indefinite integral of polynomial x with constant term C. That is, integrates each term and appends a constant term.

If self have enough capacity, Integral will use it to avoid making allocation. If length is zero, self will be zero-length. But keeps internal allocation. #disable boundary

Eval

jule

#disable boundary
fn Eval(*self, x: f64): f64

Evaluates the polynomial at a given x.

Pow

jule

fn Pow(mut *self, &x: *Dense, mut n: int)

Sets self to product x^n.

Condition n >= 0 must be true.

If self have enough capacity, Pow will use it to avoid making allocation. If length is zero, self will be zero-length. But keeps internal allocation.

The implementation uses exponentiation by squaring, equivalent to NumPy's polynomial power operation.

Normalize

jule

#disable boundary
fn Normalize(mut *self, &x: *Dense, tol: f64)

Sets self to a rescaled polynomial x, so that its leading coefficient is 1. If the polynomial is zero or its leading coefficient is very small, output length is zero.

If self have enough capacity, Normalize will use it to avoid making allocation. If length is zero, self will be zero-length. But keeps internal allocation. #disable boundary

InterpolateLinear

jule

#disable boundary
fn InterpolateLinear(mut *self, x0: f64, y0: f64, x1: f64, y1: f64)

Sets self to the unique linear polynomial that passes through points (x0, y0) and (x1, y1).

The resulting coefficients are stored in ascending order: self[0] = constant term, self[1] = x coefficient.

If self have enough capacity, InterpolateLinear will use it to avoid making allocation.

AppendFormat

jule

fn AppendFormat(*self, mut buf: []byte): []byte

Appends a human-readable string representation of the polynomial to buf and returns.

String

jule

fn String(*self): string

Returns a human-readable string representation of the polynomial.

Term

jule

struct Term {
	Coef: f64
	Exp:  int
}

Represents a single term (monomial) of a polynomial. It has a coefficient and an exponent (degree).

Mathematically, a term is expressed as:

coef * x^exp, where:
	- coef ∈ ℝ (coefficient, a real number)
	- exp ∈ ℕ₀ (non-negative integer exponent)

For example:

the term 3x² is represented as Term{Coef: 3, Exp: 2}.
the term x is represented as Term{Coef: 1, Exp: 1}.
the term 2x is represented as Term{Coef: 2, Exp: 1}.
the term 1 is represented as Term{Coef: 1, Exp: 0}

Sparse

jule

type Sparse: []Term

Represents a polynomial as a slice of Terms.

A polynomial P(x) is a finite sum of terms:

P(x) = Σᵢ [ Coefᵢ * x^Expᵢ ]

where each Term is stored as an element of the Terms slice.

Terms are expected to be stored in descending order of exponent (Exp), i.e., Terms[0].Exp > Terms[1].Exp > ... > Terms[n-1].Exp, which simplifies polynomial operations like addition and multiplication. Any corruption in this order is undefined behavior.

Capacity of underlying slices is never changed for values; i.e. that there are no 3-operand slice expressions. Any corruption of this rule is undefined behavior.

Set

jule

#disable boundary
fn Set(mut *self, terms: []Term, tol: f64)

Sets self to the given terms.

Terms may be in any order. Terms with the same exponent are merged, zero coefficients within tolerance are removed, and the result is sorted by decreasing exponent. Final polynomial will be simplified.

If self has enough capacity, Set will reuse it to avoid allocation. If terms is empty, self will be zero-length but keeps its capacity.

LeadingCoef

jule

fn LeadingCoef(*self): f64

Returns the leading coefficient of the polynomial. Panics if polynomial is zero.

Zero

jule

fn Zero(*self, tol: f64): bool

Reports whether polynomial is zero within tolerance.

Degree

jule

fn Degree(*self): int

Returns the degree of the polynomial (highest exponent). Returns -1 for the zero polynomial.

Negate

jule

#disable boundary
fn Negate(mut *self, &x: *Sparse)

Sets self to negated coefficients of the polynomial x. For example, (3x^2 - 4x + 1) becomes (-3x^2 + 4x - 1).

If self have enough capacity, Negate will use it to avoid making allocation. If length is zero, self will be zero-length. But keeps internal allocation.

Copy

jule

fn Copy(mut *self, &x: *Sparse)

Copies polynomial x to self.

If self have enough capacity, Negate will use it to avoid making allocation. If length is zero, self will be zero-length. But keeps internal allocation.

Simplify

jule

fn Simplify(mut *self, &p: *Sparse, tol: f64)

Sets self to simplified form of the polynomial p. IT merges like terms and removes zero coefficients with tolerance.

Result is sorted by decreasing exponent. If the Sparse manually modified, this function may help to follow internal polynomial representation rules as described in Sparse type.

If self have enough capacity, Simplify will use it to avoid making allocation. If length is zero, self will be zero-length. But keeps internal allocation.

Add

jule

#disable boundary
fn Add(mut *self, &x: *Sparse, &y: *Sparse, tol: f64)

Sets self to sum x+y.

If self have enough capacity, Add will use it to avoid making allocation. If length is zero, self will be zero-length. But keeps internal allocation.

Sub

jule

#disable boundary
fn Sub(mut *self, &x: *Sparse, &y: *Sparse, tol: f64)

Sets self to difference x-y.

If self have enough capacity, Sub will use it to avoid making allocation. If length is zero, self will be zero-length. But keeps internal allocation.

Scale

jule

#disable boundary
fn Scale(mut *self, &x: *Sparse, k: f64, tol: f64)

Sets self to scaled coefficients of x by scalar k. For example, if k = 2, (3x^2 - x) becomes (6x^2 - 2x).

If self have enough capacity, Scale will use it to avoid making allocation. If length is zero, self will be zero-length. But keeps internal allocation.

Mul

jule

#disable boundary
fn Mul(mut *self, &x: *Sparse, &y: *Sparse)

Sets self to product x*y.

It is equals to MulTol(x, y, tol), but determines tolerance dynamically. Dynamic tolerance value might not be suitable for some cases. Use MulTol with custom tolerance when needed, especially for precise and small coefficients like 1e-14. However, small coefficients might be removed due to rounding errors during computation with custom tolerance.

For minimum rounding-errors, use MulNaive to force native algorithms. Naive algorithm is slower than FFT, but it is more accurate.

If self have enough capacity, Mul will use it to avoid making allocation. If length is zero, self will be zero-length. But keeps internal allocation.

MulNaive

jule

#disable boundary
fn MulNaive(mut *self, &x: *Sparse, &y: *Sparse)

Sets self to product x*y.

Like Mul but forces to naive algorithm and never uses FFT. Provides more accurate results, but slower for large polynomials.

If self have enough capacity, MulNaive will use it to avoid making allocation. If length is zero, self will be zero-length. But keeps internal allocation.

MulTol

jule

fn MulTol(mut *self, &x: *Sparse, &y: *Sparse, tol: f64)

Sets self to product x*y.

Unlike Mul, this function takes custom tolerance and it uses for FFT. If FFT algorithm will not be used, tolerance will not be used.

Algorithm will select naive algorithm of FFT to compute, which one is efficient for the case.

If self have enough capacity, MulTol will use it to avoid making allocation. If length is zero, self will be zero-length. But keeps internal allocation.

MulFFT

jule

fn MulFFT(mut *self, &x: *Sparse, &y: *Sparse, tol: f64)

Sets self to product x*y.

Like MulTol but forces to FFT and never uses naive algorithm. Provides faster computations for large polynomaisl, but less accurate.

If self have enough capacity, MulFFT will use it to avoid making allocation. If length is zero, self will be zero-length. But keeps internal allocation.

DivMod

jule

fn DivMod(mut *self, &x: *Sparse, &y: *Sparse, mut &rem: *Sparse)

Sets self to quotient x/y, sets rem to remainder x/y if it is not nil. Panics for divide by zero.

It uses naive division for small inputs, FFT division for larger inputs. When FFT division used, accuracy decreased due to floating-point rounding. Especiall remainder is less accurate compared to naive division.

For minimum rounding-errors, use DivModNaive to force native division. Naive algorithm is slower than FFT, but it is more accurate.

If self and rem have enough capacity, DivMod will use it to avoid making allocation. If length is zero, self will be zero-length. But keeps internal allocation.

DivModNaive

jule

fn DivModNaive(mut *self, &x: *Sparse, &y: *Sparse, mut &rem: *Sparse)

Sets self to quotient x/y, sets rem to remainder x/y if it is not nil. Panics for divide by zero.

Like DivMod but forces to naive algorithm and never uses FFT. Provides more accurate results, but slower for large polynomials.

If self and rem have enough capacity, DivMod will use it to avoid making allocation. If length is zero, self will be zero-length. But keeps internal allocation.

DivModFFT

jule

fn DivModFFT(mut *self, &x: *Sparse, &y: *Sparse, mut &rem: *Sparse)

Sets self to quotient x/y, sets rem to remainder x/y if it is not nil. Panics for divide by zero.

If self and rem have enough capacity, DivModFFT will use it to avoid making allocation. If length is zero, self will be zero-length. But keeps internal allocation.

Deriv

jule

#disable boundary
fn Deriv(mut *self, &x: *Sparse)

Sets self to the first derivative of polynomial x.

If x = ∑ᵢ [ aᵢ * xⁱ ], then self = ∑ᵢ [ (i*aᵢ)·xⁱ⁻¹ ] for i ≥ 1.

Constant terms (exp = 0) are omitted.

If self have enough capacity, Deriv will use it to avoid making allocation. If length is zero, self will be zero-length. But keeps internal allocation.

Integral

jule

#disable boundary
fn Integral(mut *self, &x: *Sparse, C: f64)

Sets self to the indefinite integral of polynomial x with constant term C. That is, integrates each term and appends a constant term.

If self have enough capacity, Integral will use it to avoid making allocation. If length is zero, self will be zero-length. But keeps internal allocation.

Eval

jule

#disable boundary
fn Eval(*self, x: f64): f64

Evaluates the polynomial at a given x.

GCD

jule

fn GCD(mut *self, &x: *Sparse, &y: *Sparse, tol: f64)

Sets self to the greatest common divisor of two polynomials x and y. Leading coefficient is normalized to 1 (if not zero).

If self have enough capacity, GCD will use it to avoid making allocation. If length is zero, self will be zero-length. But keeps internal allocation.

LCM

jule

fn LCM(mut *self, &x: *Sparse, &y: *Sparse, tol: f64)

Sets self to the least common multiple of two polynomials x and y. Leading coefficient is normalized to 1 (if not zero).

If self have enough capacity, LCM will use it to avoid making allocation. If length is zero, self will be zero-length. But keeps internal allocation.

Pow

jule

#disable boundary
fn Pow(mut *self, &x: *Sparse, mut n: int)

Sets self to product x^n. Condition n >= 0 must be true.

If self have enough capacity, Pow will use it to avoid making allocation. If length is zero, self will be zero-length. But keeps internal allocation.

Normalize

jule

#disable boundary
fn Normalize(mut *self, &x: *Sparse, tol: f64)

Sets self to rescaled polynomial x, so that its leading coefficient is 1. If the polynomial is zero or leading coefficient is very small, output length is zero.

If self have enough capacity, Normalize will use it to avoid making allocation. If length is zero, self will be zero-length. But keeps internal allocation.

InterpolateLinear

jule

#disable boundary
fn InterpolateLinear(mut *self, x0: f64, y0: f64, x1: f64, y1: f64)

Sets self to the unique linear polynomial that passes through points (x0, y0) and (x1, y1).

If self have enough capacity, InterpolateLinear will use it to avoid making allocation.

InterpolateLagrange

jule

#disable boundary
fn InterpolateLagrange(mut *self, xs: []f64, ys: []f64, tol: f64)

Sets self to the unique degree-(n-1) polynomial that passes through the given points using the Lagrange interpolation formula. Panics if input lengths differ or have duplicate x values.

If self have enough capacity, InterpolateLagrance will use it to avoid making allocation. If length is zero, self will be zero-length. But keeps internal allocation.

AppendFormat

jule

fn AppendFormat(*self, mut buf: []byte): []byte

Appends a human-readable string representation of the polynomial to buf and returns.

String

jule

fn String(*self): string

Returns a human-readable string representation of the polynomial.

julenum/poly ​

Index ​

Dense ​

Set ​

Simplify ​

LeadingCoef ​

Zero ​

Degree ​

Negate ​

Copy ​

Add ​

Sub ​

Scale ​

Mul ​

MulNaive ​

MulTol ​

MulFFT ​

DivMod ​

DivModNaive ​

DivModFFT ​

Deriv ​

Integral ​

Eval ​

Pow ​

Normalize ​

InterpolateLinear ​

AppendFormat ​

String ​

Term ​

Sparse ​

Set ​

LeadingCoef ​

Zero ​

Degree ​

Negate ​

Copy ​

Simplify ​

Add ​

Sub ​

Scale ​

Mul ​

MulNaive ​

MulTol ​

MulFFT ​

DivMod ​

DivModNaive ​

DivModFFT ​

Deriv ​

Integral ​

Eval ​

GCD ​

LCM ​

Pow ​

Normalize ​

InterpolateLinear ​

InterpolateLagrange ​

AppendFormat ​

String ​

julenum/poly

Index

Dense

Set

Simplify

LeadingCoef

Zero

Degree

Negate

Copy

Add

Sub

Scale

Mul

MulNaive

MulTol

MulFFT

DivMod

DivModNaive

DivModFFT

Deriv

Integral

Eval

Pow

Normalize

InterpolateLinear

AppendFormat

String

Term

Sparse

Set

LeadingCoef

Zero

Degree

Negate

Copy

Simplify

Add

Sub

Scale

Mul

MulNaive

MulTol

MulFFT

DivMod

DivModNaive

DivModFFT

Deriv

Integral

Eval

GCD

LCM

Pow

Normalize

InterpolateLinear

InterpolateLagrange

AppendFormat

String