gr_poly.h

Initialises poly as the zero polynomial. gr_poly_init2 also allocates (and initialises) space for len coefficients.

Clears the coefficients and frees the memory of poly.

Returns a pointer to the coefficient of x^i. The index must be less than the allocated size; coefficients at indices from length on are initialised elements but not part of the polynomial.

Deprecated names of gr_poly_coeff_ptr and gr_poly_coeff_srcptr.

Returns the length of poly, that is one more than the index of the leading stored coefficient, or 0 for the zero polynomial. Over rings with undecidable equality this bounds the degree plus one.

Swaps poly1 and poly2 in constant time by exchanging the structures.

Ensures that poly has space for at least len coefficients, without changing its length or coefficients. The inline function gr_poly_fit_length calls _gr_poly_fit_length only when the current allocation is too small; the latter grows the allocation to at least twice its old size, so that repeated calls cost amortised linear time.

Sets the length of poly to len, which must not exceed the allocation, without normalising. When the polynomial is shortened, the coefficients beyond the new length are set to zero, which frees the memory of heap-allocated elements.

Set the length of poly to len (respectively keep the current length) and then decrease it while the leading coefficient is provably zero. This is the usual last step after an underscore function has written coefficients. Both call the ring method GR_METHOD_POLY_SET_LENGTH_NORMALISE, whose default gr_generic_poly_set_length_normalise zeroes the dropped coefficients like _gr_poly_set_length; rings with shallow elements (nmod, fmpz_mod, mpn_mod, nmod8, nmod32) override it to compute only the new length.

The default implementation of _gr_poly_set_length_normalise, declared in gr_generic.h.

Initialises vec as a vector of len zero polynomials (\mathit{len} \ge 0), respectively clears all its polynomials and frees the vector.

Return a pointer to the polynomial at index 0 \le i < \mathit{length}, and the length of the vector.

gr_poly_vec_fit_length allocates space for at least len polynomials without changing the length. gr_poly_vec_set_length changes the length to \mathit{len} \ge 0, clearing removed entries and appending zero polynomials as needed.

Sets res to a copy of src.

Append f to the vector. gr_poly_vec_append copies it; gr_poly_vec_append_swap swaps it into the new entry without copying, so that f becomes the zero polynomial.

Sets res to a copy of src.

Set res to the image of an integer polynomial, a rational polynomial, or a polynomial over the ring x_ctx, converting each coefficient into R with gr_set_fmpz or gr_set_other; for a rational polynomial the integer numerators are converted and multiplied by the inverse of the common denominator in R. The conversion fails (with GR_DOMAIN or GR_UNABLE) if a coefficient has no image, for example a fraction whose denominator is divisible by p in \mathbb{Z}/p\mathbb{Z}.

Set poly to 0, 1, -1 or the generator x. In the zero ring the results are all the zero polynomial.

Set poly to the constant polynomial c, where c is an element of R or an integer or rational number converted into R.

Sets res to the reversal x^{n-1} f(1/x) of the polynomial f formed by the first n coefficients of poly (padded with zeros if poly is shorter). The underscore version requires \mathit{len} \le n, writes n coefficients and allows res to be poly.

Sets res to poly reduced modulo x^{\mathit{newlen}}.

Write the polynomial as an expression in the variable named x, in increasing order of degree with zero terms omitted, to a stream, to a newly allocated string *res (to be freed with flint_free), or to standard output with the variable x.

Parse a polynomial from the expression s in the variable named x. The underscore version writes exactly len coefficients, zero-padding a shorter result, and returns GR_UNABLE if the parsed polynomial is longer than len (intermediate values may be longer). Returns GR_UNABLE if the string cannot be parsed.

Sets poly to a random polynomial of length at most len, with coefficients from gr_randtest. The distribution is meant for testing: it is not uniform and produces many special values.

Returns whether the two polynomials are equal, comparing the common coefficients and testing the extra coefficients of the longer one for zero. The underscore version requires \mathit{len1} \ge \mathit{len2}.

Return whether poly is 0, 1, the generator x, or a constant polynomial. Coefficients that are not provably zero or one make the answer T_UNKNOWN.

Set the coefficient of x^n to c, extending poly with zeros if n \ge length, and normalise.

Sets res to the coefficient of x^n, which is zero for n \ge length.

Sets res to -f.

Set res to the sum or difference. The underscore versions write \max(\mathit{len1}, \mathit{len2}) coefficients and allow res to be either input.

Sets res to the product. The underscore version requires positive lengths, writes \mathit{len1} + \mathit{len2} - 1 coefficients and does not allow aliasing; it is _gr_poly_mullow with the full length, so the algorithm is that of the ring's GR_METHOD_POLY_MULLOW method.

Sets res to the product truncated to length len, that is reduced modulo x^{\mathit{len}}. The underscore version requires positive lengths and \mathit{len} \le \mathit{len1} + \mathit{len2} - 1, writes len coefficients and does not allow aliasing. It calls the ring method GR_METHOD_POLY_MULLOW, which defaults to classical multiplication and which most rings with fast multiplication override.

Sets res to the middle product: the coefficients of x^{\mathit{nlo}}, \ldots, x^{\mathit{nhi} - 1} of the product, shifted down by \mathit{nlo}. The underscore version requires positive lengths and 0 \le \mathit{nlo} < \mathit{nhi} \le \mathit{len1} + \mathit{len2} - 1, writes \mathit{nhi} - \mathit{nlo} coefficients and does not allow aliasing. It calls the ring method GR_METHOD_POLY_MULMID; see Middle products and the transposition principle.

Multiply with the classical algorithm, computing each output coefficient as one dot product (_gr_vec_dot_rev), so that rings with fast dot products (delayed reduction, exact accumulation) benefit. Squaring uses the symmetry of the product to halve the number of multiplications.

One level of Karatsuba multiplication [KO1962]: three products of half length with sub-products computed by _gr_poly_mul. It is not optimised for unbalanced operands. The underscore version requires positive lengths and does not allow aliasing.

One level of balanced Toom-3 multiplication [Too1963; Coo1966]: evaluation at 0, 1, -1, 2, \infty with Bodrato's sequence of operations and five products of a third of the length, computed by _gr_poly_mul. Requires a commutative ring with exact division by 2 and 3; not optimised for squaring. The underscore version requires positive lengths and does not allow aliasing.

Toom-Cook multiplication of arbitrary order with low memory use: the inputs are split into blocks of m coefficients, viewed as polynomials in t = x^m, and the product is computed by evaluation at r points and interpolation. Exactly one of num_points (r) and splitting_degree (m) must be nonzero; the other is chosen automatically.

For coefficients that are themselves polynomials (a context created by gr_ctx_init_gr_poly or gr_ctx_init_fmpz_poly), reduce the bivariate product to one univariate product over the inner coefficient ring by Kronecker substitution y \mapsto x^k (Kronecker substitution). Returns GR_UNABLE if the coefficients are not polynomials. The polynomial-ring contexts use this for their GR_METHOD_POLY_MULLOW method when all lengths are at least 5 and the inner ring has a non-classical multiplication.

For complex coefficients stored as pairs of elements of real_ctx (real part, imaginary part), compute the product from products of real polynomials: the inputs are split into their real and imaginary parts and the products are computed in real_ctx.

Set res to f + c or f - c for a constant c, an element of R or an integer or rational number converted into R.

Set res to f c, or to c f for gr_poly_scalar_mul (the two differ over noncommutative rings).

Set res to \mathit{res} + f c or \mathit{res} - f c.

Set res to f / c, dividing each coefficient with gr_div (GR_DOMAIN if a quotient does not exist in R), respectively with gr_divexact, which assumes that every division is exact and may then be faster (for example over \mathbb{Z}).

Set res to f^e by binary exponentiation (pow_ui currently calls the binexp version). The underscore versions write e(\mathit{flen} - 1) + 1 coefficients and require \mathit{flen} \ge 1 and e \ge 1. The non-underscore versions return GR_UNABLE if the length of the result would overflow an slong.

Sets res to f^e. A negative exponent is allowed only for a constant polynomial with an invertible constant (GR_DOMAIN otherwise), and an exponent that does not fit in a word gives GR_UNABLE unless f is constant.

Set res to f^e \bmod x^{\mathit{len}} by binary exponentiation with truncated products (pow_series_ui currently calls the binexp version). The underscore versions write len coefficients.

Set res to the power series f^{p/q} \bmod x^{\mathit{len}} for a rational exponent p/q, using the recurrence obtained from q f h' = p f' h for h = f^{p/q} (often attributed to J. C. P. Miller, see [Knu1997, §4.7]), which costs O(\mathit{flen} \cdot \mathit{len}) operations. The constant term f_0^{p/q} is computed with gr_pow_fmpq, and the recurrence divides by i q f_0 for i = 1, \ldots, \mathit{len} - 1, so f_0 and these integers must be invertible (or the divisions exact).

Set res to f x^n, respectively to \lfloor f / x^n \rfloor (the coefficients of degree n and higher, moved down). The underscore versions write \mathit{len} + n respectively \mathit{len} - n coefficients (n < \mathit{len} for the right shift) and allow aliasing.

Set Q and R to the quotient and remainder of A by B. The non-underscore functions return GR_DOMAIN if B is zero and GR_UNABLE if the leading coefficient of B is not provably nonzero. gr_poly_divrem calls the ring method GR_METHOD_POLY_DIVREM.

The same as the divrem functions, but compute only the quotient. gr_poly_div calls the ring method GR_METHOD_POLY_DIV; its default _gr_poly_div_generic uses long division when the divisor or the quotient has at most 10 coefficients and Newton division otherwise (falling back to divide-and-conquer division without inversion).

The same as the divrem functions, but return only the remainder (the quotient is computed in a temporary).

Division with remainder (or quotient only) given Binv, the inverse of the reversal of B modulo x^{\mathit{lenB}}, which can be computed once with gr_poly_inv_series and reused for many divisions by B. The quotient is the reversal of a single truncated product, and the remainder costs one more product. The non-underscore versions return GR_UNABLE if \mathit{lenA} > 2 \mathit{lenB} - 2.

Set res to the power series inverse A^{-1} \bmod x^{\mathit{len}}. Returns GR_DOMAIN if the constant term of A is not invertible (for example if A = 0, except in the zero ring).

Set res to the power series quotient A / B \bmod x^{\mathit{len}}. Returns GR_DOMAIN if B = 0; if the constant term of B is not invertible, the quotient may still exist, and the basecase, noinv and divconquer algorithms find it whenever every coefficient division is exact.

Set Q to the exact quotient A / B. The non-underscore functions return GR_DOMAIN if B = 0 and GR_UNABLE if its leading coefficient is not provably nonzero. gr_poly_divexact calls the ring method GR_METHOD_POLY_DIVEXACT, whose default uses the basecase for divisors of length at most 2 and the bidirectional algorithm otherwise; fmpz uses the exact division of fmpz_poly and nmod that of nmod_poly. The underscore functions require \mathit{Alen} \ge \mathit{Blen} \ge 1 and write \mathit{Alen} - \mathit{Blen} + 1 coefficients.

Set Q to the power series quotient A / B \bmod x^{\mathit{len}}, assuming that it exists, by basecase division starting from the constant terms.

Sets res to the inverse of poly in R[x]. This succeeds only for a constant polynomial with an invertible constant (and for the zero polynomial over the zero ring); any polynomial of length at least 2 gives GR_DOMAIN.

Set res to the power series square root f^{1/2} or reciprocal square root f^{-1/2} modulo x^{\mathit{len}}. The constant term is computed with gr_sqrt or gr_rsqrt and must exist; the computation then divides by 2 and by the constant term.

Sets res to f(x) for x \in R. This calls the ring method GR_METHOD_POLY_EVALUATE, whose default gr_generic_poly_evaluate uses Horner's rule; nmod, fq, fq_nmod and fq_zech override it with the evaluation of their polynomial modules.

Set res to f(x) with a specific algorithm. Horner's rule uses \mathit{len} - 1 multiplications by x. The rectangular version (rectangular splitting, [PS1973]) computes x, \ldots, x^m for m \approx \sqrt{\mathit{len}}, evaluates the blocks of m coefficients as dot products with these powers and combines the blocks by Horner's rule in x^m, so that only O(\sqrt{\mathit{len}}) multiplications are full products of ring elements; this pays off when the coefficients are cheaper than x (small integers and a large x, scalars and a matrix or polynomial argument). The modular version also computes the powers (x^j)^0, \ldots, (x^j)^{k-1} with j \approx k \approx \sqrt{\mathit{len}} and evaluates everything with j + 1 dot products, which suits rings where dot products are much cheaper than separate multiplications (delayed modular reduction).

The default implementation of _gr_poly_evaluate (Horner's rule), declared in gr_generic.h.

Set res to f(x) where the coefficients of f belong to ctx and x and res belong to x_ctx, for example an integer polynomial evaluated at a matrix or at a real ball. The coefficients enter the computation through gr_mul_other and gr_add_other. The default version uses Horner's rule.

Convert a polynomial of length len from the monomial basis to the Newton basis or back, with O(\mathit{len}^2) operations. The underscore versions read \mathit{len} - 1 entries of basis; the non-underscore versions return GR_UNABLE if basis is shorter.

Sets res to the value at x of the polynomial given in the Newton basis, by a Horner scheme in the factors x - c_i. The same conditions on basis apply as for the conversions.

Set res to the Newton basis form of the interpolating polynomial f of length at most len with f(c_i) = y_i for 0 \le i < \mathit{len}, computed by divided differences. The first len points of basis must be pairwise distinct.

Allocate, free and fill the subproduct tree of len points roots: level 0 holds the linear polynomials x - x_i and each higher level the products of pairs of the level below.

Set poly to (x - x_0)(x - x_1) \cdots (x - x_{n-1}). The underscore version writes n + 1 coefficients.

Set y_i = f(x_i) for all points. The iter versions evaluate at each point separately with _gr_poly_evaluate (O(n \cdot \mathit{plen}) operations); the fast versions reduce f down the subproduct tree, which requires the divisions by monic tree polynomials. The precomp version takes a tree built with _gr_poly_tree_build. The non-underscore versions resize ys to the length of xs.

Set res to the interpolating polynomial f of length at most len with f(x_i) = y_i, for pairwise distinct points x_i. The default versions currently call the newton versions, which compute divided differences in the Newton basis and convert to the monomial basis, with O(\mathit{len}^2) operations.

Fast interpolation with a subproduct tree. The weights are w_i = 1 / \prod_{j \ne i} (x_i - x_j), obtained by evaluating the derivative of the root product at the points; the precomp version takes the tree from _gr_poly_tree_build and the weights from _gr_poly_interpolation_weights. This requires a field (the weights must be invertible).

Set res to the Taylor shift f(x + c). The horner version uses an optimised Horner scheme with O(\mathit{len}^2) additions and multiplications by c; the divconquer version splits f in halves and multiplies by powers of x + c, in O(M(\mathit{len}) \log \mathit{len}) operations; the convolution version uses one multiplication of length len, f(x + c) = \sum_k \frac{x^k}{k!} \sum_i (i! f_i) \frac{c^{i-k}}{(i-k)!}, which requires division by 1, \ldots, \mathit{len} - 1. The underscore versions allow aliasing.

Set res to the composition f(g(x)), where f is poly1 and g is poly2, by Horner's rule or by divide and conquer (splitting f in halves and multiplying by powers of g computed by repeated squaring). The default version handles g = a x^n + c by a Taylor shift by c followed by a scaling and an inflation, uses Horner's rule for \mathit{len1} \le 7 and divide and conquer otherwise. The underscore versions write (\mathit{len1} - 1)(\mathit{len2} - 1) + 1 coefficients and do not allow aliasing.

Set res to f(x^n). The underscore version works in place on an array of (\mathit{len} - 1) n + 1 elements whose first len entries hold f and whose other entries are zero.

gr_poly_deflation returns the largest m such that f = g(x^m) for a polynomial g: 0 for f = 0, 1 for a nonzero constant, and n for a monomial c x^n with n \ge 1. A coefficient that is not provably zero counts as nonzero, so the value is always valid but need not be maximal over inexact rings. gr_poly_deflate sets res to g given m \ge 1 (GR_DOMAIN for m = 0); f is assumed to have this form.

Set res to the power series composition f(g(x)) \bmod x^n, where f is poly1 and g is poly2 with g(0) = 0 (the non-underscore versions return GR_DOMAIN if g(0) is nonzero and GR_UNABLE if it is not provably zero). The algorithms are Horner's rule, the baby-step giant-step method of Brent and Kung [BrentKung1978], divide and conquer, and the algorithm of Kinoshita and Li [KL2024] with O(M(n) \log n) operations.

Set res to the compositional inverse f^{-1}, with f^{-1}(f(x)) = f(f^{-1}(x)) = x \bmod x^n. The reversion exists when f(0) = 0 and f'(0) is invertible; GR_DOMAIN is returned otherwise (GR_UNABLE if f(0) is not provably zero).

Sets res to the derivative f'. The underscore version writes \mathit{len} - 1 coefficients and allows aliasing.

Sets res to the n-th derivative f^{(n)}. The underscore version requires n < \mathit{len}, writes \mathit{len} - n coefficients and allows aliasing.

Sets res to the integral \int_0^x f(t)\,dt, whose coefficient of x^{i+1} is f_i / (i + 1), computed with gr_div_ui; the divisions must be possible in R (GR_DOMAIN or GR_UNABLE otherwise, for example over \mathbb{Z} or in small characteristic). The underscore version reads \mathit{len} - 1 coefficients of poly, writes len coefficients and allows aliasing.

Sets res to f / \operatorname{lc}(f), multiplying by the inverse of the leading coefficient or, if it has none, dividing each coefficient by it (which can succeed over integral domains when the divisions are exact). Returns GR_DOMAIN if f = 0 or a division fails, and GR_UNABLE if the leading coefficient is not provably nonzero.

Return whether the leading coefficient is 1. The zero polynomial is not monic.

Sets res to the canonical associate of f: f multiplied by the unit c of R that makes the leading coefficient canonical in the sense of gr_canonical_associate (1 over a field, positive over \mathbb{Z}). If u is not NULL, it is set to the constant polynomial c, so that \mathit{res} = u f. The zero polynomial is its own canonical associate, with u = 1. GCD functions use this to normalise their output.

Set G to a greatest common divisor of A and B. The non-underscore functions return the canonical associate (the monic GCD over a field, the GCD with positive leading coefficient over \mathbb{Z}), the zero polynomial if both inputs are zero, and GR_UNABLE if a leading coefficient is not provably nonzero. See Greatest common divisors over generic rings.

Set G, S, T with G = SA + TB, where G is a GCD of A and B over a field (monic) and over other GCD domains an associate of the GCD that may differ from it by a factor dividing the resultant. See Greatest common divisors over generic rings.

Implement gr_poly_gcd and gr_poly_xgcd around a given underscore implementation (with the signatures of _gr_poly_gcd and _gr_poly_xgcd): handle zero and constant inputs, order the inputs by length, check the leading coefficients, manage memory and aliasing, and canonicalise the result (for the GCD only if canonicalise_unit is nonzero; the cofactors of the extended GCD are scaled by the same unit). The non-underscore algorithm-specific functions are built this way, and rings can use them to wrap their own GCD methods.

Computes the half-gcd of a and b (Half-GCD): a 2 \times 2 matrix M of polynomials, a sign \sigma = \pm 1 = \det M and the consecutive remainders A, B with (A, B)^T = \sigma M^{-1} (a, b)^T and \deg A \ge \lceil \deg a / 2 \rceil > \deg B. The recursion uses the Euclidean algorithm below cutoff.