Your first polynomial¶

A dense polynomial is a sequence of coefficients, starting with the constant term. [1, 1] means \(1+x\); [1, 2, 3] means \(1+2x+3x^2\). Pass those coefficients to poly.dense functions to calculate with exact integers and fractions, without selecting a ring or parsing an expression.

Install the package, then run this program. It expands \((1+x)^3\) and evaluates the result and its derivative at \(x=3\).

"""Expand (1 + x)^3 and evaluate it and its derivative exactly."""
import poly
from apn_mojo import Integer
from std.testing import assert_equal


def main() raises:
    var polynomial = poly.dense.power([1, 1], 3)
    var value = poly.dense.evaluate(polynomial, 3)
    var slope = poly.dense.evaluate(poly.dense.derivative(polynomial), 3)
    assert_equal(value, Integer(64))
    assert_equal(slope, Integer(48))
    print("Value at 3:", value)
    print("Derivative at 3:", slope)

Value at 3: 64
Derivative at 3: 48

power returns the coefficients [1, 3, 3, 1]. The input integers select integer arithmetic; evaluate returns an apn_mojo Integer. All intermediate values and both answers are exact.

Reuse a polynomial¶

Every arithmetic function accepts a coefficient iterable. Call poly.dense.asarray(values) when you want to normalize an input once and reuse it. A prepared result supports len, indexing, iteration, domain(), and to_list(). Copies share immutable storage; to_list() gives you a mutable list. Trailing zero coefficients are removed, so the zero polynomial has an empty coefficient sequence.

Rational coefficients select QQ; exact complex coefficients select QQi. Use poly.coefficients((...)) for a tuple of mixed scalar types, or pass an ordinary homogeneous list directly. The array tutorial covers promotion, sparse terms, modular coefficients, and evaluation at many points.

Bound a calculation¶

Each function accepts an optional max_steps limit. As a call computes, the library counts steps: one for each term or coefficient it processes and for each element it allocates, and more for arithmetic on large numbers, growing with their size in bytes. If a call would exceed its limit, it stops and raises PolyError with kind LIMIT. The default, UInt64.MAX, means no limit.

The count is exact and repeatable: the same call on the same input takes the same number of steps on any machine. To see how many steps a call takes, pass it a Budget from polynomials as the last argument, and read how much of the budget it used:

"""Count the steps a calculation takes, then bound it with max_steps."""
import poly
from polynomials import Budget, PolyErrorKind


def main() raises:
    var work = Budget()
    _ = poly.dense.power([1, 1], 100, work)
    print("Steps for (1+x)^100:", UInt64.MAX - work.remaining())

    var stopped = False
    try:
        _ = poly.dense.power([1, 1], 100, max_steps=10000)
    except error:
        stopped = error.kind == PolyErrorKind.LIMIT
    print("Stopped by max_steps=10000:", stopped)

    var result = poly.dense.power([1, 1], 100, max_steps=1000000)
    print("Finished within max_steps=1000000, degree", poly.dense.degree(result))

Steps for (1+x)^100: 329732
Stopped by max_steps=10000: True
Finished within max_steps=1000000, degree 100

Computing \((1+x)^{100}\) takes 329,732 steps, so a limit of 10,000 stops it and a limit of 1,000,000 lets it finish.

Steps do not convert to time. On one laptop core, different operations ran at anywhere from about 100 million to over 10 billion steps per second, because the count charges arithmetic on large numbers more than it costs to run. Measure the steps your own inputs take, and set the limit with room to spare. To bound a sequence of calculations together, pass the same Budget to each call. Budgets and errors lists what each kind of work costs.

Continue with dense and sparse arrays.