Calculate with polynomial arrays¶

Use poly.dense for ascending coefficients and poly.sparse for nonzero terms. Dense storage suits a univariate polynomial with many occupied degrees; sparse storage handles several variables and avoids storing absent powers. Both infer exact coefficient domains and return immutable, iterable results. The same function names cover arithmetic, powers, calculus, division, and evaluation in either representation.

Start with coefficients or terms¶

"""Work with exact dense and sparse polynomial arrays."""
import poly
from apn_mojo import Rational, ExactComplex
from polynomials import Budget, PolyErrorKind


def main() raises:
    # Coefficients run from the constant term to the highest power.
    var p = poly.dense.asarray([1, 2, 3])
    print(p.domain(), p.to_list())
    print(poly.dense.evaluate(p, 2))
    print(poly.dense.multiply([1, 1], [1, -1]).to_list())

    # Promote heterogeneous values before making a homogeneous collection.
    var mixed = poly.coefficients((1, Rational(1, 2), ExactComplex(0, 1)))
    print(mixed.domain(), poly.dense.evaluate(mixed, 2))

    # 2*x + 3*y^2: tuple positions identify the variables.
    var terms = [((1, 0), 2), ((0, 2), 3)]
    print(poly.sparse.evaluate(terms, (2, 3)))
    print(poly.sparse.derivative(terms, axis=1).to_list())

    var modular = poly.dense.asarray([-1, 2], modulus=7)
    print(modular.domain(), poly.dense.evaluate(modular, 3).value)

    # A tuple keeps sparse coefficient types intact until promotion.
    var mixed_terms = poly.sparse.asarray(((0, 3), (2, Rational(1, 2))))
    print(mixed_terms.domain(), poly.sparse.evaluate(mixed_terms, 2))

    # A shared budget covers a sequence of operations, including conversion.
    var budget = Budget(10000)
    var slope = poly.dense.derivative(p, budget)
    print(poly.dense.evaluate(slope, 2, budget))
    try:
        _ = poly.dense.multiply(p, p, max_steps=1)
    except error:
        if error.kind != PolyErrorKind.LIMIT:
            raise error
        print("work limit reached")

ZZ [1, 2, 3]
17
[1, 0, -1]
QQi ExactComplex(2, 4)
31
[((0, 1), 6)]
GF(7) 5
QQ 5
14
work limit reached

[1, 2, 3] represents \(1+2x+3x^2\). Sparse terms [(1, 2), (2, 3)] represent \(2x+3x^2\). For several variables, use power tuples: [((1, 0), 2), ((0, 2), 3)] represents \(2x+3y^2\). Tuple positions identify variables; every term must use the same power shape. Sparse construction combines repeated powers and removes zero coefficients.

Lists, fixed arrays, spans, and finite iterables work as inputs. Dense construction also accepts one-dimensional APN integer and rational batches. An owning iterator can be consumed with asarray(iterator^). The resulting polynomial stays in memory; iteration does not imply constant-memory storage.

Let coefficient types choose the domain¶

Promotion follows types, including zero coefficients. A rational zero still selects QQ; an exact complex value with zero imaginary part still selects QQi. Algebraic arrays likewise retain AA or QQbar, even when a result is rational or zero. See algebraic coefficients. Floats and Bool require an explicit conversion before they can enter this exact interface.

Mojo must choose a list's element type before calling a function. When scalar types differ, use poly.coefficients((...)), as above. For sparse inputs, poly.sparse.asarray(((0, 3), (2, Rational(1, 2)))) directly accepts a tuple of mixed terms. Prepare that result before passing it to an arithmetic function.

poly.modint(value, prime) constructs a finite-field coefficient. Alternatively, asarray(values, modulus=7) reduces integer coefficients into \(\mathbb F_7\). All modular inputs must agree on the prime; rational and complex values have no implicit modular conversion. An empty modular input needs modulus= unless it is already a prepared result retaining its field.

Divide, integrate, and evaluate at many points¶

"""Divide, integrate, evaluate, and change representation using coefficient arrays."""
import poly


def main() raises:
    # (x^2 + 1) / (2*x + 1) has rational quotient and remainder.
    var result = poly.dense.divmod([1, 0, 1], [1, 2])
    print("Quotient:", result[0].to_list())
    print("Remainder:", result[1].to_list())
    print("Integral:", poly.dense.integral([1, 1]).to_list())

    var p = poly.dense.from_roots([0, 1, 1])
    print("Coefficients:", p.to_list())
    print("Values:", poly.dense.evaluate_many(p, [0, 1, 2, 0]).to_list())
    var terms = poly.to_sparse(p)
    print("Terms:", terms.to_list())
    print("Dense again:", poly.to_dense(terms).to_list())

    # 2*x + 3*y^2, evaluated at three coordinate pairs.
    var surface = [((1, 0), 2), ((0, 2), 3)]
    print("Surface:", poly.sparse.evaluate_many(surface, [(0, 0), (2, 3), (0, 0)]).to_list())
    print("Total degree:", poly.sparse.degree(surface))

Quotient: [-1/4, 1/2]
Remainder: [5/4]
Integral: [0, 1, 1/2]
Coefficients: [0, 1, -2, 1]
Values: [0, 0, 2, 0]
Terms: [(1, 1), (2, -2), (3, 1)]
Dense again: [0, 1, -2, 1]
Surface: [0, 31, 0]
Total degree: 2

divmod returns (quotient, remainder). Integer coefficients promote to exact rationals, so dividing \(x^2+1\) by \(2x+1\) returns \(x/2-1/4\) and \(5/4\). integral makes the same promotion and chooses zero as the integration constant. In a prime field, integration raises DOMAIN when a nonzero term would require division by zero.

evaluate_many evaluates one polynomial at each point, in input order. Its Values result retains all zeros, including trailing zeros. For a multivariate sparse polynomial, each point is a tuple of coordinates. The polynomial is prepared and promoted once for the call. Use batch maps for broadcasting collections of polynomials or constructing Cartesian grids.

from_roots constructs the monic product of \((x-r)\) factors, keeping repeated and zero roots. It accepts known exact roots; use real_roots to find them from coefficients or a root cover for certified numerical bounds.

Work with scalar constants¶

Pass a scalar directly to add, subtract, or multiply, in either operand position. dense.subtract(4, p) computes \(4-p\). divide(p, scalar) scales by the scalar's reciprocal; integer coefficients promote to QQ, so no precision is lost. Use divmod for polynomial quotient and remainder, or poly.rational to retain a polynomial denominator.

"""Scalar arithmetic keeps coefficient input concise and sparse powers sparse."""
from poly import dense, sparse
from apn_mojo import ArithmeticContext, FloatFormat, Rational
from std.testing import assert_equal


def main() raises:
    var p = dense.asarray([1, 2, 3])
    var shifted = dense.subtract(4, p)
    var half = dense.divide(p, 2)
    assert_equal(dense.evaluate(shifted, 2), -13)
    assert_equal(half[0], Rational(1, 2))
    print("Integer division promotes to", half.domain())
    var context = ArithmeticContext(format=FloatFormat(precision=80))
    var high_power = sparse.asarray([(1000000000, 6)], context=context)
    var scaled = sparse.divide(high_power, 2, context=context, max_steps=1000000)
    assert_equal(scaled[0][1].to_rational_exact(), Rational(3))
    print("Stored terms after scaling:", len(scaled))

Integer division promotes to QQ
Stored terms after scaling: 1

Exact coefficients and scalars follow the usual domain promotion rules. Prime-field operands must share a modulus and can mix with integers. Division by zero raises DOMAIN, including for a zero polynomial. Prepared inputs remain unchanged.

For numerical arrays, pass context= to each operation. The scalar converts to the array's stored domain; use astype first if you need a complex domain. A ball divisor must exclude zero. Sparse scaling visits stored terms without allocating coefficients for missing powers.

Display variable names¶

Keep coefficients as data and choose names when displaying a result:

"""Give variables names when displaying coefficient-based polynomials."""
from poly import dense, sparse


def main() raises:
    print(dense.format([1, -2, 3], variable="t"))
    var p = sparse.asarray([((2, 1), 3), ((0, 0), -1)])
    print(sparse.format(p, variables=["u", "v"]))

(3)*t^2 + (-2)*t + (1)
(3)*u^2*v + (-1)

format supports ZZ, QQ, QQi, and prime fields. It prints every nonzero term with its exact coefficient in decreasing lexicographic order. Dense polynomials and one-axis sparse polynomials default to x; multiple axes default to x0, x1, and so on. Supply one distinct ASCII identifier per sparse axis, including unused axes. The name i is reserved over QQi.

Display text omits domain, modulus, and shape metadata. Use serialization to save a value, including algebraic or numerical coefficients.

Choose the operation¶

poly.to_sparse drops zero coefficients. poly.to_dense fills missing powers of a univariate polynomial with zeros. Both preserve the domain and modulus. Dense storage needs one slot for every power through the degree; set max_steps when converting a sparse input with potentially large powers.

The zero polynomial has degree -1. Raising any polynomial, including zero, to power zero returns one. Sparse degree defaults to total degree; sparse output terms use increasing lexicographic order with tuple position zero having the highest comparison priority.

For precise signatures and shared conventions, see the array API reference; budgets and errors explains work limits. Continue with exact array algebra for factorization, interpolation, and elimination. The poly namespaces also expose root finding, Gröbner bases, CAD, and their certificate checks.

Continue with root finding and algebraic values, or use Gröbner bases and CAD for polynomial systems.

Use formal series for truncated calculations, basis arrays for Newton, Chebyshev, or Bernstein coefficients, and rational functions for normalized polynomial ratios. Each representation retains the metadata needed by its functional operations.

For floating-point or ball coefficients, choose an explicit numerical context. You can also save canonical coefficient records.