Polynomial toolkit¶
The toolkit builds on the existing exact and numerical polynomial types.
Every computational call takes a shared Budget; numerical arithmetic also
takes an explicit apn_mojo context. The calculus, interpolation,
rational-function, basis, and series groups each start with a focused example.
"""A compact tour of the expanded polynomial toolkit."""
from apn_mojo import Rational, BallContext
from polynomials import *
def main() raises:
var work = Budget()
var ring = PolynomialRing[QQ].create(["x"], NoContext(), work)
var p = DensePoly[QQ].from_sparse(ring.parse("(x+1)^3", work), work, variable=Int64(0))
if derivative_dense(integrate_dense(p, work), work) != p:
raise Error("calculus identity failed")
var nodes: List[QQ] = [QQ(Rational(0)), QQ(Rational(1)), QQ(Rational(2)), QQ(Rational(3))]
var plan = MultipointPlan[QQ].prepare(0, NoContext(), nodes, work)
var values = plan.evaluate(p, work)
if not check_interpolation(plan.interpolate(values, work), nodes, values, work):
raise Error("interpolation witness failed")
if deserialize_dense[QQ](serialize_dense(p, work), NoContext(), work) != p:
raise Error("interchange failed")
print("Calculus, interpolation and interchange checked")
var basis = BasisPolynomial[QQ].bernstein(p, 5, work)
var series = TruncatedSeries[QQ].from_polynomial(p, 6, work)
if basis.to_polynomial(work) != p or series.log(work).exp(work).polynomial != p:
raise Error("basis or formal-series identity failed")
print("Basis conversion and formal series checked")
var fraction = RationalFunction.normalize(ring.parse("x^2", work), ring.parse("x-1", work), work)
var parts = partial_fractions(fraction[0], 0, work)
var local = laurent_expansion(fraction[0], 0, QQ(Rational(1)), 4, work)
if not check_partial_fractions(fraction[0], 0, parts, work) or not check_laurent_expansion(fraction[0], local, work):
raise Error("rational-function witness failed")
print("Partial fractions and Laurent expansion checked")
var context = BallContext(128)
var numerical = numeric_from_dense[BallDomain, QQ](p, context, work)
var divisor = numeric_from_dense[BallDomain, QQ](DensePoly[QQ].from_sparse(ring.parse("x+1", work), work, variable=Int64(0)), context, work)
var division = numeric_divmod(numerical, divisor, context, work)
if not check_numeric_division(numerical, divisor, division, work):
raise Error("numerical division witness failed")
var coarse = NumericOptions(absolute_bits=2, max_subdivisions=32)
var fine = NumericOptions(absolute_bits=5, max_subdivisions=64)
var roots = real_roots_exact(p, coarse, work, complete_only=True)
var refined = refine_real_roots_exact(p, roots, coarse, fine, work, complete_only=True)
var multiplicity = real_root_multiplicities(p, refined, fine, work)
if not check_real_root_multiplicities(p, refined, fine, multiplicity, work):
raise Error("root multiplicity witness failed")
print("Numerical division, root refinement and multiplicity checked")
Run from the repository root pixi run mojo run -I build docs/examples/toolkit.mojo
Output
Calculus, interpolation and interchange checked
Basis conversion and formal series checked
Partial fractions and Laurent expansion checked
Numerical division, root refinement and multiplicity checked
Choosing the operation¶
| Need | Entry points and guarantees |
|---|---|
| Calculus and transforms | integrate_dense, definite_integral, compose_dense, affine_transform, taylor_shift, jet_evaluate, substitute_many; corresponding numerical functions use explicit contexts |
| Repeated evaluation or interpolation | MultipointPlan.prepare stores a balanced product tree; .evaluate permits repeated nodes, .interpolate requires distinct nodes |
| Derivative constraints | hermite_interpolate takes raw derivatives by default; derivatives=False takes Taylor/Hasse coefficients and avoids factorial assumptions |
| Named expressions | PolynomialRing.create maps names to stable IDs; .parse accepts a bounded polynomial grammar and .format round trips exact coefficients |
| Persistence | serialize_dense/serialize_sparse and numerical counterparts retain domains and representation metadata; decoding is strict |
| Rational functions | Evaluation, differentiation, simultaneous polynomial substitution, univariate rational composition, partial fractions, pole factors, Laurent coefficients and residues |
| Alternative bases | BasisPolynomial and NumericBasisPolynomial provide Newton, first-kind Chebyshev and Bernstein representations; Bernstein retains its degree |
| Formal series | TruncatedSeries and NumericSeries carry a known order modulo x^n; binary operations require equal orders, and .truncate only reduces precision |
| Root refinement | refine_real_roots_* and refine_complex_roots_* check earlier evidence, retain satisfactory regions and apply a new subdivision allowance |
| Repeated exact real roots | real_root_multiplicities adds a squarefree decomposition and the vanishing block of each root to a complete Descartes result |
| Root diagnostics | Residual, absolute coefficient backward-error and local derivative-sensitivity bounds are rational; sensitivity is a root condition bound only at a root |
| Newton polishing | polish_root_* treats iterates as candidates and proves a one-root rectangle independently before reporting success |
| Numerical division | Point domains return rounded q/r and full residual bounds; ball domains also prove uniform enclosure of exact Euclidean q/r |
Basis and series types use exact coefficient fields; rational_dense promotes
integer inputs for those operations. Exact antiderivatives require the
coefficient divisions to exist; use
integrate_integer_dense or integrate_integer_sparse to promote ZZ to QQ.
Chebyshev and Bernstein conversions can reject finite-characteristic fields
when their conversion factors are not invertible. Series composition requires
an exactly zero inner constant, logarithm requires constant one, exponential
requires constant zero, and reversion requires a nonzero linear coefficient.
A formal truncation supplies no analytic tail bound.
Numerical point operations round; ball operations enclose every represented
coefficient selection. Numerical interpolation requires separated node
intervals. In family division, the exact quotient and remainder belonging to
an input pair lie in the reported coefficient boxes; arbitrary independent
selections from those output boxes need not satisfy the division identity.
The separate residual bounds cover f-q*g-r even for independent selections.
Newton polishing uses the midpoint representative only to generate candidates
for uncertain coefficient families; its contour witness checks the original
family. A Newton-correction bound is a step-size bound, not a root-distance
bound.
Core partial-fraction checkers prove properness and recomposition without asserting irreducibility. Pole factors represent all their complex zeros. Laurent expansions and residues currently take rational centers. General algebraic coefficient fields are outside these core rational utilities. The array rational API supports QQ, QQi, AA, and QQbar and adds complete-normalization and irreducibility checks.
Calculus and transformations¶
For \(p(x)=3x^2+2x\), integrate_dense returns \(x^3+x^2\), and the integral
from \(0\) to \(1\) is exactly \(2\). The example also substitutes \(x+1\) with
compose_dense:
"""Integrate a polynomial exactly and evaluate a definite integral."""
from std.testing import assert_equal
from apn_mojo import Rational
from polynomials import Budget, QQ, NoContext, PolynomialRing, DensePoly, integrate_dense, derivative_dense, definite_integral, compose_dense
def main() raises:
var work = Budget()
var ring = PolynomialRing[QQ].create(["x"], NoContext(), work)
var polynomial = DensePoly[QQ].from_sparse(ring.parse("3*x^2 + 2*x", work), work, variable=Int64(0))
var primitive = integrate_dense(polynomial, work)
assert_equal(derivative_dense(primitive, work), polynomial)
var area = definite_integral(polynomial, QQ(Rational(0)), QQ(Rational(1)), work)
assert_equal(area.value, Rational(2))
var inner = DensePoly[QQ].from_sparse(ring.parse("x + 1", work), work, variable=Int64(0))
var shifted = compose_dense(polynomial, inner, work)
var expected = DensePoly[QQ].from_sparse(ring.parse("3*x^2 + 8*x + 5", work), work, variable=Int64(0))
assert_equal(shifted, expected)
print("Integral from 0 to 1:", area.value)
print("Substitution checked:", shifted == expected)
Run from the repository root pixi run mojo run -I build docs/examples/tutorial_calculus.mojo
Output
Integral from 0 to 1: 2
Substitution checked: True
derivative_dense¶
def derivative_dense[C: CoefficientRing](poly: DensePoly[C], mut budget: Budget) raises PolyError -> DensePoly[C]
Differentiate a dense polynomial exactly.
Parameters.
C: The exact coefficient ring.
Arguments.
poly: The input polynomial.budget: The shared work allowance.
Returns. The formal derivative, retaining the variable and coefficient ring.
Raises.
PolyError: DOMAIN for invalid input, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/calculus.mojo.
rational_dense¶
def rational_dense(poly: DensePoly[ZZ], mut budget: Budget) raises PolyError -> DensePoly[QQ]
Promote an integer polynomial explicitly to rational coefficients.
Arguments.
poly: The integer polynomial.budget: The shared work allowance.
Returns. The same polynomial over QQ.
Raises.
PolyError: DOMAIN for invalid input, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/calculus.mojo.
rational_sparse¶
def rational_sparse(poly: SparsePoly[ZZ], mut budget: Budget) raises PolyError -> SparsePoly[QQ]
Promote a sparse integer polynomial explicitly to QQ.
Arguments.
poly: The integer polynomial.budget: The shared work allowance.
Returns. The same polynomial with rational coefficients.
Raises.
PolyError: DOMAIN for invalid input, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/calculus.mojo.
integrate_dense¶
def integrate_dense[C: CoefficientRing](poly: DensePoly[C], mut budget: Budget) raises PolyError -> DensePoly[C]
Integrate exactly with zero constant when coefficient divisions exist.
Parameters.
C: An exact ring supporting the required divisions.
Arguments.
poly: The input polynomial.budget: The shared work allowance.
Returns. The zero-constant antiderivative in the same ring.
Raises.
PolyError: DOMAIN for a nonintegrable term, UNSUPPORTED for missing exact division, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/calculus.mojo.
integrate_integer_dense¶
def integrate_integer_dense(poly: DensePoly[ZZ], mut budget: Budget) raises PolyError -> DensePoly[QQ]
Integrate an integer polynomial after explicit rational promotion.
Arguments.
poly: The integer polynomial.budget: The shared work allowance.
Returns. Its rational antiderivative with zero constant.
Raises.
PolyError: DOMAIN for invalid input, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/calculus.mojo.
definite_integral¶
def definite_integral[C: CoefficientRing](poly: DensePoly[C], low: C, high: C, mut budget: Budget) raises PolyError -> C
Evaluate an exact antiderivative difference at two endpoints.
Parameters.
C: An exact ring supporting the required divisions.
Arguments.
poly: The polynomial.low: The lower endpoint in its coefficient ring.high: The upper endpoint in its coefficient ring.budget: The shared work allowance.
Returns. F(high) minus F(low), where F is an antiderivative.
Raises.
PolyError: DOMAIN for incompatible endpoints or nonintegrable terms, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/calculus.mojo.
compose_dense¶
def compose_dense[C: CoefficientRing](outer: DensePoly[C], inner: DensePoly[C], mut budget: Budget) raises PolyError -> DensePoly[C]
Substitute a dense polynomial into another in the same variable.
Parameters.
C: The exact coefficient ring.
Arguments.
outer: The outer polynomial.inner: The replacement polynomial.budget: The shared work allowance.
Returns. The exact composition outer(inner).
Raises.
PolyError: DOMAIN for incompatible inputs, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/calculus.mojo.
affine_transform¶
def affine_transform[C: CoefficientRing](poly: DensePoly[C], scale: C, shift: C, mut budget: Budget) raises PolyError -> DensePoly[C]
Compute p(scale*x + shift) exactly.
Parameters.
C: The exact coefficient ring.
Arguments.
poly: The polynomial.scale: The variable scale in the coefficient ring.shift: The translation in the coefficient ring.budget: The shared work allowance.
Returns. The transformed polynomial.
Raises.
PolyError: DOMAIN for incompatible inputs, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/calculus.mojo.
taylor_shift¶
def taylor_shift[C: CoefficientRing](poly: DensePoly[C], point: C, mut budget: Budget) raises PolyError -> DensePoly[C]
Compute p(x + point) without factorial division.
Parameters.
C: The exact coefficient ring.
Arguments.
poly: The polynomial.point: The shift in its coefficient ring.budget: The shared work allowance.
Returns. The Taylor polynomial in the shifted variable.
Raises.
PolyError: DOMAIN for incompatible input, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/calculus.mojo.
jet_evaluate¶
def jet_evaluate[C: CoefficientRing](poly: DensePoly[C], point: C, order: Int, mut budget: Budget) raises PolyError -> List[C]
Evaluate Taylor coefficients through degree order minus one.
Parameters.
C: The exact coefficient ring.
Arguments.
poly: The polynomial.point: The expansion point.order: The nonnegative number of coefficients requested.budget: The shared work allowance.
Returns. Hasse derivatives, equal to p^(k)(point)/k! in characteristic zero.
Raises.
PolyError: DOMAIN for a negative order or mixed rings, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/calculus.mojo.
integrate_sparse¶
def integrate_sparse[C: CoefficientRing](poly: SparsePoly[C], variable: Int64, mut budget: Budget) raises PolyError -> SparsePoly[C]
Integrate one sparse variable with zero integration constant.
Parameters.
C: An exact ring supporting the required coefficient divisions.
Arguments.
poly: The polynomial.variable: The integration variable, allowed by its monomial order.budget: The shared work allowance.
Returns. An exact antiderivative in that variable.
Raises.
PolyError: DOMAIN for unavailable divisions or invalid variables, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/calculus.mojo.
integrate_integer_sparse¶
def integrate_integer_sparse(poly: SparsePoly[ZZ], variable: Int64, mut budget: Budget) raises PolyError -> SparsePoly[QQ]
Integrate sparse integer coefficients after promotion to QQ.
Arguments.
poly: The integer polynomial.variable: The integration variable.budget: The shared work allowance.
Returns. Its rational antiderivative with zero integration constant.
Raises.
PolyError: DOMAIN for invalid inputs, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/calculus.mojo.
substitute_many¶
def substitute_many[C: CoefficientRing](poly: SparsePoly[C], assignments: List[Tuple[Int64, SparsePoly[C]]], mut budget: Budget) raises PolyError -> SparsePoly[C]
Replace several variables simultaneously, retaining unassigned variables.
Parameters.
C: The exact coefficient ring.
Arguments.
poly: The polynomial.assignments: Distinct variable IDs and replacements in its ring and order.budget: The shared work allowance.
Returns. The simultaneous substitution, with no substitutions inside replacements.
Raises.
PolyError: DOMAIN for duplicates or incompatible inputs, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/calculus.mojo.
numeric_integrate_dense¶
def numeric_integrate_dense[D: NumericDomain](poly: NumericDensePoly[D], context: D.Context, mut budget: Budget) raises PolyError -> NumericDensePoly[D]
Integrate coefficient-wise using an explicit numerical context.
Parameters.
D: The numerical domain.
Arguments.
poly: The polynomial.context: The rounding or enclosing arithmetic settings.budget: The shared work allowance.
Returns. A rounded or enclosing antiderivative with zero constant.
Raises.
PolyError: DOMAIN for invalid values or contexts, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/numeric_calculus.mojo.
numeric_definite_integral¶
def numeric_definite_integral[D: NumericDomain](poly: NumericDensePoly[D], low: D.Scalar, high: D.Scalar, context: D.Context, mut budget: Budget) raises PolyError -> D.Scalar
Evaluate a numerical antiderivative difference at explicit endpoints.
Parameters.
D: The numerical domain.
Arguments.
poly: The polynomial.low: The lower endpoint.high: The upper endpoint.context: The explicit arithmetic settings.budget: The shared work allowance.
Returns. A rounded value or uniform enclosure of the integral difference.
Raises.
PolyError: DOMAIN for invalid values or contexts, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/numeric_calculus.mojo.
numeric_compose_dense¶
def numeric_compose_dense[D: NumericDomain](outer: NumericDensePoly[D], inner: NumericDensePoly[D], context: D.Context, mut budget: Budget) raises PolyError -> NumericDensePoly[D]
Compose numerical polynomials by a fixed Horner schedule.
Parameters.
D: The numerical domain.
Arguments.
outer: The outer polynomial.inner: The replacement in the same variable.context: The explicit arithmetic settings.budget: The shared work allowance.
Returns. The rounded composition or coefficient enclosures of every composition.
Raises.
PolyError: DOMAIN for incompatible values, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/numeric_calculus.mojo.
numeric_affine_transform¶
def numeric_affine_transform[D: NumericDomain](poly: NumericDensePoly[D], scale: D.Scalar, shift: D.Scalar, context: D.Context, mut budget: Budget) raises PolyError -> NumericDensePoly[D]
Compose with scale*x + shift using the requested precision.
Parameters.
D: The numerical domain.
Arguments.
poly: The polynomial.scale: The finite scalar or enclosure multiplying x.shift: The finite translation or enclosure.context: The explicit arithmetic settings.budget: The shared work allowance.
Returns. The rounded or enclosing transformed polynomial.
Raises.
PolyError: DOMAIN for invalid values, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/numeric_calculus.mojo.
numeric_jet_evaluate¶
def numeric_jet_evaluate[D: NumericDomain](poly: NumericDensePoly[D], point: D.Scalar, order: Int, context: D.Context, mut budget: Budget) raises PolyError -> List[D.Scalar]
Compute numerical Taylor coefficients by generalized Horner evaluation.
Parameters.
D: The numerical domain.
Arguments.
poly: The polynomial.point: The expansion point or enclosure.order: The nonnegative number of Taylor coefficients.context: The explicit arithmetic settings.budget: The shared work allowance.
Returns. Rounded coefficients or uniform enclosures, including requested zero padding.
Raises.
PolyError: DOMAIN for invalid values or negative order, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/numeric_calculus.mojo.
numeric_taylor_shift¶
def numeric_taylor_shift[D: NumericDomain](poly: NumericDensePoly[D], point: D.Scalar, context: D.Context, mut budget: Budget) raises PolyError -> NumericDensePoly[D]
Translate the variable using numerical Taylor coefficients.
Parameters.
D: The numerical domain.
Arguments.
poly: The polynomial.point: The shift or its enclosure.context: The explicit arithmetic settings.budget: The shared work allowance.
Returns. A rounded or enclosing polynomial for p(x + point).
Raises.
PolyError: DOMAIN for invalid values, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/numeric_calculus.mojo.
numeric_integrate_sparse¶
def numeric_integrate_sparse[D: NumericDomain](poly: NumericSparsePoly[D], variable: Int64, context: D.Context, mut budget: Budget) raises PolyError -> NumericSparsePoly[D]
Integrate a sparse numerical polynomial in one variable.
Parameters.
D: The numerical domain.
Arguments.
poly: The input polynomial.variable: The integration variable allowed by its order.context: The explicit arithmetic settings.budget: The shared work allowance.
Returns. A rounded or enclosing antiderivative with zero integration constant.
Raises.
PolyError: DOMAIN for invalid values or variables, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/numeric_calculus.mojo.
numeric_substitute_many¶
def numeric_substitute_many[D: NumericDomain](poly: NumericSparsePoly[D], assignments: List[Tuple[Int64, NumericSparsePoly[D]]], context: D.Context, mut budget: Budget) raises PolyError -> NumericSparsePoly[D]
Replace numerical variables simultaneously in a fixed term order.
Parameters.
D: The numerical domain.
Arguments.
poly: The input polynomial.assignments: Distinct variable IDs and replacement polynomials.context: The explicit arithmetic settings.budget: The shared work allowance.
Returns. A rounded composition or an enclosure of every represented composition.
Raises.
PolyError: DOMAIN for duplicates or incompatible inputs, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/numeric_calculus.mojo.
Interpolation¶
Use MultipointPlan.prepare for evaluation, including repeated nodes. Use
MultipointPlan.prepare_interpolation when interpolating multiple value lists
at the same distinct nodes: it retains the inverse derivative weights as well
as the product tree. Both plans are immutable; preparation consumes its own
budget, and each interpolation call has a predictable work charge. The ordinary
plan and the one-shot interpolate function still work without a weight cache.
The values \(1,4,9\) at \(0,1,2\) determine \((x+1)^2\). The example builds a plan,
interpolates, checks the result with check_interpolation, and reuses the
plan for evaluation:
"""Recover a quadratic from exact values at three distinct points."""
from std.testing import assert_equal, assert_true
from apn_mojo import Rational
from polynomials import Budget, QQ, NoContext, PolynomialRing, DensePoly, MultipointPlan, check_interpolation
def main() raises:
var work = Budget()
var nodes: List[QQ] = [QQ(Rational(0)), QQ(Rational(1)), QQ(Rational(2))]
var values: List[QQ] = [QQ(Rational(1)), QQ(Rational(4)), QQ(Rational(9))]
var plan = MultipointPlan[QQ].prepare_interpolation(0, NoContext(), nodes, work)
var polynomial = plan.interpolate(values, work)
var ring = PolynomialRing[QQ].create(["x"], NoContext(), work)
var expected = DensePoly[QQ].from_sparse(ring.parse("(x + 1)^2", work), work, variable=Int64(0))
assert_equal(polynomial, expected)
assert_true(check_interpolation(polynomial, nodes, values, work))
var recovered = plan.evaluate(polynomial, work)
for i in range(len(values)):
assert_equal(recovered[i], values[i])
print("Recovered (x + 1)^2:", polynomial == expected)
print("Value at 2:", recovered[2].value)
Run from the repository root pixi run mojo run -I build docs/examples/tutorial_interpolation.mojo
Output
Recovered (x + 1)^2: True
Value at 2: 9
For arbitrary-precision exact fields, calls with at least 32 points release coefficient buffers after their last tree consumer. The reusable product tree stays in the plan.
MultipointPlan¶
@fieldwise_init
struct MultipointPlan[C: CoefficientField](Copyable, Movable)
Reuse a balanced product tree for exact evaluation and interpolation.
Parameters.
C: The exact coefficient field.
Defined in src/polynomials/interpolation.mojo.
MultipointPlan.prepare¶
@staticmethod
def prepare(variable: Int64, ring: Self.C.Context, points: List[Self.C], mut budget: Budget) raises PolyError -> Self
Prepare immutable product factors for an ordered point list.
Arguments.
variable: The retained polynomial variable.ring: The coefficient field context.points: Evaluation points; repetitions are allowed for evaluation.budget: The shared work allowance.
Returns. A reusable product tree with privately stored nodes.
Raises.
PolyError: DOMAIN for invalid points or variable, LIMIT or CAPACITY on work limits.
MultipointPlan.prepare_interpolation¶
@staticmethod
def prepare_interpolation(variable: Int64, ring: Self.C.Context, points: List[Self.C], mut budget: Budget) raises PolyError -> Self
Prepare a product tree and immutable inverse interpolation weights.
Arguments.
variable: The retained polynomial variable.ring: The coefficient field context.points: Distinct evaluation and interpolation nodes.budget: The shared work allowance, including weight preparation.
Returns. A reusable plan whose interpolation calls reuse inverse derivative weights.
Raises.
PolyError: DOMAIN for repeated or invalid points, LIMIT or CAPACITY on work limits.
MultipointPlan.point_count¶
def point_count(self) -> Int
Return the number of prepared points.
Returns. The point count, including repetitions.
MultipointPlan.evaluate¶
def evaluate(self, poly: DensePoly[Self.C], mut budget: Budget) raises PolyError -> List[Self.C]
Evaluate by propagating remainders down the prepared tree.
Arguments.
poly: The polynomial in this plan's field and variable.budget: The shared work allowance.
Returns. Values in the original point order.
Raises.
PolyError: DOMAIN for incompatible input, LIMIT or CAPACITY on work limits.
MultipointPlan.interpolate¶
def interpolate(self, values: List[Self.C], mut budget: Budget) raises PolyError -> DensePoly[Self.C]
Interpolate values using derivative weights and the product tree.
Arguments.
values: One value per prepared point.budget: The shared work allowance.
Returns. The unique polynomial of degree less than the point count.
Raises.
PolyError: DOMAIN for duplicate points or incompatible values, LIMIT or CAPACITY on work limits.
interpolate¶
def interpolate[C: CoefficientField](variable: Int64, ring: C.Context, points: List[C], values: List[C], mut budget: Budget) raises PolyError -> DensePoly[C]
Interpolate distinct points over an exact field.
Parameters.
C: The exact coefficient field.
Arguments.
variable: The output variable.ring: The coefficient field context.points: Distinct interpolation nodes.values: Corresponding function values.budget: The shared work allowance.
Returns. The degree-bounded interpolant, or zero for empty data.
Raises.
PolyError: DOMAIN for invalid data, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/interpolation.mojo.
hermite_interpolate¶
def hermite_interpolate[C: CoefficientField](variable: Int64, ring: C.Context, points: List[C], jets: List[List[C]], mut budget: Budget, *, derivatives: Bool = True) raises PolyError -> DensePoly[C]
Interpolate value and derivative constraints over an exact field.
Parameters.
C: The exact coefficient field.
Arguments.
variable: The output variable.ring: The coefficient field context.points: Distinct interpolation nodes.jets: Nonempty consecutive derivative lists beginning with the value.budget: The shared work allowance.derivatives: Interpret jets as raw derivatives; false selects Taylor coefficients.
Returns. The unique polynomial of degree less than the number of constraints.
Raises.
PolyError: DOMAIN for invalid data or noninvertible factorials, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/interpolation.mojo.
check_interpolation¶
def check_interpolation[C: CoefficientField](poly: DensePoly[C], points: List[C], values: List[C], mut budget: Budget) raises PolyError -> Bool
Check degree, distinct nodes and sample identities independently.
Parameters.
C: The exact coefficient field.
Arguments.
poly: The proposed interpolant.points: Interpolation nodes.values: Claimed sample values.budget: The shared work allowance.
Returns. Whether the constraints uniquely identify this polynomial.
Raises.
PolyError: DOMAIN for malformed coefficients, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/interpolation.mojo.
check_hermite_interpolation¶
def check_hermite_interpolation[C: CoefficientField](poly: DensePoly[C], points: List[C], jets: List[List[C]], mut budget: Budget, *, derivatives: Bool = True) raises PolyError -> Bool
Check Hermite constraints by Taylor evaluation and a degree bound.
Parameters.
C: The exact coefficient field.
Arguments.
poly: The proposed interpolant.points: Distinct interpolation nodes.jets: Claimed consecutive constraints beginning with the value.budget: The shared work allowance.derivatives: Whether constraints are raw derivatives instead of Taylor coefficients.
Returns. Whether all constraints uniquely identify the polynomial.
Raises.
PolyError: DOMAIN for malformed coefficients, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/interpolation.mojo.
numeric_multipoint_evaluate¶
def numeric_multipoint_evaluate[D: NumericDomain](poly: NumericDensePoly[D], points: List[D.Scalar], context: D.Context, mut budget: Budget) raises PolyError -> List[D.Scalar]
Evaluate numerical samples using a fixed Horner schedule per point.
Parameters.
D: The numerical domain.
Arguments.
poly: The polynomial or coefficient family.points: The evaluation points or enclosures.context: Explicit rounding or enclosure settings.budget: The shared work allowance.
Returns. Rounded values or uniform enclosures in point order.
Raises.
PolyError: DOMAIN for invalid input, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/numeric_interpolation.mojo.
numeric_interpolate¶
def numeric_interpolate[D: NumericDomain](variable: Int64, points: List[D.Scalar], values: List[D.Scalar], context: D.Context, mut budget: Budget) raises PolyError -> NumericDensePoly[D]
Interpolate numerical data by divided differences.
Parameters.
D: The numerical domain.
Arguments.
variable: The output polynomial variable.points: Distinct nodes, or pairwise separated node enclosures.values: Corresponding values or enclosures.context: Explicit rounding or enclosure settings.budget: The shared work allowance.
Returns. A rounded interpolant or coefficient enclosures for every data selection.
Raises.
PolyError: DOMAIN for invalid data or node differences containing zero, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/numeric_interpolation.mojo.
numeric_hermite_interpolate¶
def numeric_hermite_interpolate[D: NumericDomain](variable: Int64, points: List[D.Scalar], jets: List[List[D.Scalar]], context: D.Context, mut budget: Budget, *, derivatives: Bool = True) raises PolyError -> NumericDensePoly[D]
Interpolate numerical values and consecutive derivative constraints.
Parameters.
D: The numerical domain.
Arguments.
variable: The output variable.points: Distinct nodes or separated node enclosures.jets: Nonempty consecutive constraints beginning with the value.context: Explicit rounding or enclosure settings.budget: The shared work allowance.derivatives: Select raw derivatives; false selects Taylor coefficients.
Returns. A rounded interpolant or coefficient enclosures for every data selection.
Raises.
PolyError: DOMAIN for invalid data or inseparable nodes, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/numeric_interpolation.mojo.
Construction and interchange¶
Version-one serializers build one output buffer; decoders validate terms as they read them into the final polynomial, using at most 64 text rows of scratch storage for exact sparse input. They preserve canonical bytes and reject malformed metadata, noncanonical scalars and trailing data. These are internal memory improvements; the text format and public APIs are unchanged.
PolynomialRing¶
@fieldwise_init
struct PolynomialRing[C: CoefficientRing](Copyable, Movable)
Bind ASCII variable names to stable consecutive IDs and an exact ring.
Parameters.
C: A built-in exact coefficient domain for parsing and formatting.
Defined in src/polynomials/builders.mojo.
PolynomialRing.create¶
@staticmethod
def create(names: List[String], ring: Self.C.Context, mut budget: Budget, *, kind: UInt8 = MonomialOrder.LEX) raises PolyError -> Self
Create a named ring with IDs equal to name positions.
Arguments.
names: Distinct ASCII identifiers; i is reserved over QQi.ring: The exact coefficient context.budget: The shared work allowance.kind: The admissible monomial order kind.
Returns. The prepared named-variable builder.
Raises.
PolyError: DOMAIN for invalid names or orders, LIMIT or CAPACITY on work limits.
PolynomialRing.variable¶
def variable(self, name: String, mut budget: Budget) raises PolyError -> SparsePoly[Self.C]
Construct a variable by its configured name.
Arguments.
name: A name supplied when creating the ring.budget: The shared work allowance.
Returns. The corresponding polynomial generator.
Raises.
PolyError: DOMAIN for an unknown name, LIMIT or CAPACITY on work limits.
PolynomialRing.parse¶
def parse(self, text: String, mut budget: Budget) raises PolyError -> SparsePoly[Self.C]
Parse a restricted polynomial expression without executing code.
Arguments.
text: Integers, names, parentheses, unary signs, +, -, *, scalar / and literal nonnegative powers.budget: The shared work allowance.
Returns. The canonical expanded polynomial; exponent chains require parentheses.
Raises.
PolyError: ENCODING for malformed grammar, DOMAIN for unsupported division or names, LIMIT or CAPACITY on work limits.
PolynomialRing.format¶
def format(self, poly: SparsePoly[Self.C], mut budget: Budget) raises PolyError -> String
Format a polynomial as a parsable named-variable expression.
Arguments.
poly: A polynomial in the configured coefficient ring and order.budget: The shared work allowance.
Returns. Exact coefficient text in decreasing term order.
Raises.
PolyError: DOMAIN for incompatible variables or contexts, LIMIT or CAPACITY on work limits.
serialize_dense¶
def serialize_dense[C: CoefficientRing](poly: DensePoly[C], mut budget: Budget) raises PolyError -> String
Serialize exact dense coefficients and their variable and domain.
Parameters.
C: ZZ, QQ, QQi or ModInt.
Arguments.
poly: The canonical dense polynomial.budget: The shared work allowance.
Returns. Canonical version-one polynomial text, including a final newline.
Raises.
PolyError: DOMAIN for invalid input, UNSUPPORTED for other domains, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/interchange.mojo.
deserialize_dense¶
def deserialize_dense[C: CoefficientRing](text: String, ring: C.Context, mut budget: Budget) raises PolyError -> DensePoly[C]
Decode canonical exact dense interchange without repairing malformed data.
Parameters.
C: The expected built-in exact coefficient domain.
Arguments.
text: Version-one polynomial text.ring: The expected context, including the prime modulus.budget: The shared work allowance.
Returns. The exact dense polynomial with its original variable.
Raises.
PolyError: ENCODING for malformed or incompatible text, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/interchange.mojo.
serialize_sparse¶
def serialize_sparse[C: CoefficientRing](poly: SparsePoly[C], mut budget: Budget) raises PolyError -> String
Serialize exact sparse terms, their order and coefficient domain.
Parameters.
C: ZZ, QQ, QQi or ModInt.
Arguments.
poly: The canonical sparse polynomial.budget: The shared work allowance.
Returns. Canonical version-one polynomial text.
Raises.
PolyError: DOMAIN for invalid input, UNSUPPORTED for other domains, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/interchange.mojo.
deserialize_sparse¶
def deserialize_sparse[C: CoefficientRing](text: String, ring: C.Context, mut budget: Budget) raises PolyError -> SparsePoly[C]
Decode exact sparse interchange while enforcing canonical term order.
Parameters.
C: The expected built-in exact coefficient domain.
Arguments.
text: Version-one polynomial text.ring: The expected coefficient context.budget: The shared work allowance.
Returns. The exact sparse polynomial, retaining its monomial order.
Raises.
PolyError: ENCODING for malformed or incompatible text, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/interchange.mojo.
serialize_numeric_dense¶
def serialize_numeric_dense[D: NumericDomain](poly: NumericDensePoly[D], mut budget: Budget) raises PolyError -> String
Serialize numerical dense coefficients without rounding them.
Parameters.
D: The numerical domain.
Arguments.
poly: The canonical numerical polynomial.budget: The shared work allowance.
Returns. Version-one text preserving scalar formats and ball enclosures exactly.
Raises.
PolyError: DOMAIN for invalid input, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/numeric_interchange.mojo.
deserialize_numeric_dense¶
def deserialize_numeric_dense[D: NumericDomain](text: String, mut budget: Budget) raises PolyError -> NumericDensePoly[D]
Read numerical dense coefficients exactly from versioned interchange.
Parameters.
D: The expected numerical domain.
Arguments.
text: Canonical version-one polynomial text.budget: The shared work allowance.
Returns. The original scalar values, formats and retained polynomial variable.
Raises.
PolyError: ENCODING for malformed text, DOMAIN for nonfinite coefficients, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/numeric_interchange.mojo.
serialize_numeric_sparse¶
def serialize_numeric_sparse[D: NumericDomain](poly: NumericSparsePoly[D], mut budget: Budget) raises PolyError -> String
Serialize sparse numerical coefficients and monomial-order metadata.
Parameters.
D: The numerical domain.
Arguments.
poly: The canonical numerical sparse polynomial.budget: The shared work allowance.
Returns. Version-one text preserving every scalar's format and enclosure.
Raises.
PolyError: DOMAIN for invalid input, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/numeric_interchange.mojo.
deserialize_numeric_sparse¶
def deserialize_numeric_sparse[D: NumericDomain](text: String, mut budget: Budget) raises PolyError -> NumericSparsePoly[D]
Read canonical numerical sparse interchange without arithmetic or rounding.
Parameters.
D: The expected numerical domain.
Arguments.
text: Canonical version-one polynomial text.budget: The shared work allowance.
Returns. The exact stored scalar formats, enclosures and monomial order.
Raises.
PolyError: ENCODING for malformed text, DOMAIN for nonfinite coefficients, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/numeric_interchange.mojo.
Rational functions¶
For \(f(x)=x^2/(x-1)\), partial_fractions gives \(x+1+1/(x-1)\). Its value at
\(2\) is \(4\), and its residue at the pole \(1\) is \(1\):
"""Decompose a rational function and compute its residue at a pole."""
from std.testing import assert_equal, assert_true
from apn_mojo import Rational
from polynomials import Budget, QQ, NoContext, PolynomialRing, RationalFunction, partial_fractions, check_partial_fractions, rational_evaluate, rational_residue
def main() raises:
var work = Budget()
var ring = PolynomialRing[QQ].create(["x"], NoContext(), work)
var normalized = RationalFunction.normalize(ring.parse("x^2", work), ring.parse("x - 1", work), work)
var parts = partial_fractions(normalized[0], 0, work)
assert_true(check_partial_fractions(normalized[0], 0, parts, work))
var point: List[Tuple[Int64, QQ]] = [(Int64(0), QQ(Rational(2)))]
var value = rational_evaluate(normalized[0], point, work)
var residue = rational_residue(normalized[0], 0, QQ(Rational(1)), work)
assert_equal(value.value, Rational(4))
assert_equal(residue.value, Rational(1))
assert_equal(len(parts.terms), 1)
print("Value at 2:", value.value)
print("Residue at 1:", residue.value)
Run from the repository root pixi run mojo run -I build docs/examples/tutorial_rational.mojo
Output
Value at 2: 4
Residue at 1: 1
rational_evaluate¶
def rational_evaluate(f: RationalFunction, assignments: List[Tuple[Int64, QQ]], mut budget: Budget) raises PolyError -> QQ
Evaluate a rational function at a nonpole exact assignment.
Arguments.
f: The rational function.assignments: Values for all occurring variables.budget: The shared work allowance.
Returns. The exact rational value after removing common factors.
Raises.
PolyError: DOMAIN for poles or invalid assignments, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/rational_tools.mojo.
rational_derivative¶
def rational_derivative(f: RationalFunction, variable: Int64, mut budget: Budget) raises PolyError -> RationalFunction
Differentiate a rational function by the quotient rule.
Arguments.
f: The rational function.variable: The differentiation variable.budget: The shared work allowance.
Returns. The normalized exact derivative.
Raises.
PolyError: DOMAIN for malformed input, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/rational_tools.mojo.
rational_substitute¶
def rational_substitute(f: RationalFunction, assignments: List[Tuple[Int64, SparsePoly[QQ]]], mut budget: Budget) raises PolyError -> RationalFunction
Substitute polynomials simultaneously into a rational function.
Arguments.
f: The rational function.assignments: Distinct variables and compatible polynomial replacements.budget: The shared work allowance.
Returns. The normalized substituted fraction.
Raises.
PolyError: DOMAIN for invalid data or an identically zero substituted denominator, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/rational_tools.mojo.
rational_compose¶
def rational_compose(outer: RationalFunction, inner: RationalFunction, variable: Int64, mut budget: Budget) raises PolyError -> RationalFunction
Compose univariate rational functions through homogeneous evaluation.
Arguments.
outer: The outer rational function.inner: The replacement rational function in the same order and variable.variable: The sole polynomial variable.budget: The shared work allowance.
Returns. The normalized composition.
Raises.
PolyError: DOMAIN for incompatible inputs or an identically zero denominator, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/rational_tools.mojo.
PartialFractionTerm¶
@fieldwise_init
struct PartialFractionTerm(Copyable, Movable)
A proper numerator divided by a positive power of a pole factor.
Defined in src/polynomials/rational_tools.mojo.
| Field | Type | |
|---|---|---|
numerator |
DensePoly[QQ] |
The numerator of degree less than the base factor. |
factor |
DensePoly[QQ] |
The monic base denominator factor. |
exponent |
Int |
The positive denominator power. |
PartialFractions¶
@fieldwise_init
struct PartialFractions(Copyable, Movable)
An exact polynomial part and a list of proper fraction terms.
Defined in src/polynomials/rational_tools.mojo.
| Field | Type | |
|---|---|---|
polynomial |
DensePoly[QQ] |
The polynomial quotient. |
terms |
List[PartialFractionTerm] |
Nonzero proper terms grouped by deterministic factor order. |
partial_fractions¶
def partial_fractions(f: RationalFunction, variable: Int64, mut budget: Budget) raises PolyError -> PartialFractions
Decompose a univariate rational function over QQ.
Arguments.
f: The rational function.variable: Its sole variable.budget: The shared work allowance.
Returns. A polynomial part and proper terms over irreducible rational factors.
Raises.
PolyError: DOMAIN for invalid inputs, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/rational_tools.mojo.
check_partial_fractions¶
def check_partial_fractions(f: RationalFunction, variable: Int64, decomposition: PartialFractions, mut budget: Budget) raises PolyError -> Bool
Check a partial-fraction identity without repeating factorization.
Arguments.
f: The original rational function.variable: Its sole variable.decomposition: The proposed polynomial and proper terms.budget: The shared work allowance.
Returns. Whether all terms are proper and recomposition equals f; irreducibility is not asserted by this identity check.
Raises.
PolyError: DOMAIN for malformed inputs, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/rational_tools.mojo.
rational_poles¶
def rational_poles(f: RationalFunction, variable: Int64, mut budget: Budget) raises PolyError -> Factorization[QQ]
Represent all complex poles by exact rational factors and multiplicities.
Arguments.
f: The rational function.variable: Its sole variable.budget: The shared work allowance.
Returns. The factorization of its reduced denominator; each factor represents all its complex roots.
Raises.
PolyError: DOMAIN for invalid input, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/rational_tools.mojo.
LaurentExpansion¶
@fieldwise_init
struct LaurentExpansion(Copyable, Movable)
Consecutive exact coefficients in powers of x-minus-center.
Defined in src/polynomials/rational_tools.mojo.
| Field | Type | |
|---|---|---|
variable |
Int64 |
The polynomial variable. |
center |
QQ |
The rational expansion center. |
valuation |
Int |
The lowest exponent; zero for the identically zero function. |
coefficients |
List[QQ] |
Coefficients beginning at the valuation, with a formal unknown tail. |
laurent_expansion¶
def laurent_expansion(f: RationalFunction, variable: Int64, center: QQ, terms: Int, mut budget: Budget) raises PolyError -> LaurentExpansion
Expand a rational function formally at an exact rational center.
Arguments.
f: The rational function.variable: Its sole variable.center: The expansion center, possibly a pole.terms: The nonnegative number of coefficients beginning at the valuation.budget: The shared work allowance.
Returns. The exact Laurent coefficients and their lowest exponent.
Raises.
PolyError: DOMAIN for invalid inputs, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/rational_tools.mojo.
check_laurent_expansion¶
def check_laurent_expansion(f: RationalFunction, expansion: LaurentExpansion, mut budget: Budget) raises PolyError -> Bool
Check Laurent coefficients by a truncated multiplication identity.
Arguments.
f: The rational function.expansion: The proposed local expansion.budget: The shared work allowance.
Returns. Whether the valuation and every supplied coefficient are correct.
Raises.
PolyError: DOMAIN for malformed input, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/rational_tools.mojo.
rational_residue¶
def rational_residue(f: RationalFunction, variable: Int64, center: QQ, mut budget: Budget) raises PolyError -> QQ
Extract the coefficient of (x-center)^(-1) exactly.
Arguments.
f: The rational function.variable: Its sole variable.center: The exact rational expansion center.budget: The shared work allowance.
Returns. The rational residue, including zero at regular points.
Raises.
PolyError: DOMAIN for invalid inputs, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/rational_tools.mojo.
Alternative bases¶
The polynomial \(x^2\) has Bernstein coefficients \(0,0,1\) at degree two and equals \(\tfrac12 T_0(x)+\tfrac12 T_2(x)\) in the Chebyshev basis. The example also evaluates the Bernstein form at \(1/2\):
"""Express a quadratic in Bernstein and Chebyshev bases."""
from std.testing import assert_equal
from apn_mojo import Rational
from polynomials import Budget, QQ, NoContext, PolynomialRing, DensePoly, BasisPolynomial
def main() raises:
var work = Budget()
var ring = PolynomialRing[QQ].create(["x"], NoContext(), work)
var polynomial = DensePoly[QQ].from_sparse(ring.parse("x^2", work), work, variable=Int64(0))
var bernstein = BasisPolynomial[QQ].bernstein(polynomial, 2, work)
var chebyshev = BasisPolynomial[QQ].chebyshev(polynomial, work)
assert_equal(bernstein.to_polynomial(work), polynomial)
assert_equal(chebyshev.to_polynomial(work), polynomial)
assert_equal(bernstein.coefficients[0].value, Rational(0))
assert_equal(bernstein.coefficients[1].value, Rational(0))
assert_equal(bernstein.coefficients[2].value, Rational(1))
assert_equal(chebyshev.coefficients[0].value, Rational(1, 2))
assert_equal(chebyshev.coefficients[2].value, Rational(1, 2))
var value = bernstein.evaluate(QQ(Rational(1, 2)), work)
assert_equal(value.value, Rational(1, 4))
print("Bernstein coefficients:", bernstein.coefficients[0].value, bernstein.coefficients[1].value, bernstein.coefficients[2].value)
print("Value at 1/2:", value.value)
Run from the repository root pixi run mojo run -I build docs/examples/tutorial_bases.mojo
Output
Bernstein coefficients: 0 0 1
Value at 1/2: 1/4
BasisPolynomial¶
@fieldwise_init
struct BasisPolynomial[C: CoefficientField](Copyable, Movable)
Represent a polynomial in one of three structured bases.
Parameters.
C: The exact coefficient field.
Defined in src/polynomials/bases.mojo.
| Field | Type | |
|---|---|---|
variable |
Int64 |
The polynomial variable. |
kind |
UInt8 |
The basis tag. |
ring |
Self.C.Context |
The exact coefficient field context. |
coefficients |
List[Self.C] |
Ascending basis coefficients, retaining representation degree. |
nodes |
List[Self.C] |
The Newton nodes; empty for the other bases. |
BasisPolynomial.NEWTON¶
comptime NEWTON = UInt8(0)
Products of successive x-minus-node factors.
BasisPolynomial.CHEBYSHEV¶
comptime CHEBYSHEV = UInt8(1)
First-kind Chebyshev polynomials with T0=1 and T1=x.
BasisPolynomial.BERNSTEIN¶
comptime BERNSTEIN = UInt8(2)
Bernstein polynomials of the retained degree on [0,1].
BasisPolynomial.newton¶
@staticmethod
def newton(poly: DensePoly[Self.C], nodes: List[Self.C], mut budget: Budget) raises PolyError -> Self
Convert monomial coefficients to a Newton basis.
Arguments.
poly: The monomial polynomial.nodes: Newton nodes, with count at least the polynomial degree; repetitions are allowed.budget: The shared work allowance.
Returns. The exact, rounded or enclosing basis representation.
Raises.
PolyError: DOMAIN for invalid data or noninvertible conversion factors, LIMIT or CAPACITY on work limits.
BasisPolynomial.chebyshev¶
@staticmethod
def chebyshev(poly: DensePoly[Self.C], mut budget: Budget) raises PolyError -> Self
Convert monomial coefficients to a Chebyshev basis.
Arguments.
poly: The monomial polynomial.budget: The shared work allowance.
Returns. The exact, rounded or enclosing basis representation.
Raises.
PolyError: DOMAIN for invalid data or noninvertible conversion factors, LIMIT or CAPACITY on work limits.
BasisPolynomial.bernstein¶
@staticmethod
def bernstein(poly: DensePoly[Self.C], degree: Int, mut budget: Budget) raises PolyError -> Self
Convert monomial coefficients to a retained Bernstein degree.
Arguments.
poly: The monomial polynomial.degree: The retained degree, at least the polynomial degree and zero.budget: The shared work allowance.
Returns. The exact, rounded or enclosing basis representation.
Raises.
PolyError: DOMAIN for invalid data or noninvertible conversion factors, LIMIT or CAPACITY on work limits.
BasisPolynomial.to_polynomial¶
def to_polynomial(self, mut budget: Budget) raises PolyError -> DensePoly[Self.C]
Expand the basis into monomial coefficients.
Arguments.
budget: The shared work allowance.
Returns. The exact, rounded or enclosing monomial polynomial.
Raises.
PolyError: DOMAIN for invalid representations, LIMIT or CAPACITY on work limits.
BasisPolynomial.evaluate¶
def evaluate(self, point: Self.C, mut budget: Budget) raises PolyError -> Self.C
Evaluate using nested Newton, Clenshaw or de Casteljau arithmetic.
Arguments.
point: The evaluation point or subdivision parameter.budget: The shared work allowance.
Returns. The exact value, rounded value or uniform enclosure.
Raises.
PolyError: DOMAIN for invalid representations or incompatible points, LIMIT or CAPACITY on work limits.
BasisPolynomial.subdivide¶
def subdivide(self, point: Self.C, mut budget: Budget) raises PolyError -> Tuple[Self, Self]
Subdivide a Bernstein representation at an explicit parameter.
Arguments.
point: The evaluation point or subdivision parameter.budget: The shared work allowance.
Returns. Representations of p(pointx) and p(point+(1-point)x), retaining degree.
Raises.
PolyError: DOMAIN for invalid representations or incompatible points, LIMIT or CAPACITY on work limits.
NumericBasisPolynomial¶
@fieldwise_init
struct NumericBasisPolynomial[D: NumericDomain](Copyable, Movable)
Represent a polynomial in one of three structured bases.
Parameters.
D: The numerical domain.
Defined in src/polynomials/numeric_bases.mojo.
| Field | Type | |
|---|---|---|
variable |
Int64 |
The polynomial variable. |
kind |
UInt8 |
The basis tag. |
coefficients |
List[Self.D.Scalar] |
Ascending basis coefficients, retaining representation degree. |
nodes |
List[Self.D.Scalar] |
The Newton nodes; empty for the other bases. |
NumericBasisPolynomial.NEWTON¶
comptime NEWTON = UInt8(0)
Products of successive x-minus-node factors.
NumericBasisPolynomial.CHEBYSHEV¶
comptime CHEBYSHEV = UInt8(1)
First-kind Chebyshev polynomials with T0=1 and T1=x.
NumericBasisPolynomial.BERNSTEIN¶
comptime BERNSTEIN = UInt8(2)
Bernstein polynomials of the retained degree on [0,1].
NumericBasisPolynomial.newton¶
@staticmethod
def newton(poly: NumericDensePoly[Self.D], nodes: List[Self.D.Scalar], context: Self.D.Context, mut budget: Budget) raises PolyError -> Self
Convert monomial coefficients to a Newton basis.
Arguments.
poly: The monomial polynomial.nodes: Newton nodes, with count at least the polynomial degree; repetitions are allowed.context: Explicit numerical arithmetic settings.budget: The shared work allowance.
Returns. The exact, rounded or enclosing basis representation.
Raises.
PolyError: DOMAIN for invalid data or noninvertible conversion factors, LIMIT or CAPACITY on work limits.
NumericBasisPolynomial.chebyshev¶
@staticmethod
def chebyshev(poly: NumericDensePoly[Self.D], context: Self.D.Context, mut budget: Budget) raises PolyError -> Self
Convert monomial coefficients to a Chebyshev basis.
Arguments.
poly: The monomial polynomial.context: Explicit numerical arithmetic settings.budget: The shared work allowance.
Returns. The exact, rounded or enclosing basis representation.
Raises.
PolyError: DOMAIN for invalid data or noninvertible conversion factors, LIMIT or CAPACITY on work limits.
NumericBasisPolynomial.bernstein¶
@staticmethod
def bernstein(poly: NumericDensePoly[Self.D], degree: Int, context: Self.D.Context, mut budget: Budget) raises PolyError -> Self
Convert monomial coefficients to a retained Bernstein degree.
Arguments.
poly: The monomial polynomial.degree: The retained degree, at least the polynomial degree and zero.context: Explicit numerical arithmetic settings.budget: The shared work allowance.
Returns. The exact, rounded or enclosing basis representation.
Raises.
PolyError: DOMAIN for invalid data or noninvertible conversion factors, LIMIT or CAPACITY on work limits.
NumericBasisPolynomial.to_polynomial¶
def to_polynomial(self, context: Self.D.Context, mut budget: Budget) raises PolyError -> NumericDensePoly[Self.D]
Expand the basis into monomial coefficients.
Arguments.
context: Explicit numerical arithmetic settings.budget: The shared work allowance.
Returns. The exact, rounded or enclosing monomial polynomial.
Raises.
PolyError: DOMAIN for invalid representations, LIMIT or CAPACITY on work limits.
NumericBasisPolynomial.evaluate¶
def evaluate(self, point: Self.D.Scalar, context: Self.D.Context, mut budget: Budget) raises PolyError -> Self.D.Scalar
Evaluate using nested Newton, Clenshaw or de Casteljau arithmetic.
Arguments.
point: The evaluation point or subdivision parameter.context: Explicit numerical arithmetic settings.budget: The shared work allowance.
Returns. The exact value, rounded value or uniform enclosure.
Raises.
PolyError: DOMAIN for invalid representations or incompatible points, LIMIT or CAPACITY on work limits.
NumericBasisPolynomial.subdivide¶
def subdivide(self, point: Self.D.Scalar, context: Self.D.Context, mut budget: Budget) raises PolyError -> Tuple[Self, Self]
Subdivide a Bernstein representation at an explicit parameter.
Arguments.
point: The evaluation point or subdivision parameter.context: Explicit numerical arithmetic settings.budget: The shared work allowance.
Returns. Representations of p(pointx) and p(point+(1-point)x), retaining degree.
Raises.
PolyError: DOMAIN for invalid representations or incompatible points, LIMIT or CAPACITY on work limits.
Formal series¶
Modulo \(x^4\), the reciprocal of \(1-x\) is \(1+x+x^2+x^3\):
"""Invert a formal series modulo x to the fourth power."""
from std.testing import assert_equal
from polynomials import Budget, QQ, NoContext, PolynomialRing, DensePoly, TruncatedSeries
def main() raises:
var work = Budget()
var ring = PolynomialRing[QQ].create(["x"], NoContext(), work)
var polynomial = DensePoly[QQ].from_sparse(ring.parse("1 - x", work), work, variable=Int64(0))
var series = TruncatedSeries[QQ].from_polynomial(polynomial, 4, work)
var reciprocal = series.inverse(work)
var expected = DensePoly[QQ].from_sparse(ring.parse("1 + x + x^2 + x^3", work), work, variable=Int64(0))
assert_equal(reciprocal.polynomial, expected)
var product = series.mul(reciprocal, work)
var one = DensePoly[QQ].from_sparse(ring.parse("1", work), work, variable=Int64(0))
assert_equal(product.polynomial, one)
print("Reciprocal through x^3:", reciprocal.polynomial == expected)
print("Product modulo x^4 is 1:", product.polynomial == one)
Run from the repository root pixi run mojo run -I build docs/examples/tutorial_series.mojo
Output
Reciprocal through x^3: True
Product modulo x^4 is 1: True
TruncatedSeries¶
@fieldwise_init
struct TruncatedSeries[C: CoefficientField](Copyable, Movable)
Store coefficients known modulo an explicit power of x.
Parameters.
C: The exact coefficient field.
Defined in src/polynomials/series.mojo.
| Field | Type | |
|---|---|---|
polynomial |
DensePoly[Self.C] |
The canonical polynomial containing known coefficients. |
order |
Int |
The nonnegative exponent of the unknown remainder O(x^order). |
TruncatedSeries.from_polynomial¶
@staticmethod
def from_polynomial(poly: DensePoly[Self.C], order: Int, mut budget: Budget) raises PolyError -> Self
Truncate a polynomial to a specified formal precision.
Arguments.
poly: The polynomial supplying known coefficients.order: The nonnegative number of known coefficients.budget: The shared work allowance.
Returns. A formal series with zeros filled from the polynomial below the order.
Raises.
PolyError: DOMAIN for invalid inputs, LIMIT or CAPACITY on work limits.
TruncatedSeries.truncate¶
def truncate(self, order: Int, mut budget: Budget) raises PolyError -> Self
Reduce precision without inventing unknown coefficients.
Arguments.
order: The requested lower precision.budget: The shared work allowance.
Returns. A series at the requested order.
Raises.
PolyError: DOMAIN for incompatible inputs or unavailable divisions, LIMIT or CAPACITY on work limits.
TruncatedSeries.add¶
def add(self, other: Self, mut budget: Budget) raises PolyError -> Self
Add two series at equal precision.
Arguments.
other: The second series in the same variable, domain and order.budget: The shared work allowance.
Returns. The truncated sum.
Raises.
PolyError: DOMAIN for incompatible inputs or unavailable divisions, LIMIT or CAPACITY on work limits.
TruncatedSeries.sub¶
def sub(self, other: Self, mut budget: Budget) raises PolyError -> Self
Subtract two series at equal precision.
Arguments.
other: The second series in the same variable, domain and order.budget: The shared work allowance.
Returns. The truncated difference.
Raises.
PolyError: DOMAIN for incompatible inputs or unavailable divisions, LIMIT or CAPACITY on work limits.
TruncatedSeries.mul¶
def mul(self, other: Self, mut budget: Budget) raises PolyError -> Self
Multiply modulo the common truncation order.
Arguments.
other: The second series in the same variable, domain and order.budget: The shared work allowance.
Returns. The truncated product.
Raises.
PolyError: DOMAIN for incompatible inputs or unavailable divisions, LIMIT or CAPACITY on work limits.
TruncatedSeries.divide¶
def divide(self, other: Self, mut budget: Budget) raises PolyError -> Self
Divide by a series with invertible constant coefficient.
Arguments.
other: The second series in the same variable, domain and order.budget: The shared work allowance.
Returns. The quotient modulo the common order.
Raises.
PolyError: DOMAIN for incompatible inputs or unavailable divisions, LIMIT or CAPACITY on work limits.
TruncatedSeries.inverse¶
def inverse(self, mut budget: Budget) raises PolyError -> Self
Invert a series with invertible constant coefficient.
Arguments.
budget: The shared work allowance.
Returns. The multiplicative inverse at the original precision.
Raises.
PolyError: DOMAIN for incompatible inputs or unavailable divisions, LIMIT or CAPACITY on work limits.
TruncatedSeries.compose¶
def compose(self, other: Self, mut budget: Budget) raises PolyError -> Self
Compose with a series whose constant is exactly zero.
Arguments.
other: The second series in the same variable, domain and order.budget: The shared work allowance.
Returns. The composition at the common precision.
Raises.
PolyError: DOMAIN for incompatible inputs or unavailable divisions, LIMIT or CAPACITY on work limits.
TruncatedSeries.derivative¶
def derivative(self, mut budget: Budget) raises PolyError -> Self
Differentiate and decrease known precision by one.
Arguments.
budget: The shared work allowance.
Returns. The formal derivative, with order max(0, order-1).
Raises.
PolyError: DOMAIN for incompatible inputs or unavailable divisions, LIMIT or CAPACITY on work limits.
TruncatedSeries.integrate¶
def integrate(self, mut budget: Budget) raises PolyError -> Self
Integrate with zero constant and increase precision by one.
Arguments.
budget: The shared work allowance.
Returns. The antiderivative when required coefficient divisions exist.
Raises.
PolyError: DOMAIN for incompatible inputs or unavailable divisions, LIMIT or CAPACITY on work limits.
TruncatedSeries.log¶
def log(self, mut budget: Budget) raises PolyError -> Self
Compute a formal logarithm with constant coefficient one.
Arguments.
budget: The shared work allowance.
Returns. The zero-constant logarithm at the original precision.
Raises.
PolyError: DOMAIN for incompatible inputs or unavailable divisions, LIMIT or CAPACITY on work limits.
TruncatedSeries.exp¶
def exp(self, mut budget: Budget) raises PolyError -> Self
Compute a formal exponential with constant coefficient zero.
Arguments.
budget: The shared work allowance.
Returns. The unit-constant exponential at the original precision.
Raises.
PolyError: DOMAIN for incompatible inputs or unavailable divisions, LIMIT or CAPACITY on work limits.
TruncatedSeries.sqrt¶
def sqrt(self, mut budget: Budget) raises PolyError -> Self
Compute a formal square root with constant coefficient one.
Arguments.
budget: The shared work allowance.
Returns. The square root with constant term one at the original precision.
Raises.
PolyError: DOMAIN for another constant term or a field of characteristic two, LIMIT or CAPACITY on work limits.
TruncatedSeries.revert¶
def revert(self, mut budget: Budget) raises PolyError -> Self
Invert composition for zero constant and invertible linear term.
Arguments.
budget: The shared work allowance.
Returns. The reversion at the original precision, requiring order at least two.
Raises.
PolyError: DOMAIN for incompatible inputs or unavailable divisions, LIMIT or CAPACITY on work limits.
NumericSeries¶
@fieldwise_init
struct NumericSeries[D: NumericDomain](Copyable, Movable)
Store coefficients known modulo an explicit power of x.
Parameters.
D: The numerical domain; enclosures describe coefficients, not analytic tails.
Defined in src/polynomials/numeric_series.mojo.
| Field | Type | |
|---|---|---|
polynomial |
NumericDensePoly[Self.D] |
The canonical polynomial containing known coefficients. |
order |
Int |
The nonnegative exponent of the unknown remainder O(x^order). |
NumericSeries.from_polynomial¶
@staticmethod
def from_polynomial(poly: NumericDensePoly[Self.D], order: Int, context: Self.D.Context, mut budget: Budget) raises PolyError -> Self
Truncate a polynomial to a specified formal precision.
Arguments.
poly: The polynomial supplying known coefficients.order: The nonnegative number of known coefficients.context: Explicit numerical arithmetic settings.budget: The shared work allowance.
Returns. A formal series with zeros filled from the polynomial below the order.
Raises.
PolyError: DOMAIN for invalid inputs, LIMIT or CAPACITY on work limits.
NumericSeries.truncate¶
def truncate(self, order: Int, context: Self.D.Context, mut budget: Budget) raises PolyError -> Self
Reduce precision without inventing unknown coefficients.
Arguments.
order: The requested lower precision.context: Explicit rounding or enclosing arithmetic settings.budget: The shared work allowance.
Returns. A series at the requested order.
Raises.
PolyError: DOMAIN for incompatible inputs or unavailable divisions, LIMIT or CAPACITY on work limits.
NumericSeries.add¶
def add(self, other: Self, context: Self.D.Context, mut budget: Budget) raises PolyError -> Self
Add two series at equal precision.
Arguments.
other: The second series in the same variable, domain and order.context: Explicit rounding or enclosing arithmetic settings.budget: The shared work allowance.
Returns. The truncated sum.
Raises.
PolyError: DOMAIN for incompatible inputs or unavailable divisions, LIMIT or CAPACITY on work limits.
NumericSeries.sub¶
def sub(self, other: Self, context: Self.D.Context, mut budget: Budget) raises PolyError -> Self
Subtract two series at equal precision.
Arguments.
other: The second series in the same variable, domain and order.context: Explicit rounding or enclosing arithmetic settings.budget: The shared work allowance.
Returns. The truncated difference.
Raises.
PolyError: DOMAIN for incompatible inputs or unavailable divisions, LIMIT or CAPACITY on work limits.
NumericSeries.mul¶
def mul(self, other: Self, context: Self.D.Context, mut budget: Budget) raises PolyError -> Self
Multiply modulo the common truncation order.
Arguments.
other: The second series in the same variable, domain and order.context: Explicit rounding or enclosing arithmetic settings.budget: The shared work allowance.
Returns. The truncated product.
Raises.
PolyError: DOMAIN for incompatible inputs or unavailable divisions, LIMIT or CAPACITY on work limits.
NumericSeries.divide¶
def divide(self, other: Self, context: Self.D.Context, mut budget: Budget) raises PolyError -> Self
Divide by a series with invertible constant coefficient.
Arguments.
other: The second series in the same variable, domain and order.context: Explicit rounding or enclosing arithmetic settings.budget: The shared work allowance.
Returns. The quotient modulo the common order.
Raises.
PolyError: DOMAIN for incompatible inputs or unavailable divisions, LIMIT or CAPACITY on work limits.
NumericSeries.inverse¶
def inverse(self, context: Self.D.Context, mut budget: Budget) raises PolyError -> Self
Invert a series with invertible constant coefficient.
Arguments.
context: Explicit rounding or enclosing arithmetic settings.budget: The shared work allowance.
Returns. The multiplicative inverse at the original precision.
Raises.
PolyError: DOMAIN for incompatible inputs or unavailable divisions, LIMIT or CAPACITY on work limits.
NumericSeries.compose¶
def compose(self, other: Self, context: Self.D.Context, mut budget: Budget) raises PolyError -> Self
Compose with a series whose constant is exactly zero.
Arguments.
other: The second series in the same variable, domain and order.context: Explicit rounding or enclosing arithmetic settings.budget: The shared work allowance.
Returns. The composition at the common precision.
Raises.
PolyError: DOMAIN for incompatible inputs or unavailable divisions, LIMIT or CAPACITY on work limits.
NumericSeries.derivative¶
def derivative(self, context: Self.D.Context, mut budget: Budget) raises PolyError -> Self
Differentiate and decrease known precision by one.
Arguments.
context: Explicit rounding or enclosing arithmetic settings.budget: The shared work allowance.
Returns. The formal derivative, with order max(0, order-1).
Raises.
PolyError: DOMAIN for incompatible inputs or unavailable divisions, LIMIT or CAPACITY on work limits.
NumericSeries.integrate¶
def integrate(self, context: Self.D.Context, mut budget: Budget) raises PolyError -> Self
Integrate with zero constant and increase precision by one.
Arguments.
context: Explicit rounding or enclosing arithmetic settings.budget: The shared work allowance.
Returns. The antiderivative when required coefficient divisions exist.
Raises.
PolyError: DOMAIN for incompatible inputs or unavailable divisions, LIMIT or CAPACITY on work limits.
NumericSeries.log¶
def log(self, context: Self.D.Context, mut budget: Budget) raises PolyError -> Self
Compute a formal logarithm with constant coefficient one.
Arguments.
context: Explicit rounding or enclosing arithmetic settings.budget: The shared work allowance.
Returns. The zero-constant logarithm at the original precision.
Raises.
PolyError: DOMAIN for incompatible inputs or unavailable divisions, LIMIT or CAPACITY on work limits.
NumericSeries.exp¶
def exp(self, context: Self.D.Context, mut budget: Budget) raises PolyError -> Self
Compute a formal exponential with constant coefficient zero.
Arguments.
context: Explicit rounding or enclosing arithmetic settings.budget: The shared work allowance.
Returns. The unit-constant exponential at the original precision.
Raises.
PolyError: DOMAIN for incompatible inputs or unavailable divisions, LIMIT or CAPACITY on work limits.
NumericSeries.revert¶
def revert(self, context: Self.D.Context, mut budget: Budget) raises PolyError -> Self
Invert composition for zero constant and invertible linear term.
Arguments.
context: Explicit rounding or enclosing arithmetic settings.budget: The shared work allowance.
Returns. The reversion at the original precision, requiring order at least two.
Raises.
PolyError: DOMAIN for incompatible inputs or unavailable divisions, LIMIT or CAPACITY on work limits.
Numerical workflows¶
refine_real_roots_exact¶
def refine_real_roots_exact[C: CoefficientRing](poly: DensePoly[C], previous: DescartesRootResult, previous_options: NumericOptions, options: NumericOptions, mut budget: Budget, *, complete_only: Bool = False, trusted: Bool = False) raises PolyError -> DescartesRootResult
Tighten a validated Descartes result to new widths.
Parameters.
C: ZZ or QQ.
Arguments.
poly: The original exact polynomial.previous: The prior result; its certificate is checked first.previous_options: Options describing the previous result's flags.options: New targets and subdivision allowance.budget: The shared work allowance.complete_only: Raise unless every new requested guarantee succeeds.trusted: Skip checking previous, for evidence this library produced or already checked; refinement keeps a valid certificate valid.
Returns. The same leaves with narrower brackets; an incomplete previous result restarts under the new options.
Raises.
PolyError: DOMAIN for invalid prior evidence, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/numeric_refine.mojo.
refine_real_roots_numeric¶
def refine_real_roots_numeric[D: NumericDomain](poly: NumericDensePoly[D], previous: RealRootResult, previous_options: NumericOptions, options: NumericOptions, mut budget: Budget, *, complete_only: Bool = False) raises PolyError -> RealRootResult
Resume real refinement after validating the previous root evidence.
Parameters.
D: The numerical coefficient domain.
Arguments.
poly: The original polynomial or coefficient family.previous: The prior result; certified satisfactory regions are retained.previous_options: Options describing the previous result's flags.options: New targets and an additional subdivision allowance.budget: The shared work allowance.complete_only: Raise unless every new requested guarantee succeeds.
Returns. A refined cover; empty inconclusive results restart, and unresolved real cells merge before retrying.
Raises.
PolyError: DOMAIN for invalid prior evidence, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/numeric_refine.mojo.
refine_complex_roots_exact¶
def refine_complex_roots_exact[C: CoefficientRing](poly: DensePoly[C], previous: ComplexRootResult, previous_options: NumericOptions, options: NumericOptions, mut budget: Budget, *, complete_only: Bool = False) raises PolyError -> ComplexRootResult
Resume complex refinement after validating the previous root evidence.
Parameters.
C: ZZ, QQ, or QQi.
Arguments.
poly: The original polynomial or coefficient family.previous: The prior result; certified satisfactory regions are retained.previous_options: Options describing the previous result's flags.options: New targets and an additional subdivision allowance.budget: The shared work allowance.complete_only: Raise unless every new requested guarantee succeeds.
Returns. A refined cover; empty inconclusive results restart, and unresolved real cells merge before retrying.
Raises.
PolyError: DOMAIN for invalid prior evidence, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/numeric_refine.mojo.
refine_complex_roots_numeric¶
def refine_complex_roots_numeric[D: NumericDomain](poly: NumericDensePoly[D], previous: ComplexRootResult, previous_options: NumericOptions, options: NumericOptions, mut budget: Budget, *, complete_only: Bool = False) raises PolyError -> ComplexRootResult
Resume complex refinement after validating the previous root evidence.
Parameters.
D: The numerical coefficient domain.
Arguments.
poly: The original polynomial or coefficient family.previous: The prior result; certified satisfactory regions are retained.previous_options: Options describing the previous result's flags.options: New targets and an additional subdivision allowance.budget: The shared work allowance.complete_only: Raise unless every new requested guarantee succeeds.
Returns. A refined cover; empty inconclusive results restart, and unresolved real cells merge before retrying.
Raises.
PolyError: DOMAIN for invalid prior evidence, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/numeric_refine.mojo.
RootMultiplicityCertificate¶
@fieldwise_init
struct RootMultiplicityCertificate(Copyable, Movable)
Prove the multiplicity of every isolated real root through squarefree blocks.
Defined in src/polynomials/numeric_multiplicity.mojo.
| Field | Type | |
|---|---|---|
decomposition |
SquarefreeDecomposition[QQ] |
A product decomposition of the exact polynomial into multiplicity blocks. |
blocks |
List[Int] |
For each root in increasing order, the index of the block that vanishes there. |
multiplicities |
List[Int] |
For each root in increasing order, its multiplicity in the polynomial. |
real_root_multiplicities¶
def real_root_multiplicities[C: CoefficientRing](poly: DensePoly[C], roots: DescartesRootResult, options: NumericOptions, mut budget: Budget) raises PolyError -> RootMultiplicityCertificate
Attach exact multiplicities to a checked complete real-root result.
Parameters.
C: ZZ or QQ.
Arguments.
poly: The exact polynomial.roots: A complete Descartes result for poly.options: The options describing that result.budget: The shared work allowance.
Returns. The squarefree decomposition, and for each root its block and multiplicity.
Raises.
PolyError: DOMAIN for invalid or incomplete results, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/numeric_multiplicity.mojo.
check_real_root_multiplicities¶
def check_real_root_multiplicities[C: CoefficientRing](poly: DensePoly[C], roots: DescartesRootResult, options: NumericOptions, certificate: RootMultiplicityCertificate, mut budget: Budget) raises PolyError -> Bool
Check root multiplicities without performing squarefree decomposition or gcd.
Parameters.
C: ZZ or QQ.
Arguments.
poly: The exact polynomial.roots: The claimed complete Descartes result.options: The options describing that result.certificate: The decomposition and per-root blocks.budget: The shared work allowance.
Returns. Whether every per-root multiplicity is proved exactly.
Raises.
PolyError: DOMAIN for malformed polynomial data, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/numeric_multiplicity.mojo.
RootDiagnostics¶
@fieldwise_init
struct RootDiagnostics(Copyable, Movable)
Rational residual and local sensitivity bounds at a specified point.
Defined in src/polynomials/numeric_diagnostics.mojo.
| Field | Type | |
|---|---|---|
residual |
NumericBox |
An enclosure of p(z), uniformly over any coefficient family. |
derivative |
NumericBox |
An enclosure of p'(z). |
backward_error_low |
QQ |
Lower bound on the absolute complex coefficient infinity-norm backward error. |
backward_error_high |
QQ |
Upper bound on that backward error, |
newton_correction_upper |
Optional[QQ] |
Upper bound for |
coefficient_sensitivity_upper |
Optional[QQ] |
Upper bound for sum |
PolishedRootResult¶
@fieldwise_init
struct PolishedRootResult(Copyable, Movable)
A numerical Newton candidate and an optional independently checkable root witness.
Defined in src/polynomials/numeric_diagnostics.mojo.
| Field | Type | |
|---|---|---|
candidate |
Complex |
The rounded advisory candidate; its closeness alone is not a root proof. |
iterations |
Int |
The number of completed Newton updates. |
region |
Optional[ComplexRootRegion] |
A rectangle with a contour proof of exactly one root, when available. |
outcome |
NumericOutcome |
SUCCESS only when one root is validated and the requested width is met. |
root_diagnostics_exact¶
def root_diagnostics_exact[C: CoefficientRing](poly: DensePoly[C], point: NumericBox, mut budget: Budget) raises PolyError -> RootDiagnostics
Bound residuals, coefficient backward error and local derivative sensitivity.
Parameters.
C: ZZ, QQ, or QQi.
Arguments.
poly: The input polynomial.point: The exact point rectangle where diagnostics are requested.budget: The shared work allowance.
Returns. Uniform rational bounds; local sensitivity becomes root conditioning only at a root.
Raises.
PolyError: DOMAIN for invalid inputs, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/numeric_diagnostics.mojo.
check_root_diagnostics_exact¶
def check_root_diagnostics_exact[C: CoefficientRing](poly: DensePoly[C], point: NumericBox, result: RootDiagnostics, mut budget: Budget) raises PolyError -> Bool
Check exact residual and local sensitivity bounds.
Parameters.
C: ZZ, QQ, or QQi.
Arguments.
poly: The input polynomial.point: The exact point rectangle where diagnostics are requested.result: The claimed residual and local bounds.budget: The shared work allowance.
Returns. Whether the supplied bounds or root witness are valid.
Raises.
PolyError: DOMAIN for invalid inputs, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/numeric_diagnostics.mojo.
polish_root_exact¶
def polish_root_exact[C: CoefficientRing](poly: DensePoly[C], seed: Complex, radius: QQ, iterations: Int, context: ComplexContext, options: NumericOptions, mut budget: Budget) raises PolyError -> PolishedRootResult
Polish a Newton candidate and attempt an independent one-root contour proof.
Parameters.
C: ZZ, QQ, or QQi.
Arguments.
poly: The input polynomial.seed: The advisory complex starting point.radius: A positive exact radius for the final validation rectangle.iterations: The nonnegative Newton update limit.context: Explicit candidate arithmetic settings.options: Contour precision, subdivision and accuracy limits.budget: The shared work allowance.
Returns. An advisory candidate and a root certificate only if validation succeeds.
Raises.
PolyError: DOMAIN for invalid inputs, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/numeric_diagnostics.mojo.
check_polished_root_exact¶
def check_polished_root_exact[C: CoefficientRing](poly: DensePoly[C], result: PolishedRootResult, options: NumericOptions, mut budget: Budget) raises PolyError -> Bool
Check the one-root contour and candidate containment independently.
Parameters.
C: ZZ, QQ, or QQi.
Arguments.
poly: The input polynomial.result: The proposed polished root and local witness.options: The requested contour precision and accuracy.budget: The shared work allowance.
Returns. Whether the supplied bounds or root witness are valid.
Raises.
PolyError: DOMAIN for invalid inputs, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/numeric_diagnostics.mojo.
root_diagnostics_numeric¶
def root_diagnostics_numeric[D: NumericDomain](poly: NumericDensePoly[D], point: NumericBox, mut budget: Budget) raises PolyError -> RootDiagnostics
Bound residuals, coefficient backward error and local derivative sensitivity.
Parameters.
D: The numerical coefficient domain.
Arguments.
poly: The input polynomial or coefficient family.point: The exact point rectangle where diagnostics are requested.budget: The shared work allowance.
Returns. Uniform rational bounds; local sensitivity becomes root conditioning only at a root.
Raises.
PolyError: DOMAIN for invalid inputs, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/numeric_diagnostics.mojo.
check_root_diagnostics_numeric¶
def check_root_diagnostics_numeric[D: NumericDomain](poly: NumericDensePoly[D], point: NumericBox, result: RootDiagnostics, mut budget: Budget) raises PolyError -> Bool
Check exact residual and local sensitivity bounds.
Parameters.
D: The numerical coefficient domain.
Arguments.
poly: The input polynomial or coefficient family.point: The exact point rectangle where diagnostics are requested.result: The claimed residual and local bounds.budget: The shared work allowance.
Returns. Whether the supplied bounds or root witness are valid.
Raises.
PolyError: DOMAIN for invalid inputs, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/numeric_diagnostics.mojo.
polish_root_numeric¶
def polish_root_numeric[D: NumericDomain](poly: NumericDensePoly[D], seed: Complex, radius: QQ, iterations: Int, context: ComplexContext, options: NumericOptions, mut budget: Budget) raises PolyError -> PolishedRootResult
Polish a Newton candidate and attempt an independent one-root contour proof.
Parameters.
D: The numerical coefficient domain.
Arguments.
poly: The input polynomial or coefficient family.seed: The advisory complex starting point.radius: A positive exact radius for the final validation rectangle.iterations: The nonnegative Newton update limit.context: Explicit candidate arithmetic settings.options: Contour precision, subdivision and accuracy limits.budget: The shared work allowance.
Returns. An advisory candidate and a root certificate only if validation succeeds.
Raises.
PolyError: DOMAIN for invalid inputs, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/numeric_diagnostics.mojo.
check_polished_root_numeric¶
def check_polished_root_numeric[D: NumericDomain](poly: NumericDensePoly[D], result: PolishedRootResult, options: NumericOptions, mut budget: Budget) raises PolyError -> Bool
Check the one-root contour and candidate containment independently.
Parameters.
D: The numerical coefficient domain.
Arguments.
poly: The input polynomial or coefficient family.result: The proposed polished root and local witness.options: The requested contour precision and accuracy.budget: The shared work allowance.
Returns. Whether the supplied bounds or root witness are valid.
Raises.
PolyError: DOMAIN for invalid inputs, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/numeric_diagnostics.mojo.
NumericDivisionStep¶
@fieldwise_init
struct NumericDivisionStep(Copyable, Movable)
One enclosing leading-term elimination in descending quotient order.
Defined in src/polynomials/numeric_division.mojo.
| Field | Type | |
|---|---|---|
quotient |
NumericBox |
Enclosure of the exact quotient coefficient at this step. |
tail |
List[NumericBox] |
Updated lower coefficients, ascending within the shifted divisor support. |
NumericDivisionResult¶
@fieldwise_init
struct NumericDivisionResult[D: NumericDomain](Copyable, Movable)
Numerical quotient and remainder with explicit residual or family evidence.
Parameters.
D: The numerical coefficient domain.
Defined in src/polynomials/numeric_division.mojo.
| Field | Type | |
|---|---|---|
quotient |
NumericDensePoly[Self.D] |
The rounded quotient or coefficient enclosures of all exact quotients. |
remainder |
NumericDensePoly[Self.D] |
The rounded remainder or enclosure, with degree below the divisor. |
residual |
List[NumericBox] |
Exact rectangular coefficient bounds for f-q*g-r, including high-degree rounding residuals. |
steps |
List[NumericDivisionStep] |
Local interval eliminations for ball domains; empty for rounded point domains. |
uniform |
Bool |
True only when q and r enclose exact Euclidean division for every input pair. |
numeric_divmod¶
def numeric_divmod[D: NumericDomain](f: NumericDensePoly[D], g: NumericDensePoly[D], context: D.Context, mut budget: Budget) raises PolyError -> NumericDivisionResult[D]
Divide numerical polynomials with a uniformly nonzero leading divisor.
Parameters.
D: Float, Complex, Ball or ComplexBall domain.
Arguments.
f: The dividend polynomial or coefficient family.g: The divisor in the same variable, with leading enclosure excluding zero.context: Explicit rounding or enclosing arithmetic settings.budget: The shared work allowance.
Returns. Rounded point q/r plus a rigorous residual, or enclosures of exact family q/r with elimination witnesses.
Raises.
PolyError: DOMAIN for zero or uncertain-degree divisors, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/numeric_division.mojo.
check_numeric_division¶
def check_numeric_division[D: NumericDomain](f: NumericDensePoly[D], g: NumericDensePoly[D], result: NumericDivisionResult[D], mut budget: Budget) raises PolyError -> Bool
Check division bounds by exact residual identities and local interval steps.
Parameters.
D: The numerical coefficient domain.
Arguments.
f: The original dividend.g: The original divisor.result: The proposed quotient, remainder and evidence.budget: The shared work allowance.
Returns. Whether degree bounds, residual enclosures and all claimed family guarantees hold.
Raises.
PolyError: DOMAIN for malformed values or zero divisors, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/numeric_division.mojo.
Incremental text and CAD transport¶
The serialize_*_to functions write the same version-one bytes as the
String-returning serializers through PolynomialTextSink.write. The
deserialize_*_from functions consume an owned PolynomialTextSource through
end of input. Sources may return arbitrary chunks, including empty chunks;
fields may cross chunk boundaries. The default individual-field limit is
16 MiB and can be raised explicitly. Untrusted record counts do not cause
up-front allocation. The returned polynomial is complete and canonical.
The output chunk target defaults to 4 KiB. A single header or term may exceed that target; scalar codecs still construct one scalar string. A source controls its own chunk allocation. A failed operation can leave a partial destination, which callers must discard rather than treat as a complete record.
cad_to calls CADSink.begin with shared projection evidence, then writes
CADStreamEvent values in depth-first order. Internal events contain a complete
stack, whose parent is level - 1; terminal events contain evaluations and
signs. CADStreamChecker.prepare(inputs, budget) can be passed directly as the
sink. Call its finish(receipt, budget) after production. A receipt alone does
not certify a decomposition. Existing cad retains its breadth-first result
and original certificate layout.
The checker retains the projection basis and active sample stacks. It checks and discards completed projection, lifting and sign proof payloads. Empty, truncated, duplicated and reordered traversals do not certify completion. After a rejected event or failed checking computation, construct a new checker.
CADSink¶
trait CADSink
Consume a CAD projection followed by depth-first local witnesses.
Defined in src/polynomials/cad_stream.mojo.
CADSink.begin¶
def begin(mut self, projection: CADProjectionCertificate, mut budget: Budget) raises PolyError
Receive the shared projection evidence once.
Arguments.
projection: The borrowed complete projection certificate.budget: The shared transport allowance.
Raises.
PolyError: On transport or resource failure.
CADSink.write¶
def write(mut self, var event: CADStreamEvent, mut budget: Budget) raises PolyError
Consume the next owned depth-first event.
Arguments.
event: The complete stack or terminal sign evidence.budget: The shared transport allowance.
Raises.
PolyError: On transport or resource failure.
CADStreamChecker¶
@fieldwise_init
struct CADStreamChecker(CADSink, Movable)
Check CAD coverage and signs while retaining only the active sample path.
Defined in src/polynomials/cad_stream.mojo.
CADStreamChecker.prepare¶
@staticmethod
def prepare(inputs: List[SparsePoly[QQ]], mut budget: Budget) raises PolyError -> Self
Prepare checking for the original polynomial family.
Arguments.
inputs: The original rational polynomials.budget: The shared preparation allowance.
Returns. A checker awaiting one projection header and its traversal.
Raises.
PolyError: DOMAIN for malformed input, LIMIT or CAPACITY on work limits.
CADStreamChecker.begin¶
def begin(mut self, projection: CADProjectionCertificate, mut budget: Budget) raises PolyError
Validate shared projection evidence and retain only its checked basis.
Arguments.
projection: The complete projection header.budget: The shared checking allowance.
Raises.
PolyError: DOMAIN for invalid or repeated headers, LIMIT or CAPACITY on work limits; failure invalidates the checker.
CADStreamChecker.write¶
def write(mut self, var event: CADStreamEvent, mut budget: Budget) raises PolyError
Check a producer event directly as a streaming destination.
Arguments.
event: The next owned local certificate.budget: The shared checking allowance.
Raises.
PolyError: DOMAIN for rejected evidence, LIMIT or CAPACITY on work limits.
CADStreamChecker.accept¶
def accept(mut self, var event: CADStreamEvent, mut budget: Budget) raises PolyError -> Bool
Check and discard one complete stack or terminal sign witness.
Arguments.
event: The next owned depth-first event.budget: The shared checking allowance.
Returns. Whether the event is valid; rejection permanently invalidates the checker.
Raises.
PolyError: LIMIT or CAPACITY on work limits; failure invalidates the checker.
CADStreamChecker.finish¶
def finish(self, receipt: CADStreamReceipt, mut budget: Budget) raises PolyError -> Bool
Verify exhaustion of every stack and the terminal receipt counts.
Arguments.
receipt: The producer's completed traversal receipt.budget: The shared checking allowance.
Returns. True only when every branch and terminal sign required by the prepared scope was checked.
Raises.
PolyError: LIMIT on exhaustion.
CADStreamEvent¶
@fieldwise_init
struct CADStreamEvent(Copyable, Movable)
A complete stack or terminal sign witness in depth-first traversal order.
Defined in src/polynomials/cad_stream.mojo.
| Field | Type | |
|---|---|---|
stack |
Optional[CADStackCertificate] |
Present for an internal node; its parent is the preceding path level. |
evaluations |
List[AlgebraicPolynomialEvaluation] |
Input evaluations at a terminal sample, empty for a stack event. |
signs |
List[AlgebraicComparisonCertificate] |
Terminal input signs, empty for a stack event. |
witnesses |
List[CADSignWitness] |
One sign proof per input at a terminal sample, or empty when every sign has an exact evaluation. |
CADStreamReceipt¶
@fieldwise_init
struct CADStreamReceipt(Copyable, Movable)
Record a completed CAD traversal requiring its separately checked witness stream.
Defined in src/polynomials/cad_stream.mojo.
| Field | Type | |
|---|---|---|
stacks |
Int |
The number of complete stack events. |
cells |
Int |
The number of terminal sign-cell events. |
PolynomialTextSink¶
trait PolynomialTextSink
Consume canonical text chunks without retaining the complete record.
Defined in src/polynomials/text_stream.mojo.
PolynomialTextSink.write¶
def write(mut self, var chunk: String, mut budget: Budget) raises PolyError
Consume the next owned text chunk in order.
Arguments.
chunk: The next portion of the version-one record.budget: The shared transport allowance.
Raises.
PolyError: ENCODING for transport failure or LIMIT on exhaustion.
PolynomialTextSource¶
trait PolynomialTextSource(Movable, Deinitable)
Supply arbitrary UTF-8 chunks of one canonical polynomial record.
Defined in src/polynomials/text_stream.mojo.
PolynomialTextSource.read¶
def read(mut self, mut budget: Budget) raises PolyError -> Optional[String]
Read the next owned text chunk.
Arguments.
budget: The shared transport allowance.
Returns. A chunk, possibly empty, or None at the end of input.
Raises.
PolyError: ENCODING for transport failure or LIMIT on exhaustion.
cad_to¶
def cad_to[S: CADSink](inputs: List[SparsePoly[QQ]], variables: List[Int64], mut sink: S, mut budget: Budget, lazard: Bool = False) raises PolyError -> CADStreamReceipt
Produce a complete CAD as depth-first stack and terminal-cell witnesses.
Parameters.
S: The witness destination type.
Arguments.
inputs: The original rational polynomial family.variables: Variables in base-to-top cylindrical order.sink: The incremental destination, called first with projection evidence.budget: The shared computation and transport allowance.lazard: Whether to use Lazard projection and lifting.
Returns. A completion receipt requiring the separately transported witnesses.
Raises.
PolyError: DOMAIN for invalid inputs, UNSUPPORTED for disallowed nullification, LIMIT or CAPACITY on work limits; failure can leave an incomplete destination.
Defined in src/polynomials/cad_stream.mojo.
deserialize_dense_from¶
def deserialize_dense_from[C: CoefficientRing, S: PolynomialTextSource](var source: S, ring: C.Context, mut budget: Budget, *, max_field_bytes: Int = 16777216) raises PolyError -> DensePoly[C]
Decode one canonical polynomial from arbitrary text chunks.
Parameters.
C: The expected coefficient domain.S: The owned text source type.
Arguments.
source: The source consumed through end of input.ring: The expected exact coefficient context.budget: The shared parsing and transport allowance.max_field_bytes: Positive limit for any individual metadata or scalar field.
Returns. The complete polynomial, only after canonical validation and end of input.
Raises.
PolyError: ENCODING for malformed input, DOMAIN for invalid limits or nonfinite scalars, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/interchange.mojo.
deserialize_sparse_from¶
def deserialize_sparse_from[C: CoefficientRing, S: PolynomialTextSource](var source: S, ring: C.Context, mut budget: Budget, *, max_field_bytes: Int = 16777216) raises PolyError -> SparsePoly[C]
Decode one canonical polynomial from arbitrary text chunks.
Parameters.
C: The expected coefficient domain.S: The owned text source type.
Arguments.
source: The source consumed through end of input.ring: The expected exact coefficient context.budget: The shared parsing and transport allowance.max_field_bytes: Positive limit for any individual metadata or scalar field.
Returns. The complete polynomial, only after canonical validation and end of input.
Raises.
PolyError: ENCODING for malformed input, DOMAIN for invalid limits or nonfinite scalars, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/interchange.mojo.
serialize_dense_to¶
def serialize_dense_to[C: CoefficientRing, S: PolynomialTextSink](poly: DensePoly[C], mut sink: S, mut budget: Budget, *, chunk_bytes: Int = 4096) raises PolyError
Write canonical polynomial text in bounded batches.
Parameters.
C: The coefficient domain.S: The text destination type.
Arguments.
poly: The canonical polynomial to serialize.sink: The destination receiving ordered chunks.budget: The shared work and transport allowance.chunk_bytes: Positive target size; a header or single term can exceed it.
Raises.
PolyError: DOMAIN for invalid inputs, ENCODING for transport failure, LIMIT or CAPACITY on work limits; a failed write can leave an incomplete destination.
Defined in src/polynomials/interchange.mojo.
serialize_sparse_to¶
def serialize_sparse_to[C: CoefficientRing, S: PolynomialTextSink](poly: SparsePoly[C], mut sink: S, mut budget: Budget, *, chunk_bytes: Int = 4096) raises PolyError
Write canonical polynomial text in bounded batches.
Parameters.
C: The coefficient domain.S: The text destination type.
Arguments.
poly: The canonical polynomial to serialize.sink: The destination receiving ordered chunks.budget: The shared work and transport allowance.chunk_bytes: Positive target size; a header or single term can exceed it.
Raises.
PolyError: DOMAIN for invalid inputs, ENCODING for transport failure, LIMIT or CAPACITY on work limits; a failed write can leave an incomplete destination.
Defined in src/polynomials/interchange.mojo.
deserialize_numeric_dense_from¶
def deserialize_numeric_dense_from[D: NumericDomain, S: PolynomialTextSource](var source: S, mut budget: Budget, *, max_field_bytes: Int = 16777216) raises PolyError -> NumericDensePoly[D]
Decode one canonical polynomial from arbitrary text chunks.
Parameters.
D: The expected coefficient domain.S: The owned text source type.
Arguments.
source: The source consumed through end of input.budget: The shared parsing and transport allowance.max_field_bytes: Positive limit for any individual metadata or scalar field.
Returns. The complete polynomial, only after canonical validation and end of input.
Raises.
PolyError: ENCODING for malformed input, DOMAIN for invalid limits or nonfinite scalars, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/numeric_interchange.mojo.
deserialize_numeric_sparse_from¶
def deserialize_numeric_sparse_from[D: NumericDomain, S: PolynomialTextSource](var source: S, mut budget: Budget, *, max_field_bytes: Int = 16777216) raises PolyError -> NumericSparsePoly[D]
Decode one canonical polynomial from arbitrary text chunks.
Parameters.
D: The expected coefficient domain.S: The owned text source type.
Arguments.
source: The source consumed through end of input.budget: The shared parsing and transport allowance.max_field_bytes: Positive limit for any individual metadata or scalar field.
Returns. The complete polynomial, only after canonical validation and end of input.
Raises.
PolyError: ENCODING for malformed input, DOMAIN for invalid limits or nonfinite scalars, LIMIT or CAPACITY on work limits.
Defined in src/polynomials/numeric_interchange.mojo.
serialize_numeric_dense_to¶
def serialize_numeric_dense_to[D: NumericDomain, S: PolynomialTextSink](poly: NumericDensePoly[D], mut sink: S, mut budget: Budget, *, chunk_bytes: Int = 4096) raises PolyError
Write canonical polynomial text in bounded batches.
Parameters.
D: The coefficient domain.S: The text destination type.
Arguments.
poly: The canonical polynomial to serialize.sink: The destination receiving ordered chunks.budget: The shared work and transport allowance.chunk_bytes: Positive target size; a header or single term can exceed it.
Raises.
PolyError: DOMAIN for invalid inputs, ENCODING for transport failure, LIMIT or CAPACITY on work limits; a failed write can leave an incomplete destination.
Defined in src/polynomials/numeric_interchange.mojo.
serialize_numeric_sparse_to¶
def serialize_numeric_sparse_to[D: NumericDomain, S: PolynomialTextSink](poly: NumericSparsePoly[D], mut sink: S, mut budget: Budget, *, chunk_bytes: Int = 4096) raises PolyError
Write canonical polynomial text in bounded batches.
Parameters.
D: The coefficient domain.S: The text destination type.
Arguments.
poly: The canonical polynomial to serialize.sink: The destination receiving ordered chunks.budget: The shared work and transport allowance.chunk_bytes: Positive target size; a header or single term can exceed it.
Raises.
PolyError: DOMAIN for invalid inputs, ENCODING for transport failure, LIMIT or CAPACITY on work limits; a failed write can leave an incomplete destination.
Defined in src/polynomials/numeric_interchange.mojo.
Complete streaming example¶
"""Consume polynomial text and proofs without retaining completed payloads."""
from apn_mojo import Rational
from polynomials import *
@fieldwise_init
struct ByteCounter(PolynomialTextSink):
var count: Int
def write(mut self, var chunk: String, mut budget: Budget) raises PolyError:
budget.charge(UInt64(chunk.byte_length()))
self.count += chunk.byte_length()
def main() raises:
var work = Budget()
var polynomial = DensePoly[QQ].from_coefficients(0, NoContext(), [QQ(Rational(-2)), QQ(Rational(0)), QQ(Rational(1))], work)
var text_sink = ByteCounter(0)
serialize_dense_to(polynomial, text_sink, work, chunk_bytes=16)
if text_sink.count != serialize_dense(polynomial, work).byte_length():
raise Error("text byte count mismatch")
print("Canonical text consumed in chunks")
var options = NumericOptions(absolute_bits=2, max_subdivisions=1024)
var real_checker = DescartesStreamChecker.from_dense(polynomial, options, work)
var real_receipt = real_roots_exact_to(polynomial, options, real_checker, work)
if not real_checker.finish(real_receipt, work):
raise Error("incomplete real root witness")
var complex_checker = ComplexRootStreamChecker.from_dense(polynomial, options, work)
var complex_receipt = complex_roots_exact_to(polynomial, options, complex_checker, work)
if not complex_checker.finish(complex_receipt, work):
raise Error("incomplete complex root witness")
print("Real and complex root streams checked")
var inputs: List[SparsePoly[QQ]] = [SparsePoly[QQ].variable(0, MonomialOrder(), NoContext(), work)]
var cad_checker = CADStreamChecker.prepare(inputs, work)
var cad_receipt = cad_to(inputs, [Int64(0)], cad_checker, work)
if not cad_checker.finish(cad_receipt, work):
raise Error("incomplete CAD witness")
print("Cylindrical coverage checked incrementally")
Run from the repository root pixi run mojo run -I build docs/examples/streaming.mojo
Output
Canonical text consumed in chunks
Real and complex root streams checked
Cylindrical coverage checked incrementally