Malachite for FLINT Users: Rational Polynomials
This page maps the functions of FLINT’s rational polynomial type, fmpq_poly_t, onto their
Malachite counterpart:
RationalPolynomial,
from the malachite-q crate. It follows the organization of the
fmpq_poly.h chapter of the FLINT manual, as of FLINT
3.6.0. Its companion is
Malachite for FLINT Users: Integer Polynomials, which maps
the same operations over \(\mathbb{Z}\); the
conventions of the fmpz page
apply here too, and the mapping index lists the whole family.
The page covers all 32 sections of the chapter and maps every documented public function — 145 of them, plus the two type rows — as 44 ✓, 19 ≈, 15 —, and 69 ✗. Functions whose names begin with an underscore (96 of them) are omitted, as on the companion pages. Two of the chapter’s headings are both called “Powering” and cover unrelated subjects; they appear here as Powering and precomputed powers for remainders.
Conventions
The fmpq_poly representation
Both libraries store a rational polynomial as an integer numerator polynomial over a single shared
denominator rather than as a list of rational coefficients:
RationalPolynomial
is an
IntegerPolynomial
numerator over a
Natural
denominator.
Canonical form, and where it lives
FLINT calls a polynomial canonical when the numerator and denominator are coprime, the
denominator is positive, the numerator has no trailing zero coefficient, and the zero polynomial
is written \(0/1\). In Malachite all four conditions hold for every value: the first two by the
choice of a
Natural
denominator and an
IntegerPolynomial
numerator, the other two by the constructors. Canonical form is therefore an invariant of the type
rather than a state to be restored, which is why fmpq_poly_canonicalise and
fmpq_poly_is_canonical have no counterparts. In FLINT several public functions can leave a
value non-canonical: writing through the numref/denref accessors, set_str on input not in
lowest terms, the add_can/sub_can family with can = 0, and rem_powers_precomp.
What the representation costs
No coefficient is stored as such: the coefficient of \(x^i\) is \(n_i/d\), so where
IntegerPolynomial
lends a coefficient by reference, this type builds a
Rational and
returns it by value, and where that type lends a slice this one returns a
Vec.
Categories
Each function falls into one of four categories:
| meaning | |
|---|---|
| ✓ | A Malachite function does the same thing. |
| ≈ | A Malachite function serves the same purpose, but its specification differs. The notes say how. |
| — | No counterpart is needed, either because Rust handles it for you or because it is outside Malachite’s scope. The notes say which. |
| ✗ | Malachite does not fully support this yet, but will in a future version. |
Types, macros and constants
| FLINT | Malachite | |
|---|---|---|
| ✓ | fmpq_poly_struct |
RationalPolynomial |
| — | fmpq_poly_t |
The _t form exists so a polynomial can be passed and mutated through a pointer, which & and
&mut already provide, so only the struct has a counterpart.
Memory management
| FLINT | Malachite | |
|---|---|---|
| ✓ | void fmpq_poly_init (fmpq_poly_t poly) |
RationalPolynomial::ZERO |
| — | void fmpq_poly_init2 (fmpq_poly_t poly, slong alloc) |
|
| — | void fmpq_poly_realloc (fmpq_poly_t poly, slong alloc) |
|
| — | void fmpq_poly_fit_length (fmpq_poly_t poly, slong len) |
|
| — | void fmpq_poly_clear (fmpq_poly_t poly) |
|
| — | void fmpq_poly_canonicalise (fmpq_poly_t poly) |
|
| — | int fmpq_poly_is_canonical (const fmpq_poly_t poly) |
init gives the zero polynomial,
RationalPolynomial::ZERO;
init2, realloc and fit_length are capacity management, which a
Vec does for itself, and clear
is Drop. canonicalise and
is_canonical are unneeded because canonical form is an invariant of the type.
Polynomial parameters
| FLINT | Malachite | |
|---|---|---|
| ≈ | slong fmpq_poly_degree (const fmpq_poly_t poly) |
degree |
| ✓ | slong fmpq_poly_length (const fmpq_poly_t poly) |
len |
fmpq_poly_degree returns length - 1, so \(-1\) for the zero polynomial, where
degree
returns an Option<u64>
with None for
zero. fmpq_poly_length is
len,
not
to_coefficients_asc().len(),
which builds every coefficient.
Accessing the numerator and denominator
| FLINT | Malachite | |
|---|---|---|
| ≈ | fmpz * fmpq_poly_numref (fmpq_poly_t poly) |
numerator_ref, mutate_numerator |
| ≈ | fmpz_t fmpq_poly_denref (fmpq_poly_t poly) |
denominator_ref, mutate_denominator |
| ≈ | void fmpq_poly_get_numerator (fmpz_poly_t res, const fmpq_poly_t poly) |
into_numerator_and_denominator |
| ≈ | void fmpq_poly_get_denominator (fmpz_t den, const fmpq_poly_t poly) |
into_numerator_and_denominator |
numref and denref are writable, so a caller can leave the polynomial non-canonical through
them.
numerator_ref
and
denominator_ref
are read-only. To modify them, use
mutate_numerator,
mutate_denominator, or
mutate_numerator_and_denominator,
which pass the halves to a closure and reduce the polynomial when it returns, so it never becomes
non-canonical. The copying pair map to
into_numerator_and_denominator,
which returns both halves at once and consumes the polynomial. Despite get_numerator’s
description, the numerator need not be primitive: \((2x + 4)/3\) is canonical.
Random testing
| FLINT | Malachite | |
|---|---|---|
| ≈ | void fmpq_poly_randtest (fmpq_poly_t f, flint_rand_t state, slong len, flint_bitcnt_t bits) |
random_rational_polynomials, striped_random_rational_polynomials |
| ≈ | void fmpq_poly_randtest_unsigned (fmpq_poly_t f, flint_rand_t state, slong len, flint_bitcnt_t bits) |
random_rational_polynomials_from_iterators |
| ≈ | void fmpq_poly_randtest_not_zero (fmpq_poly_t f, flint_rand_t state, slong len, flint_bitcnt_t bits) |
random_rational_polynomials_min_degree |
FLINT bounds the length and bit size; Malachite’s generators take mean parameters with unbounded
support. randtest_not_zero is
random_rational_polynomials_min_degree
with a minimum degree of 0, and randtest_unsigned is
random_rational_polynomials_from_iterators
over non-negative
Rationals, since
there is no non-negative rational type.
Assignment, swap, negation
| FLINT | Malachite | |
|---|---|---|
| ✓ | void fmpq_poly_set (fmpq_poly_t poly1, const fmpq_poly_t poly2) |
Clone |
| ✓ | void fmpq_poly_set_si (fmpq_poly_t poly, slong x) |
From |
| ✓ | void fmpq_poly_set_ui (fmpq_poly_t poly, ulong x) |
From |
| ✓ | void fmpq_poly_set_fmpz (fmpq_poly_t poly, const fmpz_t x) |
From |
| ✓ | void fmpq_poly_set_fmpq (fmpq_poly_t poly, const fmpq_t x) |
From |
| ✓ | void fmpq_poly_set_fmpz_poly (fmpq_poly_t rop, const fmpz_poly_t op) |
From |
| ✓ | void fmpq_poly_zero (fmpq_poly_t poly) |
RationalPolynomial::ZERO |
| ✓ | void fmpq_poly_one (fmpq_poly_t poly) |
one |
| ✓ | void fmpq_poly_swap (fmpq_poly_t poly1, fmpq_poly_t poly2) |
mem::swap |
| ✓ | char * fmpq_poly_get_str_pretty (const fmpq_poly_t poly, const char * var) |
Display, to_string_with |
| ≈ | char * fmpq_poly_get_str (const fmpq_poly_t poly) |
Serialize |
| ≈ | int fmpq_poly_set_str (fmpq_poly_t poly, const char * str) |
Deserialize |
| ✓ | void fmpq_poly_neg (fmpq_poly_t poly1, const fmpq_poly_t poly2) |
Neg |
| ✗ | void fmpq_poly_inv (fmpq_poly_t poly1, const fmpq_poly_t poly2) |
|
| ✓ | void fmpq_poly_truncate (fmpq_poly_t poly, slong n) |
truncate_assign |
| ✓ | void fmpq_poly_set_trunc (fmpq_poly_t res, const fmpq_poly_t poly, slong n) |
truncate |
| ✓ | void fmpq_poly_reverse (fmpq_poly_t res, const fmpq_poly_t poly, slong n) |
reverse |
| ✗ | void fmpq_poly_get_slice (fmpq_poly_t rop, const fmpq_poly_t op, slong i, slong j) |
|
| ✗ | void fmpq_poly_get_nmod_poly (nmod_poly_t rop, const fmpq_poly_t op) |
|
| ✗ | void fmpq_poly_get_nmod_poly_den (nmod_poly_t rop, const fmpq_poly_t op, int den) |
|
| ✗ | void fmpq_poly_set_nmod_poly (fmpq_poly_t rop, const nmod_poly_t op) |
Assignment is Clone, the
scalar constructors are one blanket
From over anything convertible
into a Rational,
swap is mem::swap, and
From<IntegerPolynomial>
covers set_fmpz_poly. get_str and set_str use the plain one-rational-per-coefficient format
described under input and output, which differs from Malachite’s
serialisation, hence ≈; set_str guarantees canonical form only when every coefficient in the
string is in lowest terms, whereas
FromStr and
Deserialize reduce as they build.
fmpq_poly_inv calls abort() unless its argument is a nonzero constant \(c\), whose inverse is
RationalPolynomial::from(c.reciprocal()). fmpq_poly_reverse is
reverse,
or reverse_assign
in place. get_slice(i, j) keeps the terms of degree \(i\) through \(j - 1\) in place, which is
p.truncate(j) - p.truncate(i).
Getting and setting coefficients
| FLINT | Malachite | |
|---|---|---|
| ✓ | void fmpq_poly_get_coeff_fmpq (fmpq_t x, const fmpq_poly_t poly, slong n) |
coefficient |
| — | void fmpq_poly_get_coeff_fmpz (fmpz_t x, const fmpq_poly_t poly, slong n) |
|
| ≈ | void fmpq_poly_set_coeff_si (fmpq_poly_t poly, slong n, slong x) |
mutate_coefficient |
| ≈ | void fmpq_poly_set_coeff_ui (fmpq_poly_t poly, slong n, ulong x) |
mutate_coefficient |
| ≈ | void fmpq_poly_set_coeff_fmpz (fmpq_poly_t poly, slong n, const fmpz_t x) |
mutate_coefficient |
| ≈ | void fmpq_poly_set_coeff_fmpq (fmpq_poly_t poly, slong n, const fmpq_t x) |
mutate_coefficient |
get_coeff_fmpz returns the \(n\)th coefficient of the numerator, which is the coefficient only
when the denominator is 1; it is p.numerator_ref().coefficient(n).
mutate_coefficient
hands its closure the coefficient as a
Rational and
rebuilds the polynomial around what comes back, since the common denominator may change.
Building a polynomial coefficient by coefficient is quadratic;
from_coefficients_asc
takes them all at once.
Comparison
| FLINT | Malachite | |
|---|---|---|
| ✓ | int fmpq_poly_equal (const fmpq_poly_t poly1, const fmpq_poly_t poly2) |
PartialEq |
| ✓ | int fmpq_poly_cmp (const fmpq_poly_t left, const fmpq_poly_t right) |
ShortlexRationalPolynomial |
| ✓ | int fmpq_poly_is_zero (const fmpq_poly_t poly) |
p == 0u32 (PartialEq) |
| ✓ | int fmpq_poly_is_one (const fmpq_poly_t poly) |
p == 1u32 (PartialEq) |
| ✓ | int fmpq_poly_equal_trunc (const fmpq_poly_t poly1, const fmpq_poly_t poly2, slong n) |
eq_truncated |
| ✓ | int fmpq_poly_is_gen (const fmpq_poly_t poly) |
x |
fmpq_poly_cmp orders first by degree and then by coefficients from highest to lowest, which is
the Ord of
ShortlexRationalPolynomial
(and
ShortlexRationalPolynomialRef
for borrowing); the default
Ord on
RationalPolynomial
is the asymptotic order. is_gen is *p == RationalPolynomial::x(). A RationalPolynomial
compares with a value of any primitive integer type, p == c holding exactly when p is the
constant polynomial c, so is_zero and is_one are *p == 0u32 and *p == 1u32.
Addition and subtraction
| FLINT | Malachite | |
|---|---|---|
| ✓ | void fmpq_poly_add (fmpq_poly_t res, const fmpq_poly_t poly1, const fmpq_poly_t poly2) |
Add, AddAssign |
| ✓ | void fmpq_poly_sub (fmpq_poly_t res, const fmpq_poly_t poly1, const fmpq_poly_t poly2) |
Sub, SubAssign |
| — | void fmpq_poly_add_can (fmpq_poly_t res, const fmpq_poly_t poly1, const fmpq_poly_t poly2, int can) |
|
| — | void fmpq_poly_sub_can (fmpq_poly_t res, const fmpq_poly_t poly1, const fmpq_poly_t poly2, int can) |
|
| ✓ | void fmpq_poly_add_series (fmpq_poly_t res, const fmpq_poly_t poly1, const fmpq_poly_t poly2, slong n) |
add_truncated |
| ✓ | void fmpq_poly_sub_series (fmpq_poly_t res, const fmpq_poly_t poly1, const fmpq_poly_t poly2, slong n) |
sub_truncated |
| — | void fmpq_poly_add_series_can (fmpq_poly_t res, const fmpq_poly_t poly1, const fmpq_poly_t poly2, slong n, int can) |
|
| — | void fmpq_poly_sub_series_can (fmpq_poly_t res, const fmpq_poly_t poly1, const fmpq_poly_t poly2, slong n, int can) |
The _can variants take a flag selecting whether the result is canonicalised; with can = 0 the
result may not be in lowest terms. Malachite has no such flag because every value is reduced, so
those rows are —. The _series pair are
add_truncated
and
sub_truncated.
Scalar multiplication and division
| FLINT | Malachite | |
|---|---|---|
| ✗ | void fmpq_poly_scalar_mul_si (fmpq_poly_t rop, const fmpq_poly_t op, slong c) |
|
| ✗ | void fmpq_poly_scalar_mul_ui (fmpq_poly_t rop, const fmpq_poly_t op, ulong c) |
|
| ✗ | void fmpq_poly_scalar_mul_fmpz (fmpq_poly_t rop, const fmpq_poly_t op, const fmpz_t c) |
|
| ✗ | void fmpq_poly_scalar_mul_fmpq (fmpq_poly_t rop, const fmpq_poly_t op, const fmpq_t c) |
|
| ✗ | void fmpq_poly_scalar_div_si (fmpq_poly_t rop, const fmpq_poly_t op, slong c) |
|
| ✗ | void fmpq_poly_scalar_div_ui (fmpq_poly_t rop, const fmpq_poly_t op, ulong c) |
|
| ✗ | void fmpq_poly_scalar_div_fmpz (fmpq_poly_t rop, const fmpq_poly_t op, const fmpz_t c) |
|
| ✗ | void fmpq_poly_scalar_div_fmpq (fmpq_poly_t rop, const fmpq_poly_t op, const fmpq_t c) |
To scale by a rational c, multiply by RationalPolynomial::from(c), or by
RationalPolynomial::from(c.reciprocal()) to divide; scalar_div assumes a nonzero divisor
without checking, whereas the reciprocal of zero panics. Scaling by a power of 2 is << and >>:
Shl
multiplies and
Shr
divides, a negative signed amount doing the opposite.
Multiplication
| FLINT | Malachite | |
|---|---|---|
| ✓ | void fmpq_poly_mul (fmpq_poly_t res, const fmpq_poly_t poly1, const fmpq_poly_t poly2) |
* |
| ✓ | void fmpq_poly_mullow (fmpq_poly_t res, const fmpq_poly_t poly1, const fmpq_poly_t poly2, slong n) |
mul_truncated |
| ✗ | void fmpq_poly_addmul (fmpq_poly_t rop, const fmpq_poly_t op1, const fmpq_poly_t op2) |
|
| ✗ | void fmpq_poly_submul (fmpq_poly_t rop, const fmpq_poly_t op1, const fmpq_poly_t op2) |
addmul and submul are unfused in FLINT; write rop += op1 * op2 and rop -= op1 * op2.
There is no sqr; Malachite’s squaring functions are
square
and, for mullow,
square_truncated.
Powering
| FLINT | Malachite | |
|---|---|---|
| ✓ | void fmpq_poly_pow (fmpq_poly_t res, const fmpq_poly_t poly, ulong e) |
pow |
| ✓ | void fmpq_poly_pow_trunc (fmpq_poly_t res, const fmpq_poly_t poly, ulong e, slong n) |
pow_truncated |
This section is exponentiation; the chapter’s other “Powering” is the
precomputed-remainder scheme. \(0^0 = 1\), matching
Pow
for Natural.
Shifting
| FLINT | Malachite | |
|---|---|---|
| ✓ | void fmpq_poly_shift_left (fmpq_poly_t res, const fmpq_poly_t poly, slong n) |
mul_power_of_x |
| ✓ | void fmpq_poly_shift_right (fmpq_poly_t res, const fmpq_poly_t poly, slong n) |
div_power_of_x |
Shifting by \(n\) multiplies or divides by \(x^n\), the right shift discarding the low
coefficients. In Malachite << and >> mean scaling by a power of two, not this operation.
Euclidean division
| FLINT | Malachite | |
|---|---|---|
| ✗ | void fmpq_poly_divrem (fmpq_poly_t Q, fmpq_poly_t R, const fmpq_poly_t poly1, const fmpq_poly_t poly2) |
|
| ✗ | void fmpq_poly_div (fmpq_poly_t Q, const fmpq_poly_t poly1, const fmpq_poly_t poly2) |
|
| ✗ | void fmpq_poly_rem (fmpq_poly_t R, const fmpq_poly_t poly1, const fmpq_poly_t poly2) |
fmpq_poly_divrem, div and rem are ordinary Euclidean division in \(\mathbb{Q}[x]\):
\(A = BQ + R\) with \(\deg R < \deg B\). Over \(\mathbb{Q}\) both of the integer chapter’s
compromises hold at once:
| dividend | remainder | |
|---|---|---|
fmpz_poly_divrem |
\(A\) itself | may keep high-degree terms, reduced modulo \(\ell\) |
fmpz_poly_pseudo_divrem |
scaled to \(\ell^d A\) | \(\deg R < \deg B\), as in a field |
Powering (precomputed powers for remainders)
| FLINT | Malachite | |
|---|---|---|
| ✗ | void fmpq_poly_powers_precompute (fmpq_poly_powers_precomp_t pinv, fmpq_poly_t poly) |
|
| — | void fmpq_poly_powers_clear (fmpq_poly_powers_precomp_t pinv) |
|
| ✗ | void fmpq_poly_rem_powers_precomp (fmpq_poly_t R, const fmpq_poly_t A, const fmpq_poly_t B, const fmpq_poly_powers_precomp_t B_inv) |
powers_clear is — because freeing a cache is
Drop.
Divisibility testing
| FLINT | Malachite | |
|---|---|---|
| ✗ | int fmpq_poly_divides (fmpq_poly_t q, const fmpq_poly_t poly1, const fmpq_poly_t poly2) |
|
| ✗ | slong fmpq_poly_remove (fmpq_poly_t q, const fmpq_poly_t poly1, const fmpq_poly_t poly2) |
divides returns a flag and the quotient; a zero divisor divides a zero dividend and nothing else,
the convention
DivisibleBy
uses for Malachite’s integer types. remove returns the multiplicity of poly2 in poly1 and the
remaining cofactor, and aborts if poly2 is zero or a nonzero constant.
Power series division
| FLINT | Malachite | |
|---|---|---|
| ✗ | void fmpq_poly_inv_series_newton (fmpq_poly_t res, const fmpq_poly_t poly, slong n) |
|
| ✗ | void fmpq_poly_inv_series (fmpq_poly_t res, const fmpq_poly_t poly, slong n) |
|
| ✗ | void fmpq_poly_div_series (fmpq_poly_t Q, const fmpq_poly_t A, const fmpq_poly_t B, slong n) |
inv_series and inv_series_newton are the same function, and div_series computes
\(A/B \bmod x^n\). All three require only a nonzero constant term in the divisor, where the
integer chapter requires \(\pm 1\), and abort otherwise.
Greatest common divisor
| FLINT | Malachite | |
|---|---|---|
| ✗ | void fmpq_poly_gcd (fmpq_poly_t G, const fmpq_poly_t A, const fmpq_poly_t B) |
|
| ✗ | void fmpq_poly_xgcd (fmpq_poly_t G, fmpq_poly_t S, fmpq_poly_t T, const fmpq_poly_t A, const fmpq_poly_t B) |
|
| ✗ | void fmpq_poly_lcm (fmpq_poly_t L, const fmpq_poly_t A, const fmpq_poly_t B) |
|
| ✗ | void fmpq_poly_resultant (fmpq_t r, const fmpq_poly_t f, const fmpq_poly_t g) |
|
| — | void fmpq_poly_resultant_div (fmpq_t r, const fmpq_poly_t f, const fmpq_poly_t g, const fmpz_t div, slong nbits) |
resultant_div is — because it asks the caller to supply facts about the result (exact
divisibility by div, a bit bound), an internal entry point rather than an operation.
Discriminant
| FLINT | Malachite | |
|---|---|---|
| ✗ | void fmpq_poly_discriminant (fmpq_t res, const fmpq_poly_t poly) |
For \(f\) of degree \(n\) the result is \((-1)^{n(n-1)/2} \operatorname{res}(f, f')/\operatorname{lc}(f)\), for the polynomial as given rather than its monic associate; for \(f = A/d\) it equals \(\operatorname{disc}(A)/d^{2n-2}\). Constants and the zero polynomial have discriminant 0, and every linear polynomial has discriminant 1.
Derivative and integral
| FLINT | Malachite | |
|---|---|---|
| ✓ | void fmpq_poly_derivative (fmpq_poly_t res, const fmpq_poly_t poly) |
derivative |
| ✓ | void fmpq_poly_nth_derivative (fmpq_poly_t res, const fmpq_poly_t poly, ulong n) |
nth_derivative |
| ✓ | void fmpq_poly_integral (fmpq_poly_t res, const fmpq_poly_t poly) |
integral |
The constant of integration is zero.
Square roots
| FLINT | Malachite | |
|---|---|---|
| ✗ | void fmpq_poly_sqrt_series (fmpq_poly_t res, const fmpq_poly_t f, slong n) |
|
| ✗ | void fmpq_poly_invsqrt_series (fmpq_poly_t res, const fmpq_poly_t f, slong n) |
Both require the constant term to be exactly 1 and abort otherwise, even when it is another nonzero square; for a constant term \(c^2\), use \(\sqrt{f} = c\sqrt{f/c^2}\), so that \(\sqrt{4 + x} = 2\sqrt{1 + x/4}\).
Power sums
| FLINT | Malachite | |
|---|---|---|
| ✗ | void fmpq_poly_power_sums (fmpq_poly_t res, const fmpq_poly_t poly, slong n) |
|
| ✗ | void fmpq_poly_power_sums_to_fmpz_poly (fmpz_poly_t res, const fmpq_poly_t Q) |
|
| ✗ | void fmpq_poly_power_sums_to_poly (fmpq_poly_t res, const fmpq_poly_t Q) |
power_sums accepts any nonzero polynomial, not only a monic one. The two inverses differ only in
normalisation: power_sums_to_poly returns the monic polynomial and power_sums_to_fmpz_poly the
primitive one with positive leading coefficient, so either converts to the other with
make_monic
or
primitive_part.
Both read the degree from the constant term \(p_0\) without checking that it is a non-negative
integer.
Transcendental functions
| FLINT | Malachite | |
|---|---|---|
| ✗ | void fmpq_poly_log_series (fmpq_poly_t res, const fmpq_poly_t f, slong n) |
|
| ✗ | void fmpq_poly_exp_series (fmpq_poly_t res, const fmpq_poly_t h, slong n) |
|
| ✗ | void fmpq_poly_exp_expinv_series (fmpq_poly_t res1, fmpq_poly_t res2, const fmpq_poly_t h, slong n) |
|
| ✗ | void fmpq_poly_atan_series (fmpq_poly_t res, const fmpq_poly_t f, slong n) |
|
| ✗ | void fmpq_poly_atanh_series (fmpq_poly_t res, const fmpq_poly_t f, slong n) |
|
| ✗ | void fmpq_poly_asin_series (fmpq_poly_t res, const fmpq_poly_t f, slong n) |
|
| ✗ | void fmpq_poly_asinh_series (fmpq_poly_t res, const fmpq_poly_t f, slong n) |
|
| ✗ | void fmpq_poly_tan_series (fmpq_poly_t res, const fmpq_poly_t f, slong n) |
|
| ✗ | void fmpq_poly_sin_series (fmpq_poly_t res, const fmpq_poly_t f, slong n) |
|
| ✗ | void fmpq_poly_cos_series (fmpq_poly_t res, const fmpq_poly_t f, slong n) |
|
| ✗ | void fmpq_poly_sin_cos_series (fmpq_poly_t res1, fmpq_poly_t res2, const fmpq_poly_t f, slong n) |
|
| ✗ | void fmpq_poly_sinh_series (fmpq_poly_t res, const fmpq_poly_t f, slong n) |
|
| ✗ | void fmpq_poly_cosh_series (fmpq_poly_t res, const fmpq_poly_t f, slong n) |
|
| ✗ | void fmpq_poly_sinh_cosh_series (fmpq_poly_t res1, fmpq_poly_t res2, const fmpq_poly_t f, slong n) |
|
| ✗ | void fmpq_poly_tanh_series (fmpq_poly_t res, const fmpq_poly_t f, slong n) |
All fifteen require constant term 0, except log_series, which requires constant term 1; these are
the only rational points at which the functions take rational values. exp_expinv_series,
sin_cos_series and sinh_cosh_series return two results from one call, as
SinCos
does for scalars.
Orthogonal polynomials
| FLINT | Malachite | |
|---|---|---|
| ✗ | void fmpq_poly_legendre_p (fmpq_poly_t poly, ulong n) |
|
| ✗ | void fmpq_poly_laguerre_l (fmpq_poly_t poly, ulong n) |
|
| ✗ | void fmpq_poly_gegenbauer_c (fmpq_poly_t poly, ulong n, const fmpq_t a) |
These are the families with non-integral coefficients; Chebyshev, Hermite and shifted Legendre
polynomials are in the
integer chapter. gegenbauer_c
takes a rational parameter \(\alpha\), with \(C^{(1/2)}_n\) the Legendre polynomial; its
documented domain \(\alpha > 0\) is not enforced, and \(\alpha = 0\) returns 0.
Evaluation
| FLINT | Malachite | |
|---|---|---|
| ✓ | void fmpq_poly_evaluate_fmpz (fmpq_t res, const fmpq_poly_t poly, const fmpz_t a) |
evaluate |
| ✓ | void fmpq_poly_evaluate_fmpq (fmpq_t res, const fmpq_poly_t poly, const fmpq_t a) |
evaluate |
evaluate
is implemented at both a
Rational and an
Integer, and
returns a Rational either way, as both FLINT functions do.
Interpolation
| FLINT | Malachite | |
|---|---|---|
| ✗ | void fmpq_poly_interpolate_fast (fmpq_poly_t poly, const fmpq * xs, const fmpq * ys, slong n) |
|
| ✗ | void fmpq_poly_interpolate_barycentric (fmpq_poly_t poly, const fmpq * xs, const fmpq * ys, slong n) |
|
| ✗ | void fmpq_poly_interpolate_multi_mod (fmpq_poly_t poly, const fmpq * xs, const fmpq * ys, slong n) |
|
| ✗ | int fmpq_poly_interpolate_fmpq_vec (fmpq_poly_t poly, const fmpq * xs, const fmpq * ys, slong n) |
|
| ✗ | int fmpq_poly_interpolate_fmpz_fmpq_vec (fmpq_poly_t poly, const fmpz * xs, const fmpq * ys, slong n) |
|
| ✗ | int fmpq_poly_interpolate_fmpz_vec (fmpq_poly_t poly, const fmpz * xs, const fmpz * ys, slong n) |
fast, barycentric and multi_mod return void and assume distinct \(x_i\); the three
interpolate_*_vec functions return 0 when two \(x_i\) coincide. The interpolant always exists
over \(\mathbb{Q}\), so unlike
fmpz_poly_interpolate distinct points never
fail.
Composition
| FLINT | Malachite | |
|---|---|---|
| ✗ | void fmpq_poly_compose (fmpq_poly_t res, const fmpq_poly_t poly1, const fmpq_poly_t poly2) |
|
| ✗ | void fmpq_poly_rescale (fmpq_poly_t res, const fmpq_poly_t poly, const fmpq_t a) |
When the inner polynomial is \(x^k\), compose is
compose_power_of_x.
Power series composition
| FLINT | Malachite | |
|---|---|---|
| ✗ | void fmpq_poly_compose_series (fmpq_poly_t res, const fmpq_poly_t poly1, const fmpq_poly_t poly2, slong n) |
|
| ✗ | void fmpq_poly_compose_series_horner (fmpq_poly_t res, const fmpq_poly_t poly1, const fmpq_poly_t poly2, slong n) |
|
| ✗ | void fmpq_poly_compose_series_brent_kung (fmpq_poly_t res, const fmpq_poly_t poly1, const fmpq_poly_t poly2, slong n) |
|
| ✗ | void fmpq_poly_compose_series_kinoshita_li (fmpq_poly_t res, const fmpq_poly_t poly1, const fmpq_poly_t poly2, slong n) |
The inner polynomial must have zero constant term. Three sections place a condition on a constant term, for three different reasons:
| condition | why | |
|---|---|---|
| Transcendental functions | 0, or 1 for log |
the function’s value there must be rational |
| Square roots | 1 | the value there must be a square in \(\mathbb{Q}\) |
| Power series composition | 0 | otherwise \(g(h) \bmod x^n\) is not defined at all |
Power series reversion
| FLINT | Malachite | |
|---|---|---|
| ✗ | void fmpq_poly_revert_series (fmpq_poly_t res, const fmpq_poly_t poly, slong n) |
|
| — | void fmpq_poly_revert_series_lagrange (fmpq_poly_t res, const fmpq_poly_t poly, slong n) |
|
| ✗ | void fmpq_poly_revert_series_lagrange_fast (fmpq_poly_t res, const fmpq_poly_t poly, slong n) |
|
| ✗ | void fmpq_poly_revert_series_newton (fmpq_poly_t res, const fmpq_poly_t poly, slong n) |
revert_series_lagrange is — because FLINT’s dispatcher never selects it.
Gaussian content
| FLINT | Malachite | |
|---|---|---|
| ✓ | void fmpq_poly_content (fmpq_t res, const fmpq_poly_t poly) |
content |
| ≈ | void fmpq_poly_primitive_part (fmpq_poly_t res, const fmpq_poly_t poly) |
primitive_part |
| ✓ | int fmpq_poly_is_monic (const fmpq_poly_t poly) |
is_monic |
| ✓ | void fmpq_poly_make_monic (fmpq_poly_t res, const fmpq_poly_t poly) |
make_monic |
The content is the non-negative rational \(c\) for which \(f/c\) is a primitive integer
polynomial, \(\operatorname{cont}(A)/d\) for \(f = A/d\). The primitive part has non-negative
leading coefficient, so
\(f = \operatorname{sgn}(\operatorname{lc}(f)) \cdot \operatorname{cont}(f) \cdot \operatorname{pp}(f)\).
primitive_part is ≈ only in its type: the result always has denominator 1, and Malachite
returns an IntegerPolynomial.
The zero polynomial is not monic, and make_monic(0) = 0.
Square-free
| FLINT | Malachite | |
|---|---|---|
| ✗ | int fmpq_poly_is_squarefree (const fmpq_poly_t poly) |
The test is for repeated roots, that is, for a square factor of positive degree; the denominator is irrelevant, and the zero polynomial counts as square-free.
Input and output
| FLINT | Malachite | |
|---|---|---|
| ✓ | int fmpq_poly_print_pretty (const fmpq_poly_t poly, const char * var) |
Display, to_string_with |
| ✓ | int fmpq_poly_fprint_pretty (FILE * file, const fmpq_poly_t poly, const char * var) |
Display |
| ≈ | int fmpq_poly_print (const fmpq_poly_t poly) |
Serialize, to_coefficients_asc |
| ≈ | int fmpq_poly_fprint (FILE * file, const fmpq_poly_t poly) |
Serialize |
| ≈ | int fmpq_poly_read (fmpq_poly_t poly) |
Deserialize, from_coefficients_asc |
| ≈ | int fmpq_poly_fread (FILE * file, fmpq_poly_t poly) |
Deserialize |
The pretty format is
Display and
to_string_with,
which serve stdout, a file and a
String alike;
FromStr and
from_string_with
read it back. The plain print/read format is a length followed by one rational per
coefficient (4 1/3 -1/3 0 5/3 for \((5x^3 - x + 1)/3\)), whereas Malachite serialises a
numerator polynomial and a denominator under the names n and d, hence ≈; to read or write
FLINT’s format, go through
from_coefficients_asc
and
to_coefficients_asc.