Polynomial array API¶

Import poly for coefficient-first polynomial calculations. Start with dense and sparse for ordinary polynomials. The sections below cover scalar helpers, series and basis representations, rational functions, roots, and polynomial systems. See the array tutorial and exact algebra walkthrough for complete examples.

Computational functions have a mut budget: Budget overload and a convenience overload with max_steps: UInt64 = UInt64.MAX. A shared budget is the last positional argument; modulus and axis are keyword arguments. Inputs are borrowed unless an owning iterator is explicitly moved.

The compiler infers generic parameters from input types. Internal kind values in rendered signatures mean 0=ZZ, 1=QQ, 2=QQi, 3=GF(p), 4=AA, and 5=QQbar; callers do not need to supply them. Exact arrays support iteration, indexing, len, domain(), modulus(), and to_list(). Scalar results are APN values or ModInt. Unsupported scalar types fail compilation. Invalid powers, moduli, axes, or zero divisors raise PolyError with kind DOMAIN; budget exhaustion raises LIMIT, and unrepresentable allocation sizes raise CAPACITY. Algorithms without support for an inferred domain raise UNSUPPORTED; the operation references list those boundaries.

Developers who need mutable core storage can use to_core and from_core; the core API describes both.

Values¶

struct Values[T: Copyable & Deinitable, kind: Int](Copyable, Movable, Iterable, Sized, _WithModulus)

An immutable sequence from coefficients or evaluate_many, retaining every zero.

Parameters.

• T: The sequence's exact scalar type.
• kind: The inferred exact coefficient kind retained by this sequence.

Defined in src/poly/_common.mojo.

Values.IteratorType¶

comptime IteratorType[iterable_mut: Bool, //, iterable_origin: Origin[mut=iterable_mut]]: Iterator = _ValuesIterator[Self.T, Self.kind, ImmOrigin(iterable_origin)]

A borrowing iterator over the shared storage.

Parameters.

• iterable_mut: Whether the borrowing origin is mutable.
• iterable_origin: The lifetime of the borrowed array.

Values.__init__¶

def __init__(out self, var values: List[Self.T], modulus: UInt64, mut budget: Budget) raises PolyError

Take ownership of values and their already validated field metadata.

Arguments.

• values: The coefficient sequence, sparse terms, or prepared array.
• modulus: The prime modulus; supported primes are below 2**62.
• budget: The caller-owned work allowance, shared through preparation and computation.

Raises.

• PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, or DOMAIN for incompatible input.

Values.to_list¶

def to_list(self, mut budget: Budget) raises PolyError -> List[Self.T]

Return an independent mutable list, charging allocation and coefficient work.

Arguments.

• budget: The caller-owned work allowance, shared through preparation and computation.

Returns. An independent mutable list in the current entry order.

Raises.

• PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, or DOMAIN for incompatible input.

Values.to_list¶

def to_list(self, *, max_steps: UInt64 = UInt64.MAX) raises PolyError -> List[Self.T]

Return an independent mutable list, charging allocation and coefficient work.

Arguments.

• max_steps: The complete call's work allowance; defaults to UInt64.MAX.

Returns. An independent mutable list in the current entry order.

Raises.

• PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, or DOMAIN for incompatible input.

Values.modulus¶

def modulus(self) -> UInt64

Return the retained prime modulus, or zero outside a prime field.

Returns. The prime modulus for modular data, or zero otherwise.

Values.domain¶

def domain(self) -> String

Return ZZ, QQ, QQi, GF(p), AA, or QQbar, including for an empty result.

Returns. ZZ, QQ, QQi, GF(p), AA, or QQbar, including for an empty result.

coefficients¶

def coefficients[*Ts: Copyable & Deinitable](values: Tuple[*Ts], mut budget: Budget) raises PolyError -> Values[_Scalar[_TupleKind[Tuple[*Ts]]], _TupleKind[Tuple[*Ts]]]

Promote a heterogeneous tuple using the caller's work allowance.

Parameters.

• Ts: The inferred element types of the input tuple.

Arguments.

• values: The coefficient sequence, sparse terms, or prepared array.
• budget: The caller-owned work allowance, shared through preparation and computation.

Returns. An immutable sequence in the common exact domain, with zeros retained.

Raises.

• PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, or DOMAIN for incompatible input.

Defined in src/poly/_common.mojo.

modint¶

def modint[T: Movable](value: T, modulus: UInt64, mut budget: Budget) raises PolyError -> ModInt

Reduce an integer into a validated prime field.

Parameters.

• T: The sequence's exact scalar type.

Arguments.

• value: An exact integer to reduce modulo the prime.
• modulus: The prime modulus; supported primes are below 2**62.
• budget: The caller-owned work allowance, shared through preparation and computation.

Returns. A canonical ModInt residue in the validated prime field.

Raises.

• PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, or DOMAIN for incompatible input.

Defined in src/poly/_common.mojo.

to_dense¶

def to_dense[I: Iterable, P: Copyable & Deinitable, C: Copyable & Deinitable](values: I, mut budget: Budget) raises PolyError -> dense.Array[_Kind[C]] where _Element[I] == Tuple[P, C]

Fill missing powers of a univariate sparse polynomial with exact zeros.

Integer powers and one-element power tuples are accepted. The required dense length is charged before allocation; use a finite budget for large sparse powers. Multivariate power shapes raise DOMAIN even when constant.

Parameters.

• I: The inferred input iterable type.
• P: The power shape: Int or a tuple of Int powers.
• C: The inferred input coefficient type.

Arguments.

• values: The coefficient sequence, sparse terms, or prepared array.
• budget: The caller-owned work allowance, shared through preparation and computation.

Returns. The ascending coefficients, including zeros for missing powers.

Raises.

• PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, or DOMAIN for incompatible input.

Defined in src/poly/_conversion.mojo.

to_sparse¶

def to_sparse[I: Iterable](values: I, mut budget: Budget) raises PolyError -> sparse.Array[Int, _Kind[_Element[I]]]

Convert ascending coefficients to nonzero (power, coefficient) terms.

The coefficient domain and modulus are retained. Dense powers that exceed UInt32.MAX raise CAPACITY. Input preparation and conversion share the budget.

Parameters.

• I: The inferred input iterable type.

Arguments.

• values: The coefficient sequence, sparse terms, or prepared array.
• budget: The caller-owned work allowance, shared through preparation and computation.

Returns. The univariate nonzero terms, preserving domain and modulus.

Raises.

• PolyError: LIMIT on exhausted work, CAPACITY on unrepresentable sizes, or DOMAIN for incompatible input.

Defined in src/poly/_conversion.mojo.

Shared types¶

Import these from polynomials. A Budget bounds the work of one call or of a sequence of calls; see errors and work limits. Failures raise PolyError, whose PolyErrorKind separates invalid input from exhausted work and unrepresentable sizes. NumericOptions sets accuracy targets and search limits for root covers and adaptive evaluation; NumericOutcome reports why a requested property remains unresolved.

Budget¶

struct Budget(ImplicitlyCopyable, Writable)

A deterministic abstract-work allowance shared by nested calls.

Defined in src/polynomials/errors.mojo.

Budget.__init__¶

def __init__(out self, steps: UInt64 = UInt64.MAX)

Create a budget.

Arguments.

• steps: The initial work allowance.

Budget.charge¶

def charge(mut self, n: UInt64) raises PolyError

Charge before performing work; a rejected charge changes nothing.

Arguments.

• n: The work to charge.

Raises.

• PolyError: LIMIT if the allowance is insufficient.

Budget.remaining¶

def remaining(self) -> UInt64

Return the unspent allowance.

Returns. The remaining abstract work units.

PolyError¶

@fieldwise_init
struct PolyError(Copyable, Movable, Writable)

A typed failure, with no implicit conversion from plain Error.

Defined in src/polynomials/errors.mojo.

PolyErrorKind¶

@fieldwise_init
struct PolyErrorKind(ImplicitlyCopyable, Equatable, Writable)

Classify a polynomial operation's failure.

Defined in src/polynomials/errors.mojo.

PolyErrorKind.LIMIT¶

comptime LIMIT = Self(1)

The work budget is exhausted.

PolyErrorKind.CAPACITY¶

comptime CAPACITY = Self(2)

A size or work counter cannot be represented.

PolyErrorKind.DOMAIN¶

comptime DOMAIN = Self(3)

The operands do not belong to the operation's domain.

PolyErrorKind.UNSUPPORTED¶

comptime UNSUPPORTED = Self(4)

The operation is not supported for these operands.

PolyErrorKind.ENCODING¶

comptime ENCODING = Self(5)

The bytes do not encode a canonical polynomial.

NumericOptions¶

struct NumericOptions(ImplicitlyCopyable, Writable)

Explicit precision, accuracy and subdivision limits for adaptive algorithms.

Defined in src/polynomials/numeric_options.mojo.

NumericOptions.__init__¶

def __init__(out self, *, initial_precision: Int = 128, max_precision: Int = 1024, absolute_bits: Int = 32, relative_bits: Int = 0, max_subdivisions: Int = 4096, require_isolation: Bool = True)

Set explicit numerical options, validated when an algorithm starts.

Arguments.

• initial_precision: The first working precision.
• max_precision: The precision ceiling.
• absolute_bits: The absolute width exponent, zero to disable.
• relative_bits: The relative width exponent, zero to disable.
• max_subdivisions: The deterministic search allowance.
• require_isolation: Require single-root regions.

NumericOutcome¶

@fieldwise_init
struct NumericOutcome(ImplicitlyCopyable, Equatable, Writable)

Classify a completed numerical request or an inconclusive analysis.

Defined in src/polynomials/numeric_options.mojo.

NumericOutcome.SUCCESS¶

comptime SUCCESS = Self(0)

The requested claims were established.

NumericOutcome.UNCERTAIN_DEGREE¶

comptime UNCERTAIN_DEGREE = Self(1)

The leading coefficient may vanish.

NumericOutcome.INPUT_UNCERTAINTY¶

comptime INPUT_UNCERTAINTY = Self(2)

Coefficient or argument uncertainty prevents the requested guarantee.

NumericOutcome.PRECISION_CEILING¶

comptime PRECISION_CEILING = Self(3)

The configured precision did not establish the requested accuracy.

NumericOutcome.SUBDIVISION_LIMIT¶

comptime SUBDIVISION_LIMIT = Self(4)

The configured subdivision allowance did not finish the analysis.

NumericOutcome.UNRESOLVED_BOUNDARY¶

comptime UNRESOLVED_BOUNDARY = Self(5)

A search boundary could not be certified root-free.

Root and system workflows¶

• Root results: exact real roots, counts, numerical covers, independent checks, and functional refinement.
• Algebraic values: exact arithmetic, comparisons, bounds, and explicit rational approximation.
• Sparse bases: reusable Gröbner bases, normal forms, membership, and identity witnesses.
• CAD: readable sign constraints, exact samples, full decompositions, and streamed checking.

Series, bases, and rational functions¶

• Formal series: exact coefficients with an explicit unknown-tail order.
• Alternative bases: Newton, Chebyshev, and Bernstein coefficients, conversion, arithmetic, and subdivision.
• Rational functions: normalized fractions, calculus, partial fractions, and Laurent expansions.

For rounded and enclosing coefficients, use numerical arrays. Batch maps apply reusable functions across whole polynomials. The serialization guide covers complete values and existing coefficient records; poly.io provides string and streaming entry points.

Certified evaluation retains independent enclosure evidence and explicit adaptive accuracy outcomes.

Checked exact results retain algebra evidence for functional access and independent checking. Specialized CAD workflows expose projection, selected cells, Lazard evaluation, and full covering.

Exact queries and algorithm choices include closed-interval signs, determinant-certified resultants, and sparse modular GCD selection. Sparse division also accepts monomial order and axis priority.