fmpz_poly.h

Initialise poly as the zero polynomial. fmpz_poly_init allocates nothing; fmpz_poly_init2 allocates alloc coefficients, all zero. A polynomial must be cleared with fmpz_poly_clear after use.

Changes the allocated space of poly to exactly alloc coefficients. If the length exceeds alloc, the polynomial is first truncated to length alloc and normalised. For alloc = 0 the coefficients are freed and poly becomes zero.

Ensures that poly has space for at least len coefficients. If it has to grow, it grows to at least twice the old allocation, so that repeated calls with increasing lengths cost amortised linear time. The length and the coefficients are not changed.

Frees the memory used by poly, including that of its coefficients. The polynomial must be initialised again before it is used.

Sets the length of poly to newlen. If the length decreases, the dropped coefficients are set to zero (freeing their memory), which keeps the invariant that coefficients beyond the length are zero. No normalisation is done; poly must have space for newlen coefficients.

Decreases the length of poly until the leading coefficient is nonzero or the length is zero. This is the usual last step after writing coefficients with an underscore function.

Make the uninitialised trunc a read-only view of part of poly without copying: fmpz_poly_attach_truncate of the low \min(n, \operatorname{len}) coefficients, fmpz_poly_attach_shift of the coefficients from index n on, that is of \lfloor \mathit{poly} / x^n \rfloor (zero if n \ge \operatorname{len}). The view shares memory with poly; it must not be cleared, modified or used as an output, and becomes invalid when poly changes. A truncated view may have a zero leading coefficient, so it is not necessarily normalised.

Return the length and the degree of poly. The zero polynomial has length 0 and degree -1.

Return (or set x to) the coefficient of x^n in poly, which is zero if n is at least the length. The si and ui versions return the result of fmpz_get_si or fmpz_get_ui and are only meaningful when the coefficient fits.

Set the coefficient of x^n in poly to x, extending the polynomial with zero coefficients if n is beyond the length, and normalising if the leading coefficient is set to zero.

Sets poly1 to a copy of poly2.

Set poly to the constant polynomial c.

Set poly to the constant polynomial 0, respectively 1.

Swaps poly1 and poly2 in constant time by swapping their structures.

Sets the coefficients of x^i, \ldots, x^{j-1} to zero, clamping the range to the length of poly, and normalises.

Reduce modulo x^n: fmpz_poly_truncate truncates poly in place to length at most newlen, and fmpz_poly_set_trunc sets res to poly truncated to length n. Both normalise the result.

Set res to the reversal x^{n-1} f(1/x) of f = poly considered as a polynomial of length n, truncating or zero-padding it first. The underscore version writes n coefficients and requires 0 < \mathit{len} \le n; res may be equal to poly but must not partially overlap it. The non-underscore version normalises, so the result can be shorter than n.

Return whether poly1 and poly2 are equal, respectively equal modulo x^n.

Returns whether poly is the constant polynomial c (the zero polynomial if c = 0).

Return whether the polynomial is the constant 1. The underscore version allows zero padding and returns 0 for len = 0.

Returns whether poly is a unit of \mathbb{Z}[x], that is, the constant 1 or -1.

Returns whether poly is the generator x.

Set f to a random polynomial of length at most len whose coefficients have at most bits bits, with random signs (randtest), nonnegative (randtest_unsigned), or, for randtest_not_zero, not the zero polynomial, which requires len and bits to be positive. The coefficients are generated by fmpz_randtest, which favours special values (zero, small values, values close to powers of two), so these functions are meant for testing.

Sets p to a random polynomial of length at most len with coefficients of at most bits bits that has no real root.

Set pol to a random polynomial of length at most len with coefficients of at most bits bits that is irreducible over \mathbb{Z}. irreducible1 lifts a random irreducible polynomial modulo a random prime to \mathbb{Z} (an irreducible image modulo a prime that does not divide the leading coefficient proves irreducibility); irreducible2 factors a random polynomial and returns a random factor; the third function chooses one of the two at random.

Set poly to the polynomial given in plain format by the null-terminated string str. Return 0 on success and a nonzero value if the string is malformed, in which case fmpz_poly_set_str sets poly to zero and the underscore version leaves the array in an undefined state. The underscore version requires that poly has room for the number of coefficients given in the string.

Return a newly allocated string with the polynomial in plain format, respectively in pretty format with the variable name x. The string must be freed with flint_free.

Print the polynomial in plain format to stdout, respectively to file. Return a positive value on success and a nonpositive value on failure.

Print the polynomial in pretty format with the variable name x to stdout, respectively to file. Return a positive value on success and a nonpositive value on failure.

Read a polynomial in plain format from stdin, respectively from file, into poly. Return a positive value on success and a nonpositive value on failure.

Read a polynomial in pretty format from stdin, respectively from file, into poly, and set *x to a newly allocated string with the variable name found in the input, to be freed with flint_free. Return the number of characters read on success, and a nonpositive value on a read error or malformed input.

Prints the fields alloc and length and all alloc allocated coefficients of poly to stdout, for debugging.

Set (res, max(len1, len2)) to the sum, respectively difference, of (poly1, len1) and (poly2, len2). The output may be equal to either input.

Set res to poly1 + poly2, poly1 - poly2, respectively -poly.

Set res to the sum, respectively difference, of poly1 and poly2 truncated to length n.

Set res to poly + c, poly - c, respectively c - poly, for an integer constant c.

Sets res to the polynomial whose coefficients are the absolute values of those of poly.

Set poly1 to poly2 multiplied by x, respectively by 2^{exp}.

Set poly1 to poly1 + x * poly2, respectively poly1 - x * poly2.

Set poly1 to poly2 divided by x, rounding each coefficient towards -\infty (fdiv) or towards zero (tdiv). Division by zero raises an exception.

Set poly1 to poly2 divided by 2^{exp}, rounding each coefficient towards -\infty, respectively towards zero.

Set poly1 to poly2 divided by x, assuming that x divides every coefficient. This is not checked; the result is undefined otherwise. Division by zero raises an exception.

Set poly1 to poly2 with each coefficient reduced modulo x > 0, into [0, x), respectively into the symmetric range (-x/2, x/2].

Set res to poly multiplied by x^n. The underscore version writes len + n coefficients; res may be equal to poly.

Set res to \lfloor \mathit{poly} / x^n \rfloor, dropping the low n coefficients; the result is zero if n is at least the length. The underscore version requires \mathit{len} > n and writes len - n coefficients; res may be equal to poly, in which case the top n entries of the array are left unchanged.

Sets result to p(x^n), where p is input and n = inflation. For n = 0 the result is the constant p(1).

Sets result to p(x^{1/n}), where p is input and n = deflation, that is, keeps the coefficients of x^0, x^n, x^{2n}, \ldots. Requires that n \ge 1 divides fmpz_poly_deflation(input); other coefficients are dropped and the result is not necessarily normalised. Division by n = 0 raises an exception.

Return the largest n such that the polynomial is a polynomial in x^n, that is, the GCD of the exponents of its nonzero terms. Return 0 for the zero polynomial and 1 for a nonzero constant.

Returns the largest number of limbs needed to store the absolute value of a coefficient of poly, or 0 if poly is zero.

Returns the largest bit length b of the absolute value of a coefficient of poly if all coefficients are nonnegative, and -b otherwise.

Sets res to the height of poly, the largest absolute value of a coefficient (the \infty-norm), which is 0 for the zero polynomial.

Set res to \lfloor \|f\|_2 \rfloor, the integer square root of the sum of the squares of the coefficients.

Returns an upper bound, at most one too large, for the number of bits of \|f\|_2 / |\operatorname{lc}(f)|, the Euclidean norm of (poly, len) divided by the absolute value of its leading coefficient. Requires \mathit{len} > 0 and a nonzero leading coefficient. This is used for Landau–Mignotte bounds.

Returns the number of nonzero coefficients of (a, len).

Set res to the product of poly1 and poly2. The underscore version writes len1 + len2 - 1 coefficients, requires positive lengths (in either order), allows zero padding and does not allow res to overlap the inputs.

Set res to the product of poly1 and poly2 truncated to length n, that is, reduced modulo x^n. The underscore version writes n coefficients and requires positive lengths (in either order), 0 < n \le \mathit{len1} + \mathit{len2} - 1 and no overlap of res with the inputs.

Set res to the coefficients of x^{nlo}, \ldots, x^{nhi - 1} of the product of poly1 and poly2, shifted down to start at index 0, that is, to \lfloor (\mathit{poly1} \cdot \mathit{poly2} \bmod x^{nhi}) / x^{nlo} \rfloor. The non-underscore version clamps \mathit{nhi} to the length of the product and returns zero for an empty range. The underscore version writes \mathit{nhi} - \mathit{nlo} coefficients and requires positive lengths (in either order), 0 \le \mathit{nlo} < \mathit{nhi} \le \mathit{len1} + \mathit{len2} - 1 and no overlap of res with the inputs.

Sets res to a polynomial of length \mathit{len1} + \mathit{len2} - 1 whose top n coefficients are those of the product of poly1 and poly2; the coefficients below are arbitrary. Both operands are used at their full lengths.

Sets the coefficients res[start], ..., res[len1 + len2 - 2] to those of the product of (poly1, len1) and (poly2, len2), leaving res[0], ..., res[start - 1] unchanged. Requires positive lengths (in either order), 0 \le \mathit{start} < \mathit{len1} + \mathit{len2} - 1 and no overlap of res with the inputs.

Set rop to the square of op. The underscore version writes `2*len

• 1coefficients, requires $\mathit{len} > 0$, allows zero padding and does not allowropto overlapop`.

Set res to the square of poly truncated to length n. The underscore version writes n coefficients and requires \mathit{len} > 0, 0 < n \le 2 \mathit{len} - 1 and no overlap of res with poly.

Classical (schoolbook) multiplication: each output coefficient is computed as one dot product of fmpz values (_fmpz_vec_dot_general), and squares use the symmetry of the products. The cost is proportional to the number of coefficient products in the requested range. The underscore versions require positive lengths and do not allow res to overlap the inputs.

Set the coefficients of res from index start on to those of the product of poly1 and poly2 by the classical algorithm, and the coefficients below start to zero; the result has length \mathit{len1} + \mathit{len2} - 1, or is zero if start is at least that. The underscore version requires positive lengths and does not allow res to overlap the inputs.

Middle and full products computed on packed fixed-size limb arrays instead of fmpz values, with classical, Karatsuba and Karatsuba middle-product algorithms (_flint_mpn_poly_mulmid). Intended for lengths up to a few dozen and coefficients up to about a thousand bits.

As _fmpz_poly_mulmid_mpn, taking the signed bit bounds bits1 and bits2 of the coefficients, as returned by _fmpz_vec_max_bits, from the caller. The absolute values of the bounds need not be tight, but a bound must be negative if the polynomial has a negative coefficient, and a bound 0 means that the polynomial is zero.

Multiply by Toom–Cook evaluation and interpolation in the polynomial variable, at the points 0, \pm 1, \ldots, \pm p, one more point when the output length is odd, and infinity, using exactly \mathit{len1} + \mathit{len2} - 1 coefficient multiplications. Return 1 on success and 0, leaving res unchanged, if the output length \mathit{len1} + \mathit{len2} - 1 exceeds FMPZ_POLY_TOOM_SCALAR_N_MAX (20 on 64-bit and 13 on 32-bit machines), respectively \min(\mathit{nmax}, FMPZ_POLY_TOOM_SCALAR_N_MAX).

Compute the middle product window [\mathit{nlo}, \mathit{nhi}) as _fmpz_poly_mulmid, by Toom–Cook interpolation. With m, n the lengths of the operands after removing coefficients that cannot contribute and w the length of the window, the number of coefficient multiplications is the sum of the two smallest of m, n, w, minus one: either a full product of the trimmed operands, or, transposed, a middle product of the window against the shorter operand. Return 0, leaving res unchanged, when both routes exceed the length bound of _fmpz_poly_mul_toom_scalar_nmax.

Karatsuba multiplication with the Toom–Cook functions _fmpz_poly_mul_toom_scalar_nmax and _fmpz_poly_mulmid_toom_scalar_nmax as base cases, for short polynomials with large coefficients. Full products use Karatsuba with the longer operand cut into pieces of the length of the shorter one; low products use Mulders' short product [Mul2000], high products a low product of the reversed operands, and other windows the Karatsuba middle product of Hanrot, Quercia and Zimmermann [HQZ2004], so that a middle-product-shaped window costs about half a full product.

Multiply by Kronecker substitution: the coefficients are packed into bit fields of b_1 + b_2 + \lceil \log_2 (\min(\mathit{len1}, \mathit{len2}) + 1) \rceil bits, plus one for signs (where b_i bounds the bits of the coefficients), the two integers are multiplied with flint_mpn_mul (or flint_mpn_mulmid for windows, which computes only the needed limbs), and the product is unpacked. The underscore versions require positive lengths (in either order), allow zero padding and zero polynomials, and allow res to be equal to an input, since the inputs are packed before anything is written.

Multiply by a Schönhage–Strassen convolution (Schönhage–Strassen multiplication): each coefficient becomes one element of \mathbb{Z}/(2^N + 1)\mathbb{Z} large enough for the coefficients of the product, and the product is a convolution of power-of-two length computed with fft_convolution (or fft_convolution_sd_fft, whose pointwise products use fft_small). For a window that does not reach the top of the product, a cyclic convolution of a power-of-two length \ge \max(\mathit{nhi}, \mathit{len1} + \mathit{len2} - 1 - \mathit{nlo}) is used when it is shorter than the truncated transform, so that the wrapped-around terms land below \mathit{nlo} (fft_convolution_choose_mid). The underscore versions require positive lengths (in either order), allow zero padding and allow res to be equal to an input. The convolutions use flint_get_num_threads threads.

Classical multiplication in which the coefficient products are computed in the transform space of fft_small (Arithmetic in transform space): the coefficients of the shorter operand are transformed once, the longer operand runs through a window of transformed coefficients, and each output coefficient is a sum of pointwise products transformed back once. Squares share transforms and pair symmetric terms. This is efficient for short polynomials with very large coefficients. Return 1 on success and 0, writing nothing, when the transform representation is not available (small coefficients, or a build without fft_small). The underscore version takes the lengths in either order and does not allow res to overlap the inputs.

Precomputes the transform of poly2 for multiplications by polynomials of length at most len1 whose coefficients have at most bits1 bits. The transform length is the power of two 2^k \ge \mathit{len1} + \mathit{len2} - 1; products whose length is at most 2^{k-1} are computed with the same, too long, transform. bits1 may be negative, as returned by fmpz_poly_max_bits for polynomials with negative coefficients; only its absolute value is used.

Frees the memory used by pre.

Set res to the product of poly1 and the polynomial stored in pre, truncated to length n (trunc) for the mullow versions. The length and bit size of poly1 must not exceed those given to fmpz_poly_mul_SS_precache_init. The non-underscore versions use classical multiplication when one of the lengths or n is at most 2. The underscore version requires trunc to be at most the length of the product and does not allow output to overlap input1.

Adds the coefficients of (poly, len), negated if negate is -1, into consecutive fields of bit_size bits of the zero-initialised limb array arr, representing negative coefficients by borrows from the next field, so that the array holds \pm f(2^b) as a nonnegative integer when the leading coefficient times the sign is positive. negate must be 0 or -1, and bit_size must exceed the bit length of every coefficient.

Unpack the signed (respectively unsigned) coefficients in the fields \mathit{nlo}, \ldots, \mathit{nhi} - 1 of bit_size bits of arr, written by _fmpz_poly_bit_pack, to poly[0], ..., poly[nhi - nlo - 1], negating them if negate is -1. The signed version returns the final borrow: if it is nonzero, a coefficient \pm 1 (with the sign given by negate) has to be added at index nhi.

Sets f to \mathit{poly}(2^b) for b = bit_size, which must exceed the bit length of every coefficient plus one. The sign of f is that of the leading coefficient.

Set poly to the polynomial with signed (respectively nonnegative) coefficients of absolute value less than 2^{b-1} (respectively 2^b) such that \mathit{poly}(2^b) = f, for b = bit_size. The unsigned version requires f \ge 0.

Set res to poly raised to the power e, with 0^0 = 1. The function uses repeated squaring and multiplication for e \le 4, the binomial theorem for binomials, the J. C. P. Miller recurrence (_fmpz_poly_pow_multinomial) for short polynomials with small coefficients compared to e, and binary exponentiation otherwise. The underscore version requires e > 0 and \mathit{len} > 0, writes e(\mathit{len} - 1) + 1 coefficients and does not allow aliasing.

Sets res to poly raised to the power e \le 4 by squarings and one multiplication. Requires \mathit{len} > 0 and room for e(\mathit{len} - 1) + 1 coefficients; no aliasing.

Set res to poly raised to the power e by left-to-right binary exponentiation [Knu1997, §4.6.3]. The underscore version requires \mathit{len} > 0, e > 1 and room for e(\mathit{len} - 1) + 1 coefficients, and does not allow aliasing.

Set res to poly raised to the power e along an addition chain. The underscore version takes a star chain 1 = a_0 < a_1 < \cdots < a_n = e (each a_i is a_{i-1} + a_j for some j < i) with n > 1, requires \mathit{len} > 0 and does not allow aliasing. The non-underscore version uses a table of chains for e \le 148 and raises an exception for larger e.

Set res to (a + bx)^e for poly = a + bx of length exactly 2, by the binomial theorem. The non-underscore version raises an exception for any other length; the underscore version requires e > 0 and does not allow aliasing.

Set res to poly raised to the power e using the J. C. P. Miller recurrence [Knu1997, §4.6.1, exercise 16], [Zei1995]: if P(x) = \sum_{i=0}^m p_i x^i with p_0 \ne 0 and P(x)^e = \sum_k a_k x^k, then a_0 = p_0^e and

Each coefficient costs O(m) multiplications and one exact division. Low zero coefficients are removed first. The underscore version requires \mathit{len} > 0 and e > 0 and does not allow aliasing.

Set res to poly raised to the power e and truncated to length n, computed with truncated products throughout, which is much faster than powering and truncating; with 0^0 = 1 for n > 0. The underscore version reads n coefficients of poly (so it must be zero padded to length n), requires e, n > 0 and does not allow aliasing.

Set Q and R to the quotient and remainder of A by B as defined above. Division by zero raises an exception. The underscore version writes (Q, lenA - lenB + 1) and (R, lenA), requires \mathit{lenA} \ge \mathit{lenB} > 0, allows zero padding of A and does not allow aliasing. It uses the basecase algorithm for \mathit{lenB} < 6 and divide and conquer otherwise.

Set Q to the quotient of A by B as defined above, without computing the remainder. Division by zero raises an exception. The underscore version writes lenA - lenB + 1 coefficients, requires \mathit{lenA} \ge \mathit{lenB} > 0, allows zero padding of A and does not allow aliasing; exact is as for _fmpz_poly_divrem.

Set R to the remainder of A by B as defined above. Division by zero raises an exception. The underscore version writes lenA coefficients, requires \mathit{lenA} \ge \mathit{lenB} > 0 and does not allow aliasing.

Set Q to A / B, assuming that B divides A; this is not checked, and the result is undefined otherwise. Division by zero raises an exception. Short quotients and short divisors are computed from both ends at once, with coefficients no larger than those of Q; long ones use _fmpz_poly_div. The underscore version requires \mathit{lenA} \ge \mathit{lenB} > 0 and does not allow aliasing.

Return whether B divides A in \mathbb{Z}[x], and if so set Q to the quotient. Inexact divisions are usually detected quickly: by the constant coefficients, by the values at x = 1, and by the first inexact quotient coefficient. If B does not divide A, the value of Q is undefined. Division by zero raises an exception. The underscore version requires \mathit{lenA} \ge \mathit{lenB} > 0, room for \mathit{lenA} - \mathit{lenB} + 1 coefficients in Q and no aliasing.

Returns the largest k such that poly2^k divides poly1 and sets res to poly1 divided by poly2^k. The value of k is first bounded using the values at x = 1. Raises an exception if poly2 is zero or \pm 1.

Set Q to the quotient of A by x - c by synthetic division (Horner's rule); the remainder A(c) is discarded. The underscore version writes len - 1 coefficients; Q may be equal to A but must not partially overlap it.

Set Q to A / (qx - p) where c = p/q in lowest terms, assuming that c is a root of A; this is not checked. The underscore version writes len - 1 coefficients; Q may be equal to A but must not partially overlap it.

Set Q, R and d such that \ell^d A = BQ + R with \deg R < \deg B, where \ell = \operatorname{lc}(B) and 0 \le d \le \mathit{lenA} - \mathit{lenB} + 1. Factors \ell are introduced only where a quotient coefficient would otherwise not be an integer, so d is small when the division is nearly exact. These are the divide-and-conquer functions fmpz_poly_pseudo_divrem_divconquer under another name. Q and R must be distinct, and division by zero raises an exception.

As fmpz_poly_pseudo_divrem, returning only the quotient, respectively only the remainder, together with d.

Division with remainder by the schoolbook algorithm, with the semantics of fmpz_poly_divrem. The underscore version requires positive lengths, allows zero padding of A, and allows R to be equal to A; no other aliasing is allowed.

Quotient by the schoolbook algorithm, with the semantics of fmpz_poly_div; only the coefficients of the remainder that are needed for the quotient are updated. The underscore version takes a temporary array R of length lenA, or NULL to allocate one; R may be equal to A; no other aliasing is allowed.

Division with remainder, respectively quotient only, by recursive division of the top halves, so that the cost is O(M(n) \log n) coefficient operations for a product cost M(n), with the semantics of fmpz_poly_divrem and fmpz_poly_div. The underscore versions require \mathit{lenA} \ge \mathit{lenB} > 0, allow zero padding of A and do not allow aliasing.

The recursive steps of divide-and-conquer division for the balanced case \operatorname{len}(A) = 2 \mathit{lenB} - 1: they compute the quotient (Q, lenB), and divrem also the product (BQ, 2 lenB - 1) using the temporary (W, 2 lenB - 1); divremlow computes only the low \mathit{lenB} - 1 coefficients of BQ correctly (the array must still have room for 2 \mathit{lenB} - 1); div uses a temporary (temp, 2 lenB - 1) and does not compute BQ [Mul2000]. The low \mathit{lenB} - 1 coefficients of A are not read. They require \mathit{lenB} > 0 and do not allow aliasing; exact is as for _fmpz_poly_divrem.

Remainder by the schoolbook algorithm, with the semantics of fmpz_poly_rem. The underscore version writes lenA coefficients and allows R to be equal to A; no other aliasing is allowed.

Set B_inv to the inverse of the reversal of B as a power series of length n = \operatorname{len}(B), by Newton iteration, for use with fmpz_poly_div_preinv and fmpz_poly_divrem_preinv. B must have leading coefficient \pm 1 (for example, be monic). Division by zero raises an exception. The underscore version requires n > 0 and no aliasing.

Set Q to the quotient of A by B, given the precomputed inverse B_inv of B, using a truncated product with the inverse (and splitting A into blocks if its quotient is longer than B). B must have leading coefficient \pm 1. The underscore version requires \mathit{len1} \ge \mathit{len2}, room for \mathit{len1} - \mathit{len2} + 1 coefficients in Q, and no aliasing.

As fmpz_poly_div_preinv, also computing the remainder. The underscore version replaces the low \mathit{len2} - 1 coefficients of A by the remainder.

Compute the residues of x^i modulo the monic polynomial B of length len for 0 \le i < 2 \mathit{len} - 1, each as a vector of \mathit{len} - 1 coefficients. Division by zero raises an exception.

Free the residues computed by _fmpz_poly_powers_precompute, respectively fmpz_poly_powers_precompute.

Set R to A \bmod B for the monic B of length n, as a linear combination of the precomputed residues of x^i; this costs O(\operatorname{len}(A) \cdot n) coefficient operations and is fast for \operatorname{len}(A) < 2n. The underscore version reduces (A, m) in place, leaving the remainder in its low n - 1 coefficients, and does not allow aliasing.

Sets (res, n) to the low n coefficients of f / g modulo p, reduced into the symmetric range, assuming that the division is exact modulo p. Common low zero coefficients are removed first; the lowest nonzero coefficient of g must be invertible modulo p, which is not checked. Used by _fmpz_poly_factor_CLD_mat.

Sets (res, n) to the high n coefficients of f / g modulo p, reduced into the symmetric range, where f is the output of fmpz_poly_mulhigh_n applied to g and a polynomial of length n (only the top n coefficients of f are read). The leading coefficient of g must be invertible modulo p, which is not checked. Used by _fmpz_poly_factor_CLD_mat.

Pseudo-division with the semantics of fmpz_poly_pseudo_divrem, by the schoolbook algorithm, which multiplies the partial remainder by \ell only when a quotient coefficient would be inexact, respectively by divide and conquer. The underscore basecase version allows R to be equal to A; the divide-and-conquer version only sets the low \mathit{lenB} - 1 coefficients of (R, lenA) correctly and allows no aliasing. inv is as for _fmpz_poly_pseudo_divrem.

Pseudo-division with the exponent fixed at d = \max(0, \operatorname{len}(A) - \operatorname{len}(B) + 1), by Algorithm 3.1.2 of [Coh1996]: \ell^d A = BQ + R with \deg R < \deg B. This is the pseudo-remainder of the subresultant algorithm; it is quadratic and meant for short polynomials. The underscore versions require \mathit{lenA} \ge \mathit{lenB} > 0, room for \mathit{lenA} coefficients in R, and allow R to be equal to A; no other aliasing.

Set res to the nonnegative content of the polynomial; the content of the zero polynomial is zero. res may be one of the coefficients of poly in the non-underscore version, but not in the underscore version.

Set res to the primitive part of poly, with positive leading coefficient; the primitive part of zero is zero. The underscore version requires a nonzero polynomial and allows res to be equal to poly.

Set res to the GCD of poly1 and poly2 with positive leading coefficient. Common powers of x are removed first. Polynomials of length less than 6 use the subresultant algorithm; otherwise, when the coefficients have at most 40 bits in total, the heuristic GCD is tried, and the multimodular algorithm is used if it fails or the coefficients are larger. The underscore version requires \mathit{len1} \ge \mathit{len2} > 0 and writes len2 coefficients (zero padded); res may be equal to an input.

GCD by the multimodular algorithm: the primitive parts are reduced modulo batches of word-size primes, their monic GCDs modulo each prime are scaled to a common leading (or constant) coefficient and combined by the Chinese remainder theorem, and the candidate is certified by checking that it divides both inputs. The result is always correct. The underscore version has the conventions of _fmpz_poly_gcd.

Attempt to compute the GCD by the heuristic GCD algorithm GCDHEU [CGG1989], evaluating the primitive parts at a power of two, taking the GCD of the two integers and reconstructing a polynomial from it. Return 1 on success, when the reconstructed polynomial is verified to divide both inputs, and 0 on failure, in which case res is undefined. The underscore version has the conventions of _fmpz_poly_gcd.

GCD by the subresultant pseudo-remainder sequence, Algorithm 3.3.1 of [Coh1996], which keeps the intermediate coefficients small by exact divisions. It is quadratic in the degree and fast only for short polynomials. The underscore version has the conventions of _fmpz_poly_gcd.

Set r to the resultant of f and g and, if r \ne 0, find s, t with \deg s < \deg g, \deg t < \deg f and sf + tg = r. If r = 0 the function returns after setting r; s and t are then not computed and their values are undefined. The functions without _modular are inline wrappers of the multimodular algorithm, which computes the extended GCD modulo word-size primes and combines the cofactors by the Chinese remainder theorem until the identity is proved by a size bound.

Set res to the least common multiple fg / \gcd(f, g) of the two polynomials with nonnegative leading coefficient, so that fg = \pm \gcd(f, g) \operatorname{lcm}(f, g). The LCM is zero if either input is zero. The underscore version requires \mathit{len1} \ge \mathit{len2} > 0, writes \mathit{len1} + \mathit{len2} - 1 coefficients (zero padded) and does not allow aliasing.

Set res to the resultant of poly1 and poly2. The function uses the subresultant algorithm (fmpz_poly_resultant_euclidean) for short polynomials with small coefficients and the multimodular algorithm otherwise: when \mathit{len2} > 144 or \mathit{len2}^3 (b_1 + b_2) > 6 \cdot 10^6, where b_1, b_2 are the bit sizes of the coefficients. The underscore version requires \mathit{len1} \ge \mathit{len2} > 0.

Resultant by the multimodular algorithm [Col1971]: the contents are removed, the resultant of the primitive parts is computed modulo enough 64-bit primes to exceed twice the Hadamard bound \|f\|_2^{\deg g} \|g\|_2^{\deg f}, and the images are combined by the Chinese remainder theorem. The underscore version requires \mathit{len1} \ge \mathit{len2} > 0.

Set res to the resultant of poly1 and poly2 divided by divisor, assuming that the division is exact and that the quotient has at most nbits bits in absolute value. Only enough primes for nbits bits are used, instead of the general bound; this is used when the size of the result is known in advance, as for discriminants of number fields. If divisor is zero, res is set to zero. The underscore version requires \mathit{len1} \ge \mathit{len2} > 0. The number of primes is chosen so that their product exceeds 2^{\mathit{nbits} + 1}, as the signed reconstruction requires.

Resultant by the subresultant algorithm, Algorithm 3.3.7 of [Coh1996], with exact divisions that keep the coefficients of the remainders of the size of minors of the Sylvester matrix. The underscore version requires \mathit{len1} \ge \mathit{len2} > 0.

Set res to the discriminant of f = poly of degree n,

where \alpha_1, \ldots, \alpha_n are the roots of f. The discriminant of a polynomial of degree 1 is 1, and that of a constant or zero polynomial is defined to be 0. The underscore version requires \mathit{len} > 1.

Return whether the polynomial has no repeated factor of positive degree, that is, whether it is squarefree in \mathbb{Q}[x]; the content is ignored, so 4x + 4 counts as squarefree. Polynomials of length at most 2 are squarefree, including zero; quadratics are tested with the discriminant, and longer polynomials by checking that \gcd(f, f') is constant.

Sets res to f / \gcd(f, f') for f = poly, with positive leading coefficient: the product of the distinct irreducible factors of positive degree of f, times a constant. The squarefree part of a nonzero constant is 1 and that of zero is zero.

Set res to the derivative of poly. The underscore version writes len - 1 coefficients, handles \mathit{len} \le 1, and allows rpoly to be equal to poly.

Set res to the n-th derivative of poly. The underscore version writes len - n coefficients, handles \mathit{len} \le n, and allows rpoly to be equal to poly.

Set res to f(a) for an integer a, by Horner's rule for length at most 50 and by the divide-and-conquer algorithm otherwise. In the non-underscore version res may be equal to a; in both versions res must not be a coefficient of f, and in the underscore version it must not be a. See Evaluation.

Evaluate at an integer by Horner's rule, respectively by splitting f = f_0 + a^m f_1 recursively, which balances the sizes of the integer products so that they can use fast multiplication. The aliasing rules are those of fmpz_poly_evaluate_fmpz; the divide-and-conquer underscore version requires \mathit{len} \ge 1 and allows zero padding.

Set res to f(a) for a rational a, in lowest terms, by Horner's rule for short polynomials or large denominators, and by divide and conquer otherwise. The underscore version takes a = anum/aden in lowest terms with positive denominator and sets (rnum, rden); the outputs must not be aliased with the inputs or the coefficients. The non-underscore version allows res to be equal to a.

Evaluate at a rational number by Horner's rule, respectively by divide and conquer, with the conventions of fmpz_poly_evaluate_fmpq. The divide-and-conquer underscore version requires \mathit{len} \ge 1.

Return f(a) \bmod n for a word-size modulus n \ge 1, by Horner's rule with each coefficient reduced modulo n. The underscore version takes the precomputed inverse ninv = n_preinvert_limb(n).

Sets res[i] to f(a_i) for the n integers in a, one at a time with fmpz_poly_evaluate_fmpz.

Return an approximation of f(d) computed by Horner's rule in double precision, with no control of the error and no protection against overflow. Meant for quick estimates, for example for polynomials with nonnegative coefficients evaluated at d > 0.

Return m and set *exp to e such that m 2^e approximates f(d), respectively f(d \cdot 2^{\mathit{dexp}}), by Horner's rule in a floating-point format with a double mantissa and a separate exponent, which cannot overflow. As for fmpz_poly_evaluate_horner_d, the error is not controlled; cancellation can make the result meaningless for polynomials with coefficients of both signs.

Set poly to the polynomial f of degree less than n with f(x_i) = y_i for 0 \le i < n and return 1, if the x_i are distinct and f has integer coefficients; otherwise return 0. The newton version computes divided differences, failing at the first inexact division, and converts from the Newton basis; the multi_mod version interpolates modulo word-size primes (with a fast algorithm for many points) and combines the results by the Chinese remainder theorem until they stabilise and are checked. The default uses Newton interpolation for n \le 25 and chooses by size otherwise. The underscore versions write n coefficients.

As fmpz_poly_interpolate and fmpz_poly_interpolate_newton, but assuming that the x_i are distinct and that the interpolating polynomial has integer coefficients; this is not checked, and the result is undefined otherwise. The default uses Newton interpolation for n \le 70 and the multimodular algorithm otherwise.

As fmpz_poly_interpolate, but raises a FLINT_INEXACT exception if the x_i are not distinct or the interpolating polynomial does not have integer coefficients.

Convert (poly, n) in place between the monomial basis and the Newton basis 1, (x - r_0), (x - r_0)(x - r_1), \ldots, (x - r_0) \cdots (x - r_{n-2}) for the integers r_i in roots: monomial_to_newton finds the c_i with f = \sum_i c_i \prod_{j < i} (x - r_j) by repeated synthetic division, and newton_to_monomial evaluates such a sum by Horner's rule.

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

Set poly to (q_0 x - p_0) \cdots (q_{n-1} x - p_{n-1}) for the rational numbers x_i = p_i / q_i in xs, the primitive polynomial in \mathbb{Z}[x] with roots x_i when they are given in lowest terms. The underscore version writes n + 1 coefficients.

Allocate and free a subproduct tree for len linear factors. Level i of the tree is one array that holds the \lfloor \mathit{len}/2^i \rfloor products of 2^i linear factors, each stored with 2^i + 1 coefficients, followed by the product of the remaining factors if 2^i does not divide len.

Fills the tree allocated by _fmpz_poly_tree_alloc with the products of the linear factors q_i x - p_i for the roots p_i / q_i; the product at the top level is not computed.

Set res to the composition g(h(x)) of g = poly1 and h = poly2. Inner polynomials of the form ax^n + b use a Taylor shift and a scaling, short outer polynomials Horner's rule, and others the divide-and-conquer algorithm. The underscore version requires positive lengths, writes (\mathit{len1} - 1)(\mathit{len2} - 1) + 1 coefficients and does not allow aliasing. See Composition and Taylor shifts.

Composition by Horner's rule, respectively by the divide-and-conquer algorithm that splits g into blocks evaluated at h and combines them with the powers h^{2^k}. The underscore versions have the conventions of _fmpz_poly_compose.

Set g to f(x + c); the underscore version shifts (poly, n) in place. It uses Horner's scheme for length less than 64 and the divide-and-conquer algorithm otherwise.

Taylor shift by Horner's scheme, O(n^2) additions and multiplications by c (only additions for c = \pm 1).

Taylor shift by divide and conquer, f_0(x + c) + (x + c)^m f_1(x + c) with the powers of x + c computed by the binomial theorem; the two halves are shifted in parallel when threads are available. Short inputs use Horner's scheme, with a cutoff that grows with the size of the coefficients.

Taylor shift by a multimodular algorithm: the shift is computed modulo enough word-size primes for a bound on the result and combined by the Chinese remainder theorem, using flint_get_num_threads threads.

Set Qinv to the inverse of the power series Q modulo x^n, which requires the constant term of Q to be \pm 1; this is not checked. The basecase recurrence is used when Q or n is shorter than 64, Newton iteration otherwise. A zero Q or n = 0 raises an exception. The underscore version requires n \ge 1, writes n coefficients and does not allow aliasing.