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.