newFmpzPoly

Construct a new FmpzPoly

withFmpzPoly poly f

Execute f on poly

withNewFmpzPoly poly f

Execute f on a new FmpzPoly

fmpz_poly_init poly

Initialises poly for use, setting its length to zero. A corresponding call to fmpz_poly_clear must be made after finishing with the fmpz_poly_t to free the memory used by the polynomial.

fmpz_poly_init2 poly alloc

Initialises poly with space for at least alloc coefficients and sets the length to zero. The allocated coefficients are all set to zero.

fmpz_poly_realloc poly alloc

Reallocates the given polynomial to have space for alloc coefficients. If alloc is zero the polynomial is cleared and then reinitialised. If the current length is greater than alloc the polynomial is first truncated to length alloc.

fmpz_poly_fit_length poly len

If len is greater than the number of coefficients currently allocated, then the polynomial is reallocated to have space for at least len coefficients. No data is lost when calling this function.

The function efficiently deals with the case where fit_length is called many times in small increments by at least doubling the number of allocated coefficients when length is larger than the number of coefficients currently allocated.

fmpz_poly_clear poly

Clears the given polynomial, releasing any memory used. It must be reinitialised in order to be used again.

_fmpz_poly_normalise poly

Sets the length of poly so that the top coefficient is non-zero. If all coefficients are zero, the length is set to zero. This function is mainly used internally, as all functions guarantee normalisation.

_fmpz_poly_set_length poly newlen

Demotes the coefficients of poly beyond newlen and sets the length of poly to newlen.

fmpz_poly_attach_truncate trunc poly n

This function sets the uninitialised polynomial trunc to the low \(n\) coefficients of poly, or to poly if the latter doesn't have \(n\) coefficients. The polynomial trunc not be cleared or used as the output of any Flint functions.

fmpz_poly_attach_shift trunc poly n

This function sets the uninitialised polynomial trunc to the high coefficients of poly, i.e. the coefficients not among the low \(n\) coefficients of poly. If the latter doesn't have \(n\) coefficients trunc is set to the zero polynomial. The polynomial trunc not be cleared or used as the output of any Flint functions.

fmpz_poly_length poly

Returns the length of poly. The zero polynomial has length zero.

fmpz_poly_degree poly

Returns the degree of poly, which is one less than its length.

fmpz_poly_set poly1 poly2

Sets poly1 to equal poly2.

fmpz_poly_set_si poly c

Sets poly to the signed integer c.

fmpz_poly_set_ui poly c

Sets poly to the unsigned integer c.

fmpz_poly_set_fmpz poly c

Sets poly to the integer c.

_fmpz_poly_set_str poly str

Sets poly to the polynomial encoded in the null-terminated string str. Assumes that poly is allocated as a sufficiently large array suitable for the number of coefficients present in str.

Returns \(0\) if no error occurred. Otherwise, returns a non-zero value, in which case the resulting value of poly is undefined. If str is not null-terminated, calling this method might result in a segmentation fault.

fmpz_poly_set_str poly str

Imports a polynomial from a null-terminated string. If the string str represents a valid polynomial returns \(0\), otherwise returns \(1\).

Returns \(0\) if no error occurred. Otherwise, returns a non-zero value, in which case the resulting value of poly is undefined. If str is not null-terminated, calling this method might result in a segmentation fault.

_fmpz_poly_get_str poly len

Returns the plain FLINT string representation of the polynomial (poly, len).

fmpz_poly_get_str poly

Returns the plain FLINT string representation of the polynomial poly.

_fmpz_poly_get_str_pretty poly len x

Returns a pretty representation of the polynomial (poly, len) using the null-terminated string x as the variable name.

fmpz_poly_get_str_pretty poly x

Returns a pretty representation of the polynomial poly using the null-terminated string x as the variable name.

fmpz_poly_zero poly

Sets poly to the zero polynomial.

fmpz_poly_one poly

Sets poly to the constant polynomial one.

fmpz_poly_zero_coeffs poly i j

Sets the coefficients of \(x^i, \dotsc, x^{j-1}\) to zero.

fmpz_poly_swap poly1 poly2

Swaps poly1 and poly2. This is done efficiently without copying data by swapping pointers, etc.

_fmpz_poly_reverse res poly len n

Sets (res, n) to the reverse of (poly, n), where poly is in fact an array of length len. Assumes that 0 < len <= n. Supports aliasing of res and poly, but the behaviour is undefined in case of partial overlap.

fmpz_poly_reverse res poly n

This function considers the polynomial poly to be of length \(n\), notionally truncating and zero padding if required, and reverses the result. Since the function normalises its result res may be of length less than \(n\).

fmpz_poly_truncate poly newlen

If the current length of poly is greater than newlen, it is truncated to have the given length. Discarded coefficients are not necessarily set to zero.

fmpz_poly_set_trunc res poly n

Sets res to a copy of poly, truncated to length n.

fmpz_poly_randtest f state len bits

Sets \(f\) to a random polynomial with up to the given length and where each coefficient has up to the given number of bits. The coefficients are signed randomly.

fmpz_poly_randtest_unsigned f state len bits

Sets \(f\) to a random polynomial with up to the given length and where each coefficient has up to the given number of bits.

fmpz_poly_randtest_not_zero f state len bits

As for fmpz_poly_randtest except that len and bits may not be zero and the polynomial generated is guaranteed not to be the zero polynomial.

fmpz_poly_randtest_no_real_root p state len bits

Sets p to a random polynomial without any real root, whose length is up to len and where each coefficient has up to the given number of bits.

fmpz_poly_randtest_irreducible1 pol state len bits

fmpz_poly_randtest_irreducible2 pol state len bits

fmpz_poly_randtest_irreducible pol state len bits

Sets p to a random irreducible polynomial, whose length is up to len and where each coefficient has up to the given number of bits. There are two algorithms: irreducible1 generates an irreducible polynomial modulo a random prime number and lifts it to the integers; irreducible2 generates a random integer polynomial, factors it, and returns a random factor. The default function chooses randomly between these methods.

fmpz_poly_get_coeff_fmpz x poly n

Sets \(x\) to the \(n\)-th coefficient of poly. Coefficient numbering is from zero and if \(n\) is set to a value beyond the end of the polynomial, zero is returned.

fmpz_poly_get_coeff_si poly n

Returns coefficient \(n\) of poly as a slong. The result is undefined if the value does not fit into a slong. Coefficient numbering is from zero and if \(n\) is set to a value beyond the end of the polynomial, zero is returned.

fmpz_poly_get_coeff_ui poly n

Returns coefficient \(n\) of poly as a ulong. The result is undefined if the value does not fit into a ulong. Coefficient numbering is from zero and if \(n\) is set to a value beyond the end of the polynomial, zero is returned.

fmpz_poly_set_coeff_fmpz poly n x

Sets coefficient \(n\) of poly to the fmpz value x. Coefficient numbering starts from zero and if \(n\) is beyond the current length of poly then the polynomial is extended and zero coefficients inserted if necessary.

fmpz_poly_set_coeff_si poly n x

Sets coefficient \(n\) of poly to the slong value x. Coefficient numbering starts from zero and if \(n\) is beyond the current length of poly then the polynomial is extended and zero coefficients inserted if necessary.

fmpz_poly_set_coeff_ui poly n x

Sets coefficient \(n\) of poly to the ulong value x. Coefficient numbering starts from zero and if \(n\) is beyond the current length of poly then the polynomial is extended and zero coefficients inserted if necessary.

fmpz_poly_equal poly1 poly2

Returns \(1\) if poly1 is equal to poly2, otherwise returns \(0\). The polynomials are assumed to be normalised.

fmpz_poly_equal_trunc poly1 poly2 n

Return \(1\) if poly1 and poly2, notionally truncated to length \(n\) are equal, otherwise return \(0\).

fmpz_poly_is_one poly

Returns \(1\) if the polynomial is one and \(0\) otherwise.

fmpz_poly_is_unit poly

Returns \(1\) if the polynomial is the constant polynomial \(\pm 1\), and \(0\) otherwise.

fmpz_poly_is_gen poly

Returns \(1\) if the polynomial is the degree \(1\) polynomial \(x\), and \(0\) otherwise.

_fmpz_poly_add res poly1 len1 poly2 len2

Sets res to the sum of (poly1, len1) and (poly2, len2). It is assumed that res has sufficient space for the longer of the two polynomials.

fmpz_poly_add res poly1 poly2

Sets res to the sum of poly1 and poly2.

fmpz_poly_add_series res poly1 poly2 n

Notionally truncate poly1 and poly2 to length \(n\) and then set res to the sum.

_fmpz_poly_sub res poly1 len1 poly2 len2

Sets res to (poly1, len1) minus (poly2, len2). It is assumed that res has sufficient space for the longer of the two polynomials.

fmpz_poly_sub res poly1 poly2

Sets res to poly1 minus poly2.

fmpz_poly_sub_series res poly1 poly2 n

Notionally truncate poly1 and poly2 to length \(n\) and then set res to the sum.

fmpz_poly_neg res poly

Sets res to -poly.

fmpz_poly_scalar_abs res poly

Sets poly1 to the polynomial whose coefficients are the absolute value of those of poly2.

fmpz_poly_scalar_mul_fmpz poly1 poly2 x

Sets poly1 to poly2 times \(x\).

fmpz_poly_scalar_mul_si poly1 poly2 x

Sets poly1 to poly2 times the signed slong x.

fmpz_poly_scalar_mul_ui poly1 poly2 x

Sets poly1 to poly2 times the ulong x.

fmpz_poly_scalar_mul_2exp poly1 poly2 exp

Sets poly1 to poly2 times 2^exp.

fmpz_poly_scalar_addmul_si poly1 poly2 x

fmpz_poly_scalar_addmul_ui poly1 poly2 x

fmpz_poly_scalar_addmul_fmpz poly1 poly2 x

Sets poly1 to poly1 + x * poly2.

fmpz_poly_scalar_submul_fmpz poly1 poly2 x

Sets poly1 to poly1 - x * poly2.

fmpz_poly_scalar_fdiv_fmpz poly1 poly2 x

Sets poly1 to poly2 divided by the fmpz_t x, rounding coefficients down toward \(- \infty\).

fmpz_poly_scalar_fdiv_si poly1 poly2 x

Sets poly1 to poly2 divided by the slong x, rounding coefficients down toward \(- \infty\).

fmpz_poly_scalar_fdiv_ui poly1 poly2 x

Sets poly1 to poly2 divided by the ulong x, rounding coefficients down toward \(- \infty\).

fmpz_poly_scalar_fdiv_2exp poly1 poly2 x

Sets poly1 to poly2 divided by 2^x, rounding coefficients down toward \(- \infty\).

fmpz_poly_scalar_tdiv_fmpz poly1 poly2 x

Sets poly1 to poly2 divided by the fmpz_t x, rounding coefficients toward \(0\).

fmpz_poly_scalar_tdiv_si poly1 poly2 x

Sets poly1 to poly2 divided by the slong x, rounding coefficients toward \(0\).

fmpz_poly_scalar_tdiv_ui poly1 poly2 x

Sets poly1 to poly2 divided by the ulong x, rounding coefficients toward \(0\).

fmpz_poly_scalar_tdiv_2exp poly1 poly2 x

Sets poly1 to poly2 divided by 2^x, rounding coefficients toward \(0\).

fmpz_poly_scalar_divexact_fmpz poly1 poly2 x

Sets poly1 to poly2 divided by the fmpz_t x, assuming the division is exact for every coefficient.

fmpz_poly_scalar_divexact_si poly1 poly2 x

Sets poly1 to poly2 divided by the slong x, assuming the coefficient is exact for every coefficient.

fmpz_poly_scalar_divexact_ui poly1 poly2 x

Sets poly1 to poly2 divided by the ulong x, assuming the coefficient is exact for every coefficient.

fmpz_poly_scalar_mod_fmpz poly1 poly2 p

Sets poly1 to poly2, reducing each coefficient modulo \(p > 0\).

fmpz_poly_scalar_smod_fmpz poly1 poly2 p

Sets poly1 to poly2, symmetrically reducing each coefficient modulo \(p > 0\), that is, choosing the unique representative in the interval \((-p/2, p/2]\).

_fmpz_poly_remove_content_2exp pol len

Remove the 2-content of pol and return the number \(k\) that is the maximal non-negative integer so that \(2^k\) divides all coefficients of the polynomial. For the zero polynomial, \(0\) is returned.

_fmpz_poly_scale_2exp pol len k

Scale (pol, len) to \(p(2^k X)\) in-place and divide by the 2-content (so that the gcd of coefficients is odd). If k is negative the polynomial is multiplied by \(2^{kd}\).

_fmpz_poly_bit_pack arr poly len bit_size negate

Packs the coefficients of poly into bitfields of the given bit_size, negating the coefficients before packing if negate is set to \(-1\).

_fmpz_poly_bit_unpack poly len arr bit_size negate

Unpacks the polynomial of given length from the array as packed into fields of the given bit_size, finally negating the coefficients if negate is set to \(-1\). Returns borrow, which is nonzero if a leading term with coefficient \(\pm1\) should be added at position len of poly.

_fmpz_poly_bit_unpack_unsigned poly len arr bit_size

Unpacks the polynomial of given length from the array as packed into fields of the given bit_size. The coefficients are assumed to be unsigned.

fmpz_poly_bit_pack f poly bit_size

Packs poly into bitfields of size bit_size, writing the result to f. The sign of f will be the same as that of the leading coefficient of poly.

fmpz_poly_bit_unpack poly f bit_size

Unpacks the polynomial with signed coefficients packed into fields of size bit_size as represented by the integer f.

fmpz_poly_bit_unpack_unsigned poly f bit_size

Unpacks the polynomial with unsigned coefficients packed into fields of size bit_size as represented by the integer f. It is required that f is nonnegative.

_fmpz_poly_mul_classical res poly1 len1 poly2 len2

Sets (res, len1 + len2 - 1) to the product of (poly1, len1) and (poly2, len2).

Assumes len1 and len2 are positive. Allows zero-padding of the two input polynomials. No aliasing of inputs with outputs is allowed.

fmpz_poly_mul_classical res poly1 poly2

Sets res to the product of poly1 and poly2, computed using the classical or schoolbook method.

_fmpz_poly_mullow_classical res poly1 len1 poly2 len2 n

Sets (res, n) to the first \(n\) coefficients of (poly1, len1) multiplied by (poly2, len2).

Assumes 0 < n <= len1 + len2 - 1. Assumes neither len1 nor len2 is zero.

fmpz_poly_mullow_classical res poly1 poly2 n

Sets res to the first \(n\) coefficients of poly1 * poly2.

_fmpz_poly_mulhigh_classical res poly1 len1 poly2 len2 start

Sets the first start coefficients of res to zero and the remainder to the corresponding coefficients of (poly1, len1) * (poly2, len2).

Assumes start <= len1 + len2 - 1. Assumes neither len1 nor len2 is zero.

fmpz_poly_mulhigh_classical res poly1 poly2 start

Sets the first start coefficients of res to zero and the remainder to the corresponding coefficients of the product of poly1 and poly2.

_fmpz_poly_mulmid_classical res poly1 len1 poly2 len2

Sets res to the middle len1 - len2 + 1 coefficients of the product of (poly1, len1) and (poly2, len2), i.e. the coefficients from degree len2 - 1 to len1 - 1 inclusive. Assumes that len1 >= len2 > 0.

fmpz_poly_mulmid_classical res poly1 poly2

Sets res to the middle len(poly1) - len(poly2) + 1 coefficients of poly1 * poly2, i.e. the coefficient from degree len2 - 1 to len1 - 1 inclusive. Assumes that len1 >= len2.

_fmpz_poly_mul_karatsuba res poly1 len1 poly2 len2

Sets (res, len1 + len2 - 1) to the product of (poly1, len1) and (poly2, len2). Assumes len1 >= len2 > 0. Allows zero-padding of the two input polynomials. No aliasing of inputs with outputs is allowed.

fmpz_poly_mul_karatsuba res poly1 poly2

Sets res to the product of poly1 and poly2.

_fmpz_poly_mullow_karatsuba_n res poly1 poly2 n

Sets res to the product of poly1 and poly2 and truncates to the given length. It is assumed that poly1 and poly2 are precisely the given length, possibly zero padded. Assumes \(n\) is not zero.

fmpz_poly_mullow_karatsuba_n res poly1 poly2 n

Sets res to the product of poly1 and poly2 and truncates to the given length.

_fmpz_poly_mulhigh_karatsuba_n res poly1 poly2 len

Sets res to the product of poly1 and poly2 and truncates at the top to the given length. The first len - 1 coefficients are set to zero. It is assumed that poly1 and poly2 are precisely the given length, possibly zero padded. Assumes len is not zero.

fmpz_poly_mulhigh_karatsuba_n res poly1 poly2 len

Sets the first len - 1 coefficients of the result to zero and the remaining coefficients to the corresponding coefficients of the product of poly1 and poly2. Assumes poly1 and poly2 are at most of the given length.

_fmpz_poly_mul_KS res poly1 len1 poly2 len2

Sets (res, len1 + len2 - 1) to the product of (poly1, len1) and (poly2, len2).

Places no assumptions on len1 and len2. Allows zero-padding of the two input polynomials. Supports aliasing of inputs and outputs.

fmpz_poly_mul_KS res poly1 poly2

Sets res to the product of poly1 and poly2.

_fmpz_poly_mullow_KS res poly1 len1 poly2 len2 n

Sets (res, n) to the lowest \(n\) coefficients of the product of (poly1, len1) and (poly2, len2).

Assumes that len1 and len2 are positive, but does allow for the polynomials to be zero-padded. The polynomials may be zero, too. Assumes \(n\) is positive. Supports aliasing between res, poly1 and poly2.

fmpz_poly_mullow_KS res poly1 poly2 n

Sets res to the lowest \(n\) coefficients of the product of poly1 and poly2.

_fmpz_poly_mul_SS output input1 length1 input2 length2

Sets (output, length1 + length2 - 1) to the product of (input1, length1) and (input2, length2).

We must have len1 > 1 and len2 > 1. Allows zero-padding of the two input polynomials. Supports aliasing of inputs and outputs.

fmpz_poly_mul_SS res poly1 poly2

Sets res to the product of poly1 and poly2. Uses the Schönhage-Strassen algorithm.

_fmpz_poly_mullow_SS output input1 length1 input2 length2 n

Sets (res, n) to the lowest \(n\) coefficients of the product of (poly1, len1) and (poly2, len2).

Assumes that len1 and len2 are positive, but does allow for the polynomials to be zero-padded. We must have len1 > 1 and len2 > 1. Assumes \(n\) is positive. Supports aliasing between res, poly1 and poly2.

fmpz_poly_mullow_SS res poly1 poly2 n

Sets res to the lowest \(n\) coefficients of the product of poly1 and poly2.

_fmpz_poly_mul res poly1 len1 poly2 len2

Sets (res, len1 + len2 - 1) to the product of (poly1, len1) and (poly2, len2). Assumes len1 >= len2 > 0. Allows zero-padding of the two input polynomials. Does not support aliasing between the inputs and the output.

fmpz_poly_mul res poly1 poly2

Sets res to the product of poly1 and poly2. Chooses an optimal algorithm from the choices above.

_fmpz_poly_mullow res poly1 len1 poly2 len2 n

Sets (res, n) to the lowest \(n\) coefficients of the product of (poly1, len1) and (poly2, len2).

Assumes len1 >= len2 > 0 and 0 < n <= len1 + len2 - 1. Allows for zero-padding in the inputs. Does not support aliasing between the inputs and the output.

fmpz_poly_mullow res poly1 poly2 n

Sets res to the lowest \(n\) coefficients of the product of poly1 and poly2.

fmpz_poly_mulhigh_n res poly1 poly2 n

Sets the high \(n\) coefficients of res to the high \(n\) coefficients of the product of poly1 and poly2, assuming the latter are precisely \(n\) coefficients in length, zero padded if necessary. The remaining \(n - 1\) coefficients may be arbitrary.

_fmpz_poly_mulhigh res poly1 len1 poly2 len2 start

Sets all but the low \(n\) coefficients of \(res\) to the corresponding coefficients of the product of \(poly1\) of length \(len1\) and \(poly2\) of length \(len2\), the remaining coefficients being arbitrary. It is assumed that \(len1 >= len2 > 0\) and that \(0 < n < len1 + len2 - 1\). Aliasing of inputs is not permitted.

fmpz_poly_mul_SS_precache_init pre len1 bits1 poly2

Precompute the FFT of poly2 to enable repeated multiplication of poly2 by polynomials whose length does not exceed len1 and whose number of bits per coefficient does not exceed bits1.

The value bits1 may be negative, i.e. it may be the result of calling fmpz_poly_max_bits. The function only considers the absolute value of bits1.

Suppose len2 is the length of poly2 and len = len1 + len2 - 1 is the maximum output length of a polynomial multiplication using pre. Then internally len is rounded up to a power of two, \(2^n\) say. The truncated FFT algorithm is used to smooth performance but note that it can only do this in the range \((2^{n-1}, 2^n]\). Therefore, it may be more efficient to recompute \(pre\) for cases where the output length will fall below \(2^{n-1} + 1\). Otherwise the implementation will zero pad them up to that length.

Note that the Schoenhage-Strassen algorithm is only efficient for polynomials with relatively large coefficients relative to the length of the polynomials.

Also note that there are no restrictions on the polynomials. In particular the polynomial whose FFT is being precached does not have to be either longer or shorter than the polynomials it is to be multiplied by.

fmpz_poly_mul_precache_clear pre

Clear the space allocated by fmpz_poly_mul_SS_precache_init.

_fmpz_poly_mullow_SS_precache output input1 len1 pre trunc

Write into output the first trunc coefficients of the polynomial (input1, len1) by the polynomial whose FFT was precached by fmpz_poly_mul_SS_precache_init and stored in pre.

For performance reasons it is recommended that all polynomials be truncated to at most trunc coefficients if possible.

fmpz_poly_mullow_SS_precache res poly1 pre n

Set res to the product of poly1 by the polynomial whose FFT was precached by fmpz_poly_mul_SS_precache_init (and stored in pre). The result is truncated to \(n\) coefficients (and normalised).

There are no restrictions on the length of poly1 other than those given in the call to fmpz_poly_mul_SS_precache_init.

fmpz_poly_mul_SS_precache res poly1 pre

Set res to the product of poly1 by the polynomial whose FFT was precached by fmpz_poly_mul_SS_precache_init (and stored in pre).

There are no restrictions on the length of poly1 other than those given in the call to fmpz_poly_mul_SS_precache_init.

_fmpz_poly_sqr_KS rop op len

Sets (rop, 2*len - 1) to the square of (op, len), assuming that len > 0.

Supports zero-padding in (op, len). Does not support aliasing.

fmpz_poly_sqr_KS rop op

Sets rop to the square of the polynomial op using Kronecker segmentation.

_fmpz_poly_sqr_karatsuba rop op len

Sets (rop, 2*len - 1) to the square of (op, len), assuming that len > 0.

Supports zero-padding in (op, len). Does not support aliasing.

fmpz_poly_sqr_karatsuba rop op

Sets rop to the square of the polynomial op using the Karatsuba multiplication algorithm.

_fmpz_poly_sqr_classical rop op len

Sets (rop, 2*len - 1) to the square of (op, len), assuming that len > 0.

Supports zero-padding in (op, len). Does not support aliasing.

fmpz_poly_sqr_classical rop op

Sets rop to the square of the polynomial op using the classical or schoolbook method.

_fmpz_poly_sqr rop op len

Sets (rop, 2*len - 1) to the square of (op, len), assuming that len > 0.

Supports zero-padding in (op, len). Does not support aliasing.

fmpz_poly_sqr rop op

Sets rop to the square of the polynomial op.

_fmpz_poly_sqrlow_KS res poly len n

Sets (res, n) to the lowest \(n\) coefficients of the square of (poly, len).

Assumes that len is positive, but does allow for the polynomial to be zero-padded. The polynomial may be zero, too. Assumes \(n\) is positive. Supports aliasing between res and poly.

fmpz_poly_sqrlow_KS res poly n

Sets res to the lowest \(n\) coefficients of the square of poly.

_fmpz_poly_sqrlow_karatsuba_n res poly n

Sets (res, n) to the square of (poly, n) truncated to length \(n\), which is assumed to be positive. Allows for poly to be zero-padded.

fmpz_poly_sqrlow_karatsuba_n res poly n

Sets res to the square of poly and truncates to the given length.

_fmpz_poly_sqrlow_classical res poly len n

Sets (res, n) to the first \(n\) coefficients of the square of (poly, len).

Assumes that 0 < n <= 2 * len - 1.

fmpz_poly_sqrlow_classical res poly n

Sets res to the first \(n\) coefficients of the square of poly.

_fmpz_poly_sqrlow res poly len n

Sets (res, n) to the lowest \(n\) coefficients of the square of (poly, len).

Assumes len1 >= len2 > 0 and 0 < n <= 2 * len - 1. Allows for zero-padding in the input. Does not support aliasing between the input and the output.

fmpz_poly_sqrlow res poly n

Sets res to the lowest \(n\) coefficients of the square of poly.

_fmpz_poly_pow_multinomial res poly len e

Computes res = poly^e. This uses the J.C.P. Miller pure recurrence as follows:

If \(\ell\) is the index of the lowest non-zero coefficient in poly, as a first step this method zeros out the lowest \(e \ell\) coefficients of res. The recurrence above is then used to compute the remaining coefficients.

Assumes len > 0, e > 0. Does not support aliasing.

fmpz_poly_pow_multinomial res poly e

Computes res = poly^e using a generalisation of binomial expansion called the J.C.P. Miller pure recurrence [1], [2]. If \(e\) is zero, returns one, so that in particular 0^0 = 1.

The formal statement of the recurrence is as follows. Write the input polynomial as \(P(x) = p_0 + p_1 x + \dotsb + p_m x^m\) with \(p_0 \neq 0\) and let

\[`\] \[P(x)^n = a(n, 0) + a(n, 1) x + \dotsb + a(n, mn) x^{mn}.\]

Then \(a(n, 0) = p_0^n\) and, for all \(1 \leq k \leq mn\),

\[`\] \[a(n, k) = (k p_0)^{-1} \sum_{i = 1}^m p_i \bigl( (n + 1) i - k \bigr) a(n, k-i).\]

1

D. Knuth, The Art of Computer Programming Vol. 2, Seminumerical Algorithms, Third Edition (Reading, Massachusetts: Addison-Wesley, 1997)

2

D. Zeilberger, The J.C.P. Miller Recurrence for Exponentiating a Polynomial, and its q-Analog, Journal of Difference Equations and Applications, 1995, Vol. 1, pp. 57--60

_fmpz_poly_pow_binomial res poly e

Computes res = poly^e when poly is of length 2, using binomial expansion.

Assumes \(e > 0\). Does not support aliasing.

fmpz_poly_pow_binomial res poly e

Computes res = poly^e when poly is of length \(2\), using binomial expansion.

If the length of poly is not \(2\), raises an exception and aborts.

_fmpz_poly_pow_addchains res poly len a n

Given a star chain \(1 = a_0 < a_1 < \dotsb < a_n = e\) computes res = poly^e.

A star chain is an addition chain \(1 = a_0 < a_1 < \dotsb < a_n\) such that, for all \(i > 0\), \(a_i = a_{i-1} + a_j\) for some \(j < i\).

Assumes that \(e > 2\), or equivalently \(n > 1\), and len > 0. Does not support aliasing.

fmpz_poly_pow_addchains res poly e

Computes res = poly^e using addition chains whenever \(0 \leq e \leq 148\).

If \(e > 148\), raises an exception and aborts.

_fmpz_poly_pow_binexp res poly len e

Sets res = poly^e using left-to-right binary exponentiation as described on p. 461 of [Knu1997].

Assumes that len > 0, e > 1. Assumes that res is an array of length at least e*(len - 1) + 1. Does not support aliasing.

fmpz_poly_pow_binexp res poly e

Computes res = poly^e using the binary exponentiation algorithm. If \(e\) is zero, returns one, so that in particular 0^0 = 1.

_fmpz_poly_pow_small res poly len e

Sets res = poly^e whenever \(0 \leq e \leq 4\).

Assumes that len > 0 and that res is an array of length at least e*(len - 1) + 1. Does not support aliasing.

_fmpz_poly_pow res poly len e

Sets res = poly^e, assuming that e, len > 0 and that res has space for e*(len - 1) + 1 coefficients. Does not support aliasing.

fmpz_poly_pow res poly e

Computes res = poly^e. If \(e\) is zero, returns one, so that in particular 0^0 = 1.

_fmpz_poly_pow_trunc res poly e n

Sets (res, n) to (poly, n) raised to the power \(e\) and truncated to length \(n\).

Assumes that \(e, n > 0\). Allows zero-padding of (poly, n). Does not support aliasing of any inputs and outputs.

fmpz_poly_pow_trunc res poly e n

Notationally raises poly to the power \(e\), truncates the result to length \(n\) and writes the result in res. This is computed much more efficiently than simply powering the polynomial and truncating.

Thus, if \(n = 0\) the result is zero. Otherwise, whenever \(e = 0\) the result will be the constant polynomial equal to \(1\).

This function can be used to raise power series to a power in an efficient way.

_fmpz_poly_shift_left res poly len n

Sets (res, len + n) to (poly, len) shifted left by \(n\) coefficients.

Inserts zero coefficients at the lower end. Assumes that len and \(n\) are positive, and that res fits len + n elements. Supports aliasing between res and poly.

fmpz_poly_shift_left res poly n

Sets res to poly shifted left by \(n\) coeffs. Zero coefficients are inserted.

_fmpz_poly_shift_right res poly len n

Sets (res, len - n) to (poly, len) shifted right by \(n\) coefficients.

Assumes that len and \(n\) are positive, that len > n, and that res fits len - n elements. Supports aliasing between res and poly, although in this case the top coefficients of poly are not set to zero.

fmpz_poly_shift_right res poly n

Sets res to poly shifted right by \(n\) coefficients. If \(n\) is equal to or greater than the current length of poly, res is set to the zero polynomial.

fmpz_poly_max_limbs poly

Returns the maximum number of limbs required to store the absolute value of coefficients of poly. If poly is zero, returns \(0\).

fmpz_poly_max_bits poly

Computes the maximum number of bits \(b\) required to store the absolute value of coefficients of poly. If all the coefficients of poly are non-negative, \(b\) is returned, otherwise \(-b\) is returned.

fmpz_poly_height height poly

Computes the height of poly, defined as the largest of the absolute values of the coefficients of poly. Equivalently, this gives the infinity norm of the coefficients. If poly is zero, the height is \(0\).