Malachite for FLINT Users: Integer Polynomials
This page maps the functions of FLINT’s integer polynomial type, fmpz_poly_t, onto their
Malachite counterpart:
IntegerPolynomial,
from the malachite-nz crate. It follows the organization of the
fmpz_poly.h chapter of the FLINT manual, as of FLINT
3.6.0, and is a companion to Malachite for FLINT Users: Integers,
whose conventions, including word types and aliasing,
apply here as well; the mapping index lists the whole family.
Every section of the chapter is mapped below: 254 rows across 49 sections, of which 51 are ✓, 22 ⚙, 26 ≈, 25 —, and 130 ✗. Functions whose names begin with an underscore are omitted, as on the fmpq page, except in Newton basis and Subproduct trees, which have no public functions.
Conventions
The fmpz_poly representation
An fmpz_poly_struct holds coeffs (ascending, so coeffs[i] belongs to \(x^i\)), alloc, and
length. An
IntegerPolynomial
is a single
Vec<Integer> in the same
ascending order; alloc and length are the
Vec’s own.
FLINT expects every input to be normalised (length zero or nonzero leading coefficient) and
leaves that to the caller. In Malachite it is an invariant: trailing zero coefficients are never
stored, the field is private, and
from_coefficients_asc
drops trailing zeros as it builds.
Coefficients that are not Integers
Malachite has four polynomial types differing only in their coefficients:
IntegerPolynomial
over \(\mathbb{Z}\),
NaturalPolynomial
over \(\mathbb{N}\),
UnsignedPolynomial
with u64 coefficients (in
malachite-base), and
RationalPolynomial
over \(\mathbb{Q}\), the counterpart of fmpq_poly and the subject of its own page. Every row
below names the
IntegerPolynomial
version; the other types use the same method names wherever the coefficients allow it.
NaturalPolynomial and UnsignedPolynomial hold residues for modular arithmetic (the Mod* and
ModPowerOf2* traits), which is the only arithmetic UnsignedPolynomial has. Every modular
operation checks that its arguments are reduced and panics otherwise.
Categories
Each function falls into one of five categories:
| meaning | |
|---|---|
| ✓ | A Malachite function does the same thing. |
| ≈ | A Malachite function serves the same purpose, but its specification differs. The notes say how. |
| ⚙ | Malachite does not expose this algorithm or helper; the Malachite column or the notes say what to call instead. |
| — | 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 | |
|---|---|---|
| ✓ | fmpz_poly_struct |
IntegerPolynomial |
| — | fmpz_poly_t |
fmpz_poly_t is the pass-by-reference device that & and &mut already are.
Polynomial parameters
| FLINT | Malachite | |
|---|---|---|
| ✓ | slong fmpz_poly_length (const fmpz_poly_t poly) |
len |
| ≈ | slong fmpz_poly_degree (const fmpz_poly_t poly) |
degree |
len
returns a u64. fmpz_poly_degree
returns \(-1\) for the zero polynomial;
degree
returns
Option<u64>,
and the zero polynomial’s degree is
None, so a
comparison against \(-1\) becomes a match on None.
Assignment and basic manipulation
| FLINT | Malachite | |
|---|---|---|
| ✓ | void fmpz_poly_set (fmpz_poly_t poly1, const fmpz_poly_t poly2) |
Clone |
| ✓ | void fmpz_poly_set_si (fmpz_poly_t poly, slong c) |
From |
| ✓ | void fmpz_poly_set_ui (fmpz_poly_t poly, ulong c) |
From |
| ✓ | void fmpz_poly_set_fmpz (fmpz_poly_t poly, const fmpz_t c) |
From |
| ≈ | int fmpz_poly_set_str (fmpz_poly_t poly, const char * str) |
from_coefficients_asc, Deserialize |
| ≈ | char * fmpz_poly_get_str (const fmpz_poly_t poly) |
coefficients_asc, Serialize |
| ✓ | char * fmpz_poly_get_str_pretty (const fmpz_poly_t poly, const char * x) |
to_string_with, Display |
| ✓ | void fmpz_poly_zero (fmpz_poly_t poly) |
IntegerPolynomial::ZERO |
| ✓ | void fmpz_poly_one (fmpz_poly_t poly) |
one |
| ✓ | void fmpz_poly_zero_coeffs (fmpz_poly_t poly, slong i, slong j) |
zero_coefficients |
| ✓ | void fmpz_poly_swap (fmpz_poly_t poly1, fmpz_poly_t poly2) |
mem::swap |
| ✓ | void fmpz_poly_reverse (fmpz_poly_t res, const fmpz_poly_t poly, slong n) |
reverse |
| ✓ | void fmpz_poly_truncate (fmpz_poly_t poly, slong newlen) |
truncate_assign |
| ✓ | void fmpz_poly_set_trunc (fmpz_poly_t res, const fmpz_poly_t poly, slong n) |
truncate |
fmpz_poly_set is Clone, or
a move when the original is not needed afterwards. The three scalar constructors are one
generic From over anything
convertible into an
Integer.
IntegerPolynomial::ZERO
is an associated constant, while
one
(like
two,
negative_one,
and
x)
is a function; the
One
trait is not implemented.
FLINT’s plain string format is a serialization (the length, then the coefficients in ascending
order, so \(5x^3 - 1\) is 4 -1 0 0 5, with the zero polynomial written 0). Malachite has no
such format; the counterparts are
Serialize and
Deserialize under the
enable_serde feature, or the pair
coefficients_asc
/
from_coefficients_asc,
which carry no length and cannot fail. The pretty format agrees character for character with
Display when the variable is
x: \(5x^3 - 1\) is 5*x^3-1 in both. FLINT takes the variable as an arbitrary C string;
to_string_with
takes a Var from a
VarScheme
(for instance
ListVars::new(["t"])),
whose names may not contain an ASCII digit, whitespace, or + - * / ^ ( ) , (see
char_is_reserved).
zero_coefficients
takes u64 indices and panics if
start is greater than end. When res and poly are the same polynomial, fmpz_poly_reverse
is
reverse_assign.
Malachite’s truncate returns a new polynomial, as set_trunc does, rather than shortening in
place as Vec::truncate
does; the in-place form is truncate_assign.
Randomisation
| FLINT | Malachite | |
|---|---|---|
| ≈ | void fmpz_poly_randtest (fmpz_poly_t f, flint_rand_t state, slong len, flint_bitcnt_t bits) |
random_integer_polynomials, striped_random_integer_polynomials |
| ≈ | void fmpz_poly_randtest_unsigned (fmpz_poly_t f, flint_rand_t state, slong len, flint_bitcnt_t bits) |
random_natural_polynomials |
| ≈ | void fmpz_poly_randtest_not_zero (fmpz_poly_t f, flint_rand_t state, slong len, flint_bitcnt_t bits) |
random_integer_polynomials_min_degree |
| ✗ | void fmpz_poly_randtest_no_real_root (fmpz_poly_t p, flint_rand_t state, slong len, flint_bitcnt_t bits) |
|
| ✗ | void fmpz_poly_randtest_irreducible1 (fmpz_poly_t pol, flint_rand_t state, slong len, flint_bitcnt_t bits) |
|
| ✗ | void fmpz_poly_randtest_irreducible2 (fmpz_poly_t pol, flint_rand_t state, slong len, flint_bitcnt_t bits) |
|
| ✗ | void fmpz_poly_randtest_irreducible (fmpz_poly_t pol, flint_rand_t state, slong len, flint_bitcnt_t bits) |
FLINT’s generators take bounds (len caps the length, bits caps each coefficient’s bit
length); Malachite’s take means, sampling the degree and the coefficient bit length from
geometric distributions with unbounded support, so every row here is ≈ at best. The degree can
be constrained with the _with_degree, _min_degree, _degree_range, and
_degree_inclusive_range variants, and
_from_iterators
takes arbitrary coefficient and leading-coefficient iterators. randtest_unsigned is a change of
type, to
random_natural_polynomials.
randtest_not_zero is
random_integer_polynomials_min_degree
with minimum degree 0.
Getting and setting coefficients
| FLINT | Malachite | |
|---|---|---|
| ✓ | void fmpz_poly_get_coeff_fmpz (fmpz_t x, const fmpz_poly_t poly, slong n) |
coefficient |
| ≈ | slong fmpz_poly_get_coeff_si (const fmpz_poly_t poly, slong n) |
coefficient, TryFrom |
| ≈ | ulong fmpz_poly_get_coeff_ui (const fmpz_poly_t poly, slong n) |
coefficient, TryFrom |
| ≈ | fmpz * fmpz_poly_get_coeff_ptr (const fmpz_poly_t poly, slong n) |
coefficient, mutate_coefficient |
| ≈ | fmpz * fmpz_poly_lead (const fmpz_poly_t poly) |
leading_coefficient |
| ≈ | void fmpz_poly_set_coeff_fmpz (fmpz_poly_t poly, slong n, const fmpz_t x) |
mutate_coefficient |
| ≈ | void fmpz_poly_set_coeff_si (fmpz_poly_t poly, slong n, slong x) |
mutate_coefficient |
| ≈ | void fmpz_poly_set_coeff_ui (fmpz_poly_t poly, slong n, ulong x) |
mutate_coefficient |
The four getters collapse onto
coefficient,
which returns &Integer
in constant time; _si and _ui, whose result FLINT leaves undefined when the coefficient does
not fit, become i64::try_from(p.coefficient(n)) or the
WrappingFrom
/
SaturatingFrom
family. Past the degree, get_coeff_fmpz, _si, and _ui return zero but get_coeff_ptr
returns NULL, and fmpz_poly_lead returns NULL for the zero polynomial; Malachite returns a
reference to a static zero in all of those cases, including
leading_coefficient
of the zero polynomial, so a translated NULL check becomes a comparison against zero.
The three setters and in-place mutation through get_coeff_ptr are all
mutate_coefficient,
which takes a closure over &mut Integer
(assignment is p.mutate_coefficient(n, |c| *c = x)) so that the invariant can be restored after
the mutation. The index may run past the degree; the polynomial grows to reach it and trailing
zeros are dropped afterwards.
Comparison
| FLINT | Malachite | |
|---|---|---|
| ✓ | int fmpz_poly_equal (const fmpz_poly_t poly1, const fmpz_poly_t poly2) |
PartialEq |
| ✓ | int fmpz_poly_equal_trunc (const fmpz_poly_t poly1, const fmpz_poly_t poly2, slong n) |
eq_truncated |
| ✓ | int fmpz_poly_is_zero (const fmpz_poly_t poly) |
p == 0u32 (PartialEq) |
| ✓ | int fmpz_poly_is_one (const fmpz_poly_t poly) |
p == 1u32 (PartialEq) |
| ✓ | int fmpz_poly_is_unit (const fmpz_poly_t poly) |
IsUnit |
| ✓ | int fmpz_poly_is_gen (const fmpz_poly_t poly) |
x |
An IntegerPolynomial compares with a value of any primitive integer type, in either order:
p == c holds exactly when p is the constant polynomial c. So is_zero and is_one are
*p == 0u32 and *p == 1u32, and is_gen is *p == IntegerPolynomial::x(). For
equal_trunc, comparing coefficients_asc().iter().take(n) with
Iterator::eq is
wrong because it also compares lengths; use
eq_truncated.
FLINT has no fmpz_poly_cmp; Malachite’s default
Ord is asymptotic (\(p < q\) when
\(p(x) < q(x)\) for all sufficiently large \(x\)), and
ShortlexIntegerPolynomial
compares degree first and then coefficients from the leading one down, as fmpq_poly_cmp does.
Addition and subtraction
| FLINT | Malachite | |
|---|---|---|
| ✓ | void fmpz_poly_add (fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2) |
Add |
| ✓ | void fmpz_poly_add_series (fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2, slong n) |
add_truncated |
| ✓ | void fmpz_poly_sub (fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2) |
Sub |
| ✓ | void fmpz_poly_sub_series (fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2, slong n) |
sub_truncated |
| ✓ | void fmpz_poly_neg (fmpz_poly_t res, const fmpz_poly_t poly) |
Neg |
Each operator takes either operand by value or by reference and has an Assign form
(NegAssign
for negation). FLINT’s _series suffix becomes _truncated throughout this page:
add_truncated
and
sub_truncated
read only the first len coefficients of each operand. FLINT clamps a negative n to zero;
len is a u64, so it cannot be negative.
Scalar absolute value, multiplication and division
| FLINT | Malachite | |
|---|---|---|
| ✗ | void fmpz_poly_scalar_abs (fmpz_poly_t res, const fmpz_poly_t poly) |
|
| ✗ | void fmpz_poly_scalar_mul_fmpz (fmpz_poly_t poly1, const fmpz_poly_t poly2, const fmpz_t x) |
|
| ✗ | void fmpz_poly_scalar_mul_si (fmpz_poly_t poly1, const fmpz_poly_t poly2, slong x) |
|
| ✗ | void fmpz_poly_scalar_mul_ui (fmpz_poly_t poly1, const fmpz_poly_t poly2, ulong x) |
|
| ✓ | void fmpz_poly_scalar_mul_2exp (fmpz_poly_t poly1, const fmpz_poly_t poly2, ulong exp) |
Shl |
| ✗ | void fmpz_poly_scalar_addmul_si (fmpz_poly_t poly1, const fmpz_poly_t poly2, slong x) |
|
| ✗ | void fmpz_poly_scalar_addmul_ui (fmpz_poly_t poly1, const fmpz_poly_t poly2, ulong x) |
|
| ✗ | void fmpz_poly_scalar_addmul_fmpz (fmpz_poly_t poly1, const fmpz_poly_t poly2, const fmpz_t x) |
|
| ✗ | void fmpz_poly_scalar_submul_fmpz (fmpz_poly_t poly1, const fmpz_poly_t poly2, const fmpz_t x) |
|
| ✗ | void fmpz_poly_scalar_fdiv_fmpz (fmpz_poly_t poly1, const fmpz_poly_t poly2, const fmpz_t x) |
|
| ✗ | void fmpz_poly_scalar_fdiv_si (fmpz_poly_t poly1, const fmpz_poly_t poly2, slong x) |
|
| ✗ | void fmpz_poly_scalar_fdiv_ui (fmpz_poly_t poly1, const fmpz_poly_t poly2, ulong x) |
|
| ✗ | void fmpz_poly_scalar_fdiv_2exp (fmpz_poly_t poly1, const fmpz_poly_t poly2, ulong x) |
|
| ✗ | void fmpz_poly_scalar_tdiv_fmpz (fmpz_poly_t poly1, const fmpz_poly_t poly2, const fmpz_t x) |
|
| ✗ | void fmpz_poly_scalar_tdiv_si (fmpz_poly_t poly1, const fmpz_poly_t poly2, slong x) |
|
| ✗ | void fmpz_poly_scalar_tdiv_ui (fmpz_poly_t poly1, const fmpz_poly_t poly2, ulong x) |
|
| ✗ | void fmpz_poly_scalar_tdiv_2exp (fmpz_poly_t poly1, const fmpz_poly_t poly2, ulong x) |
|
| ✓ | void fmpz_poly_scalar_divexact_fmpz (fmpz_poly_t poly1, const fmpz_poly_t poly2, const fmpz_t x) |
DivExact |
| ✗ | void fmpz_poly_scalar_divexact_si (fmpz_poly_t poly1, const fmpz_poly_t poly2, slong x) |
|
| ✗ | void fmpz_poly_scalar_divexact_ui (fmpz_poly_t poly1, const fmpz_poly_t poly2, ulong x) |
|
| ✓ | void fmpz_poly_scalar_mod_fmpz (fmpz_poly_t poly1, const fmpz_poly_t poly2, const fmpz_t p) |
Mod |
| ✓ | void fmpz_poly_scalar_smod_fmpz (fmpz_poly_t poly1, const fmpz_poly_t poly2, const fmpz_t p) |
BalancedMod |
scalar_mul_2exp is << by a
u64: throughout Malachite << and
>> scale by a power of two and never mean multiplication by \(x^k\) (see
Shifting). scalar_divexact_fmpz is
DivExact
by an Integer.
scalar_mod_fmpz reduces each coefficient into \([0, p)\). On IntegerPolynomial,
Mod
and
ModPowerOf2
take a positive Natural
or a power of 2 and return a
NaturalPolynomial,
not an IntegerPolynomial.
Rem instead takes an
Integer, returns
an IntegerPolynomial, and keeps each coefficient’s sign (the remainder of scalar_tdiv_fmpz,
which FLINT does not provide). scalar_smod_fmpz takes the representative in \((-p/2, p/2]\), as
BalancedMod
does.
Bit packing
| FLINT | Malachite | |
|---|---|---|
| ≈ | void fmpz_poly_bit_pack (fmpz_t f, const fmpz_poly_t poly, flint_bitcnt_t bit_size) |
bit_pack |
| ≈ | void fmpz_poly_bit_unpack (fmpz_poly_t poly, const fmpz_t f, flint_bitcnt_t bit_size) |
bit_unpack |
| ≈ | void fmpz_poly_bit_unpack_unsigned (fmpz_poly_t poly, const fmpz_t f, flint_bitcnt_t bit_size) |
bit_unpack |
bit_pack
always returns \(p(2^b)\), hence ≈: it agrees with fmpz_poly_bit_pack when
\(b > 0\) and every coefficient’s absolute value is less than \(2^b\), but FLINT gives 0 for
\(b = 0\) and truncates wider coefficients, while bit_pack lets them overlap the fields above.
bit_unpack reads the fields as signed on
IntegerPolynomial, exactly as fmpz_poly_bit_unpack does (each negative field borrows from the
one above, and a negative input negates every coefficient), and as unsigned on
NaturalPolynomial, as fmpz_poly_bit_unpack_unsigned does; both are ≈ only because they panic
for \(b = 0\), where FLINT returns the zero polynomial.
Multiplication
| FLINT | Malachite | |
|---|---|---|
| ✓ | void fmpz_poly_mul (fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2) |
* |
| ⚙ | void fmpz_poly_mul_classical (fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2) |
* |
| ⚙ | void fmpz_poly_mul_karatsuba (fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2) |
* |
| ⚙ | void fmpz_poly_mul_KS (fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2) |
* |
| ⚙ | void fmpz_poly_mul_SS (fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2) |
* |
| ✓ | void fmpz_poly_mullow (fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2, slong n) |
mul_truncated |
| ⚙ | void fmpz_poly_mullow_classical (fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2, slong n) |
mul_truncated |
| ⚙ | void fmpz_poly_mullow_karatsuba_n (fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2, slong n) |
mul_truncated |
| ⚙ | void fmpz_poly_mullow_KS (fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2, slong n) |
mul_truncated |
| ⚙ | void fmpz_poly_mullow_SS (fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2, slong n) |
mul_truncated |
| ✗ | void fmpz_poly_mulhigh_n (fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2, slong n) |
|
| ✗ | void fmpz_poly_mulhigh_classical (fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2, slong start) |
|
| ✗ | void fmpz_poly_mulhigh_karatsuba_n (fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2, slong len) |
|
| ✗ | void fmpz_poly_mulmid (fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2) |
|
| ✗ | void fmpz_poly_mulmid_classical (fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2) |
|
| ✗ | void fmpz_poly_mulmid_KS (fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2) |
|
| ✗ | void fmpz_poly_mulmid_SS (fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2) |
Malachite chooses the multiplication algorithm itself, so the _classical, _karatsuba, _KS,
and _SS functions map to the same operation as their dispatcher: * (with *=) for the whole
product, and
mul_truncated
(with mul_truncated_assign) for the low \(n\) coefficients.
FFT precached multiplication
| FLINT | Malachite | |
|---|---|---|
| — | void fmpz_poly_mul_SS_precache_init (fmpz_poly_mul_precache_t pre, slong len1, slong bits1, const fmpz_poly_t poly2) |
|
| — | void fmpz_poly_mul_precache_clear (fmpz_poly_mul_precache_t pre) |
|
| — | void fmpz_poly_mul_SS_precache (fmpz_poly_t res, const fmpz_poly_t poly1, fmpz_poly_mul_precache_t pre) |
|
| — | void fmpz_poly_mullow_SS_precache (fmpz_poly_t res, const fmpz_poly_t poly1, fmpz_poly_mul_precache_t pre, slong n) |
These cache the transform of a fixed operand for one algorithm. Malachite does not expose its
multiplication algorithms, so there is nothing to cache; _precache_clear is
Drop.
Squaring
| FLINT | Malachite | |
|---|---|---|
| ✓ | void fmpz_poly_sqr (fmpz_poly_t rop, const fmpz_poly_t op) |
square |
| ⚙ | void fmpz_poly_sqr_classical (fmpz_poly_t rop, const fmpz_poly_t op) |
square |
| ⚙ | void fmpz_poly_sqr_karatsuba (fmpz_poly_t rop, const fmpz_poly_t op) |
square |
| ⚙ | void fmpz_poly_sqr_KS (fmpz_poly_t rop, const fmpz_poly_t op) |
square |
| ✓ | void fmpz_poly_sqrlow (fmpz_poly_t res, const fmpz_poly_t poly, slong n) |
square_truncated |
| ⚙ | void fmpz_poly_sqrlow_classical (fmpz_poly_t res, const fmpz_poly_t poly, slong n) |
square_truncated |
| ⚙ | void fmpz_poly_sqrlow_karatsuba_n (fmpz_poly_t res, const fmpz_poly_t poly, slong n) |
square_truncated |
| ⚙ | void fmpz_poly_sqrlow_KS (fmpz_poly_t res, const fmpz_poly_t poly, slong n) |
square_truncated |
As with multiplication, the algorithm variants map to
square
(with square_assign) and
square_truncated
(with square_truncated_assign).
Powering
| FLINT | Malachite | |
|---|---|---|
| ✓ | void fmpz_poly_pow (fmpz_poly_t res, const fmpz_poly_t poly, ulong e) |
pow |
| ⚙ | void fmpz_poly_pow_multinomial (fmpz_poly_t res, const fmpz_poly_t poly, ulong e) |
pow |
| ⚙ | void fmpz_poly_pow_binomial (fmpz_poly_t res, const fmpz_poly_t poly, ulong e) |
pow |
| ⚙ | void fmpz_poly_pow_addchains (fmpz_poly_t res, const fmpz_poly_t poly, ulong e) |
pow |
| ⚙ | void fmpz_poly_pow_binexp (fmpz_poly_t res, const fmpz_poly_t poly, ulong e) |
pow |
| ✓ | void fmpz_poly_pow_trunc (fmpz_poly_t res, const fmpz_poly_t poly, ulong e, slong n) |
pow_truncated |
Pow
and
PowAssign
take a u64 exponent. pow
chooses among several algorithms itself, so FLINT’s four algorithm-specific functions all map to
it, without the domain restrictions of pow_binomial (length exactly 2) or pow_addchains
(\(e \leq 148\)).
PowTruncatedAssign
is the in-place form of pow_truncated, which reads only the first len coefficients. Both
libraries take \(0^0 = 1\).
Shifting
| FLINT | Malachite | |
|---|---|---|
| ✓ | void fmpz_poly_shift_left (fmpz_poly_t res, const fmpz_poly_t poly, slong n) |
mul_power_of_x |
| ✓ | void fmpz_poly_shift_right (fmpz_poly_t res, const fmpz_poly_t poly, slong n) |
div_power_of_x |
div_power_of_x, like shift_right, discards the low coefficients, and yields zero when n is
at or beyond the length. Neither operation is << or >>, which throughout Malachite scale by a
power of two (see the scalar section).
Bit sizes and norms
| FLINT | Malachite | |
|---|---|---|
| — | ulong fmpz_poly_max_limbs (const fmpz_poly_t poly) |
|
| ≈ | slong fmpz_poly_max_bits (const fmpz_poly_t poly) |
height_significant_bits |
| ✓ | void fmpz_poly_height (fmpz_t height, const fmpz_poly_t poly) |
Height, HeightRef |
| ✓ | void fmpz_poly_2norm (fmpz_t res, const fmpz_poly_t poly) |
floor_l2_norm |
fmpz_poly_height is
Height’s
to_height
or
into_height;
HeightRef
returns it by reference. max_bits returns the bit length \(b\) of the height, negated when any
coefficient is negative;
height_significant_bits
returns \(|b|\) as a plain
u64 (0 for the zero polynomial)
and the sign flag must come from elsewhere, hence ≈. max_limbs is a memory-estimation helper;
limbs are an implementation detail in Malachite. 2norm (the integer square root of the sum of
squared coefficients) is
floor_l2_norm;
the exact sum of squares is
l2_norm_squared.
Greatest common divisor
| FLINT | Malachite | |
|---|---|---|
| ✗ | void fmpz_poly_gcd (fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2) |
|
| ✗ | void fmpz_poly_gcd_subresultant (fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2) |
|
| ✗ | int fmpz_poly_gcd_heuristic (fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2) |
|
| ✗ | void fmpz_poly_gcd_modular (fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2) |
|
| ✗ | void fmpz_poly_lcm (fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2) |
|
| ✗ | void fmpz_poly_xgcd (fmpz_t r, fmpz_poly_t s, fmpz_poly_t t, const fmpz_poly_t f, const fmpz_poly_t g) |
|
| ✗ | void fmpz_poly_xgcd_modular (fmpz_t r, fmpz_poly_t s, fmpz_poly_t t, const fmpz_poly_t f, const fmpz_poly_t g) |
|
| ✗ | void fmpz_poly_resultant (fmpz_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2) |
|
| ✗ | void fmpz_poly_resultant_euclidean (fmpz_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2) |
|
| ✗ | void fmpz_poly_resultant_modular (fmpz_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2) |
|
| — | void fmpz_poly_resultant_modular_div (fmpz_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2, const fmpz_t div, slong nbits) |
|
| ✗ | void fmpz_poly_squarefree_part (fmpz_poly_t res, const fmpz_poly_t poly) |
fmpz_poly_xgcd is not an extended gcd: it sets \(r\) to the resultant of \(f\) and \(g\) and
finds \(s, t\) with \(sf + tg = r\), so it does not correspond to
ExtendedGcd
on the scalar types. resultant_modular_div is — because it asks the caller to supply
unverifiable facts (that div divides the resultant exactly and that the result fits in nbits)
in exchange for skipping a bound computation.
Discriminant
| FLINT | Malachite | |
|---|---|---|
| ✗ | void fmpz_poly_discriminant (fmpz_t res, const fmpz_poly_t poly) |
FLINT normalises the discriminant as \((-1)^{n(n-1)/2} \operatorname{res}(f, f') / \operatorname{lc}(f)\), with \(n\) the degree, and gives 0 for the zero polynomial and for every constant.
Gaussian content
| FLINT | Malachite | |
|---|---|---|
| ✓ | void fmpz_poly_content (fmpz_t res, const fmpz_poly_t poly) |
content |
| ✓ | void fmpz_poly_primitive_part (fmpz_poly_t res, const fmpz_poly_t poly) |
primitive_part |
Malachite’s content is a
Natural. The
primitive part follows FLINT’s sign convention (non-negative leading coefficient), so for a
negative leading coefficient the identity is
Both functions return zero for the zero polynomial.
content_and_primitive_part
replaces a call to both.
Square-free
| FLINT | Malachite | |
|---|---|---|
| ✗ | int fmpz_poly_is_squarefree (const fmpz_poly_t poly) |
fmpz_poly_is_squarefree tests for repeated roots, that is, square-freeness over
\(\mathbb{Q}[x]\): it checks that \(\gcd(f, f')\) is constant, so \(4\) and \(4x + 4\) pass, and
the zero polynomial passes by fiat. This is the condition that fmpz_poly_signature
requires of its input.
Euclidean division
| FLINT | Malachite | |
|---|---|---|
| ✗ | void fmpz_poly_divrem (fmpz_poly_t Q, fmpz_poly_t R, const fmpz_poly_t A, const fmpz_poly_t B) |
|
| ✗ | void fmpz_poly_divrem_basecase (fmpz_poly_t Q, fmpz_poly_t R, const fmpz_poly_t A, const fmpz_poly_t B) |
|
| ✗ | void fmpz_poly_divrem_divconquer (fmpz_poly_t Q, fmpz_poly_t R, const fmpz_poly_t A, const fmpz_poly_t B) |
|
| ✗ | void fmpz_poly_div (fmpz_poly_t Q, const fmpz_poly_t A, const fmpz_poly_t B) |
|
| ✗ | void fmpz_poly_div_basecase (fmpz_poly_t Q, const fmpz_poly_t A, const fmpz_poly_t B) |
|
| ✗ | void fmpz_poly_div_divconquer (fmpz_poly_t Q, const fmpz_poly_t A, const fmpz_poly_t B) |
|
| ✗ | void fmpz_poly_rem (fmpz_poly_t R, const fmpz_poly_t A, const fmpz_poly_t B) |
|
| ✗ | void fmpz_poly_rem_basecase (fmpz_poly_t R, const fmpz_poly_t A, const fmpz_poly_t B) |
|
| ✗ | void fmpz_poly_divexact (fmpz_poly_t Q, const fmpz_poly_t A, const fmpz_poly_t B) |
|
| ✗ | void fmpz_poly_div_root_fmpz (fmpz_poly_t Q, const fmpz_poly_t A, const fmpz_t c) |
|
| ✗ | void fmpz_poly_divexact_root_fmpq (fmpz_poly_t Q, const fmpz_poly_t A, const fmpq_t c) |
Over \(\mathbb{Z}[x]\) FLINT’s divrem is \(A = BQ + R\) where each coefficient of \(R\) beyond
\(\operatorname{len}(B) - 1\) is reduced modulo the leading coefficient of \(B\), so the remainder
may keep high-degree terms; see also pseudo-division.
Division with precomputed inverse
| FLINT | Malachite | |
|---|---|---|
| ✗ | void fmpz_poly_preinvert (fmpz_poly_t B_inv, const fmpz_poly_t B) |
|
| ✗ | void fmpz_poly_div_preinv (fmpz_poly_t Q, const fmpz_poly_t A, const fmpz_poly_t B, const fmpz_poly_t B_inv) |
|
| ✗ | void fmpz_poly_divrem_preinv (fmpz_poly_t Q, fmpz_poly_t R, const fmpz_poly_t A, const fmpz_poly_t B, const fmpz_poly_t B_inv) |
|
| ✗ | void fmpz_poly_powers_precompute (fmpz_poly_powers_precomp_t pinv, fmpz_poly_t poly) |
|
| ✗ | void fmpz_poly_rem_powers_precomp (fmpz_poly_t R, const fmpz_poly_t A, const fmpz_poly_t B, fmpz_poly_powers_precomp_t B_inv) |
|
| — | void fmpz_poly_powers_clear (fmpz_poly_powers_precomp_t pinv) |
powers_clear frees the powers table, which is
Drop.
Divisibility testing
| FLINT | Malachite | |
|---|---|---|
| ✗ | int fmpz_poly_divides (fmpz_poly_t Q, const fmpz_poly_t A, const fmpz_poly_t B) |
|
| ✗ | slong fmpz_poly_remove (fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2) |
fmpz_poly_divides returns a flag and, on success, the quotient. fmpz_poly_remove returns the
quotient through res and the exponent as its return value, and raises an exception for a
divisor of 0 or \(\pm 1\), the inputs on which the scalar
RemovePower
panics.
Division mod p
| FLINT | Malachite | |
|---|---|---|
| — | void fmpz_poly_divlow_smodp (fmpz * res, const fmpz_poly_t f, const fmpz_poly_t g, const fmpz_t p, slong n) |
|
| — | void fmpz_poly_divhigh_smodp (fmpz * res, const fmpz_poly_t f, const fmpz_poly_t g, const fmpz_t p, slong n) |
Both are, in FLINT’s words, “a bespoke function used by factoring”: internal helpers with unchecked preconditions, so they are —.
Power series division
| FLINT | Malachite | |
|---|---|---|
| ✗ | void fmpz_poly_inv_series (fmpz_poly_t Qinv, const fmpz_poly_t Q, slong n) |
|
| ✗ | void fmpz_poly_inv_series_basecase (fmpz_poly_t Qinv, const fmpz_poly_t Q, slong n) |
|
| ✗ | void fmpz_poly_inv_series_newton (fmpz_poly_t Qinv, const fmpz_poly_t Q, slong n) |
|
| ✗ | void fmpz_poly_div_series (fmpz_poly_t Q, const fmpz_poly_t A, const fmpz_poly_t B, slong n) |
|
| ✗ | void fmpz_poly_div_series_basecase (fmpz_poly_t Q, const fmpz_poly_t A, const fmpz_poly_t B, slong n) |
|
| ✗ | void fmpz_poly_div_series_divconquer (fmpz_poly_t Q, const fmpz_poly_t A, const fmpz_poly_t B, slong n) |
These work in \(\mathbb{Z}[[x]]/(x^n)\) and require the constant term of the series being
inverted (Q or B) to be \(\pm 1\), the only units of \(\mathbb{Z}\), without checking it.
Pseudo division
| FLINT | Malachite | |
|---|---|---|
| ✗ | void fmpz_poly_pseudo_divrem (fmpz_poly_t Q, fmpz_poly_t R, ulong * d, const fmpz_poly_t A, const fmpz_poly_t B) |
|
| ✗ | void fmpz_poly_pseudo_divrem_basecase (fmpz_poly_t Q, fmpz_poly_t R, ulong * d, const fmpz_poly_t A, const fmpz_poly_t B) |
|
| ✗ | void fmpz_poly_pseudo_divrem_divconquer (fmpz_poly_t Q, fmpz_poly_t R, ulong * d, const fmpz_poly_t A, const fmpz_poly_t B) |
|
| ✗ | void fmpz_poly_pseudo_divrem_cohen (fmpz_poly_t Q, fmpz_poly_t R, const fmpz_poly_t A, const fmpz_poly_t B) |
|
| ✗ | void fmpz_poly_pseudo_div (fmpz_poly_t Q, ulong * d, const fmpz_poly_t A, const fmpz_poly_t B) |
|
| ✗ | void fmpz_poly_pseudo_rem (fmpz_poly_t R, ulong * d, const fmpz_poly_t A, const fmpz_poly_t B) |
|
| ✗ | void fmpz_poly_pseudo_rem_cohen (fmpz_poly_t R, const fmpz_poly_t A, const fmpz_poly_t B) |
Pseudo-division computes \(Q\), \(R\), and \(d\) with \(\ell^d A = BQ + R\) and \(\deg R < \deg B\), where \(\ell\) is the leading coefficient of \(B\):
| dividend | remainder | |
|---|---|---|
divrem |
\(A\) itself | may keep high-degree terms, reduced modulo \(\ell\) |
pseudo_divrem |
scaled to \(\ell^d A\) | \(\deg R < \deg B\), as in a field |
Derivative
| FLINT | Malachite | |
|---|---|---|
| ✓ | void fmpz_poly_derivative (fmpz_poly_t res, const fmpz_poly_t poly) |
derivative |
| ✓ | void fmpz_poly_nth_derivative (fmpz_poly_t res, const fmpz_poly_t poly, ulong n) |
nth_derivative |
Both return zero when the length is at most n (at most 1 for derivative). The chapter has no
integral, because integration divides by \(i + 1\) and leaves \(\mathbb{Z}\); fmpq_poly has one.
Evaluation
| FLINT | Malachite | |
|---|---|---|
| ✓ | void fmpz_poly_evaluate_fmpz (fmpz_t res, const fmpz_poly_t f, const fmpz_t a) |
evaluate |
| ⚙ | void fmpz_poly_evaluate_horner_fmpz (fmpz_t res, const fmpz_poly_t f, const fmpz_t a) |
evaluate |
| ⚙ | void fmpz_poly_evaluate_divconquer_fmpz (fmpz_t res, const fmpz_poly_t poly, const fmpz_t a) |
evaluate |
| ✓ | void fmpz_poly_evaluate_fmpq (fmpq_t res, const fmpz_poly_t f, const fmpq_t a) |
evaluate |
| ⚙ | void fmpz_poly_evaluate_horner_fmpq (fmpq_t res, const fmpz_poly_t f, const fmpq_t a) |
evaluate |
| ⚙ | void fmpz_poly_evaluate_divconquer_fmpq (fmpq_t res, const fmpz_poly_t poly, const fmpq_t a) |
evaluate |
| ≈ | ulong fmpz_poly_evaluate_mod (const fmpz_poly_t poly, ulong a, ulong n) |
mod_evaluate |
| ✓ | void fmpz_poly_evaluate_fmpz_vec (fmpz * res, const fmpz_poly_t f, const fmpz * a, slong n) |
evaluate_many |
| — | double fmpz_poly_evaluate_horner_d (const fmpz_poly_t poly, double d) |
|
| — | double fmpz_poly_evaluate_horner_d_2exp (slong * exp, const fmpz_poly_t poly, double d) |
evaluate
chooses between Horner’s rule and divide and conquer itself, so the _horner and _divconquer
rows map to it as well. Its result type is its argument type: at an
Integer it
returns an Integer, and at a
Rational (the
_fmpq rows) a Rational in lowest terms.
mod_evaluate
evaluates at a u64 modulo a u64,
reducing each coefficient (negative ones into \([0, n)\)) as FLINT does, but it panics unless a
is already reduced, hence ≈. The two double rows are — because FLINT itself says they make “no
attempt” at efficiency or numerical stability and exist only for quick evaluations of polynomials
with positive coefficients.
Newton basis
| FLINT | Malachite | |
|---|---|---|
| ✗ | void _fmpz_poly_monomial_to_newton (fmpz * poly, const fmpz * roots, slong n) |
|
| ✗ | void _fmpz_poly_newton_to_monomial (fmpz * poly, const fmpz * roots, slong n) |
These convert a coefficient list in place between the monomial basis and the Newton basis
\(1,\; (x - r_0),\; (x - r_0)(x - r_1),\; \ldots\) for a caller-supplied root sequence. The
conversion is integral in both directions with no precondition, and both directions must be
given the same roots.
Interpolation
| FLINT | Malachite | |
|---|---|---|
| ✗ | int fmpz_poly_interpolate (fmpz_poly_t poly, const fmpz * xs, const fmpz * ys, slong n) |
|
| ✗ | int fmpz_poly_interpolate_newton (fmpz_poly_t poly, const fmpz * xs, const fmpz * ys, slong n) |
|
| ✗ | int fmpz_poly_interpolate_multi_mod (fmpz_poly_t poly, const fmpz * xs, const fmpz * ys, slong n) |
|
| — | void fmpz_poly_interpolate_exact (fmpz_poly_t poly, const fmpz * xs, const fmpz * ys, slong n) |
|
| — | void fmpz_poly_interpolate_exact_newton (fmpz_poly_t poly, const fmpz * xs, const fmpz * ys, slong n) |
|
| — | void fmpz_poly_interpolate_fmpz_vec (fmpz_poly_t poly, const fmpz * xs, const fmpz * ys, slong n) |
An interpolant with integer coefficients may not exist. On failure interpolate returns 0,
interpolate_exact leaves the behaviour undefined, and interpolate_fmpz_vec throws
FLINT_INEXACT. The _exact and _fmpz_vec rows are — because they differ from interpolate
only in error discipline, which in Rust is the caller’s choice of match,
unwrap, or
unwrap_unchecked
on one Option-returning
function.
Composition
| FLINT | Malachite | |
|---|---|---|
| ✗ | void fmpz_poly_compose (fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2) |
|
| ✗ | void fmpz_poly_compose_horner (fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2) |
|
| ✗ | void fmpz_poly_compose_divconquer (fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2) |
fmpz_poly_compose sets res to \(g(h(x))\) for poly1 \(= g\) and poly2 \(= h\); the
_horner and _divconquer rows are algorithm choices. The same result comes from Horner’s rule,
running over the coefficients \(c\) of \(g\) from the top with
acc = acc * h + IntegerPolynomial::from(c); when \(h\) is \(x^k\), compose is
compose_power_of_x.
Inflation and deflation
| FLINT | Malachite | |
|---|---|---|
| ✓ | void fmpz_poly_inflate (fmpz_poly_t result, const fmpz_poly_t input, ulong inflation) |
compose_power_of_x |
| ≈ | void fmpz_poly_deflate (fmpz_poly_t result, const fmpz_poly_t input, ulong deflation) |
deflate_power_of_x |
| ≈ | ulong fmpz_poly_deflation (const fmpz_poly_t input) |
exponent_gcd |
compose_power_of_x,
like fmpz_poly_inflate, gives the constant \(p(1)\) for \(n = 0\). fmpz_poly_deflate silently
discards the coefficients at exponents that are not multiples of \(n\), so deflating \(x^2 + x\)
by 2 returns \(x\);
deflate_power_of_x
panics instead, hence ≈. fmpz_poly_deflation returns 0 for the zero polynomial and 1 for a
constant;
exponent_gcd
returns 0 for every constant, hence ≈.
Taylor shift
| FLINT | Malachite | |
|---|---|---|
| ✗ | void fmpz_poly_taylor_shift (fmpz_poly_t g, const fmpz_poly_t f, const fmpz_t c) |
|
| ✗ | void fmpz_poly_taylor_shift_horner (fmpz_poly_t g, const fmpz_poly_t f, const fmpz_t c) |
|
| ✗ | void fmpz_poly_taylor_shift_divconquer (fmpz_poly_t g, const fmpz_poly_t f, const fmpz_t c) |
|
| ✗ | void fmpz_poly_taylor_shift_multi_mod (fmpz_poly_t g, const fmpz_poly_t f, const fmpz_t c) |
fmpz_poly_taylor_shift computes \(f(x + c)\); the other three rows are algorithm choices. The
same result comes from the Horner recipe under composition, with inner polynomial
\(x + c\).
Power series composition
| FLINT | Malachite | |
|---|---|---|
| ✗ | void fmpz_poly_compose_series (fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2, slong n) |
|
| ✗ | void fmpz_poly_compose_series_horner (fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2, slong n) |
|
| ✗ | void fmpz_poly_compose_series_brent_kung (fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_poly_t poly2, slong n) |
compose_series is composition truncated to \(n\) terms, and requires the inner
polynomial to have zero constant term. The same result comes from the Horner recipe under
composition with
mul_truncated
in place of *.
Power series reversion
| FLINT | Malachite | |
|---|---|---|
| ✗ | void fmpz_poly_revert_series (fmpz_poly_t Qinv, const fmpz_poly_t Q, slong n) |
fmpz_poly_revert_series computes the compositional inverse, with \(Q(Q^{-1}(x)) = x \bmod
x^n\), not the multiplicative one that inv_series computes. It
requires \(Q_0 = 0\) and \(Q_1 = \pm 1\), and checks neither.
Square root
| FLINT | Malachite | |
|---|---|---|
| ✗ | int fmpz_poly_sqrt (fmpz_poly_t b, const fmpz_poly_t a) |
|
| ✗ | int fmpz_poly_sqrt_classical (fmpz_poly_t b, const fmpz_poly_t a) |
|
| ✗ | int fmpz_poly_sqrt_divconquer (fmpz_poly_t b, const fmpz_poly_t a) |
|
| — | int fmpz_poly_sqrt_KS (fmpz_poly_t b, const fmpz_poly_t a) |
|
| ✗ | int fmpz_poly_sqrtrem_classical (fmpz_poly_t b, fmpz_poly_t r, const fmpz_poly_t a) |
|
| ✗ | int fmpz_poly_sqrtrem_divconquer (fmpz_poly_t b, fmpz_poly_t r, const fmpz_poly_t a) |
|
| ✗ | int fmpz_poly_sqrt_series (fmpz_poly_t b, const fmpz_poly_t a, slong n) |
sqrt_KS returns \(-1\) when its heuristic cannot decide; it is — because fmpz_poly_sqrt
already handles that case.
Power sums
| FLINT | Malachite | |
|---|---|---|
| ✗ | void fmpz_poly_power_sums (fmpz_poly_t res, const fmpz_poly_t poly, slong n) |
|
| ✗ | void fmpz_poly_power_sums_naive (fmpz_poly_t res, const fmpz_poly_t poly, slong n) |
|
| ✗ | void fmpz_poly_power_sums_to_poly (fmpz_poly_t res, const fmpz_poly_t Q) |
fmpz_poly_power_sums returns the power sums \(p_i = \sum_j r_j^i\) of the complex roots, for
\(0 \le i < n\), as the coefficients of a series, and power_sums_to_poly converts back, reading
the degree from \(p_0\). Both directions require a monic polynomial, and neither checks its
preconditions.
Signature
| FLINT | Malachite | |
|---|---|---|
| ✗ | void fmpz_poly_signature (slong * r1, slong * r2, const fmpz_poly_t poly) |
fmpz_poly_signature returns \((r_1, r_2)\), with \(r_1\) real roots and \(2r_2\) non-real
ones. The input must be square-free over \(\mathbb{Q}\), the condition that
fmpz_poly_is_squarefree tests, and the behaviour is undefined otherwise; the
zero polynomial gives \((0, 0)\).
Hensel lifting
| FLINT | Malachite | |
|---|---|---|
| ✗ | void fmpz_poly_hensel_lift_once (fmpz_poly_factor_t lifted_fac, const fmpz_poly_t f, const nmod_poly_factor_t local_fac, slong N) |
|
| — | void fmpz_poly_hensel_lift (fmpz_poly_t Gout, fmpz_poly_t Hout, fmpz_poly_t Aout, fmpz_poly_t Bout, ...) |
|
| — | void fmpz_poly_hensel_lift_without_inverse (fmpz_poly_t Gout, fmpz_poly_t Hout, ...) |
|
| — | void fmpz_poly_hensel_lift_only_inverse (fmpz_poly_t Aout, fmpz_poly_t Bout, ...) |
|
| — | void fmpz_poly_hensel_build_tree (slong * link, fmpz_poly_t * v, fmpz_poly_t * w, const nmod_poly_factor_t fac) |
|
| — | void fmpz_poly_hensel_lift_tree (slong * link, fmpz_poly_t * v, fmpz_poly_t * w, ...) |
|
| — | void fmpz_poly_hensel_lift_tree_recursive (slong * link, fmpz_poly_t * v, fmpz_poly_t * w, ...) |
FLINT labels hensel_lift_once as the one entry “intended for end users”; the other six are
internal tree and step functions, so they are —.
Input and output
| FLINT | Malachite | |
|---|---|---|
| ✓ | int fmpz_poly_print_pretty (const fmpz_poly_t poly, const char * x) |
Display, to_string_with |
| ✓ | int fmpz_poly_fprint_pretty (FILE * file, const fmpz_poly_t poly, const char * x) |
Display |
| ≈ | int fmpz_poly_read_pretty (fmpz_poly_t poly, char ** x) |
FromStr, from_string_with |
| ≈ | int fmpz_poly_fread_pretty (FILE * file, fmpz_poly_t poly, char ** x) |
FromStr |
| ≈ | int fmpz_poly_print (const fmpz_poly_t poly) |
Serialize, coefficients_asc |
| ≈ | int fmpz_poly_fprint (FILE * file, const fmpz_poly_t poly) |
Serialize |
| ≈ | int fmpz_poly_read (fmpz_poly_t poly) |
Deserialize, from_coefficients_asc |
| ≈ | int fmpz_poly_fread (FILE * file, fmpz_poly_t poly) |
Deserialize |
The print/fprint split disappears because
Display writes to any
Formatter. The plain format
is handled as in the assignment section. The pretty read
rows are ≈ because fread_pretty reports the variable name it found through char ** x, whereas
FromStr assumes x and
from_string_with
takes the
Var up front.
Modular reduction and reconstruction
| FLINT | Malachite | |
|---|---|---|
| ✓ | void fmpz_poly_get_nmod_poly (nmod_poly_t Amod, const fmpz_poly_t A) |
Mod |
| ✗ | void fmpz_poly_set_nmod_poly (fmpz_poly_t A, const nmod_poly_t Amod) |
|
| ✗ | void fmpz_poly_set_nmod_poly_unsigned (fmpz_poly_t A, const nmod_poly_t Amod) |
|
| ✗ | void fmpz_poly_CRT_ui (fmpz_poly_t res, const fmpz_poly_t poly1, const fmpz_t m, const nmod_poly_t poly2, int sign) |
Malachite has no nmod_poly type: a polynomial with reduced coefficients is a
NaturalPolynomial
or
UnsignedPolynomial
satisfying
ModIsReduced.
get_nmod_poly is (&a).mod_op(m) with m of the same type as the result’s coefficients (a
u64 modulus gives an UnsignedPolynomial<u64>).
Products
| FLINT | Malachite | |
|---|---|---|
| ✗ | void fmpz_poly_product_roots_fmpz_vec (fmpz_poly_t poly, const fmpz * xs, slong n) |
|
| ✗ | void fmpz_poly_product_roots_fmpq_vec (fmpz_poly_t poly, const fmpq * xs, slong n) |
product_roots_fmpz_vec builds \(\prod_i (x - x_i)\). The rational variant clears
denominators, building \(\prod_i (q_i x - p_i)\) for \(x_i = p_i/q_i\), so its leading
coefficient is the product of the denominators. Either product can be formed with * from linear
factors built by
from_coefficients_asc.
Subproduct trees
| FLINT | Malachite | |
|---|---|---|
| — | fmpz ** _fmpz_poly_tree_alloc (slong len) |
|
| — | void _fmpz_poly_tree_free (fmpz ** tree, slong len) |
|
| — | void _fmpz_poly_tree_build_fmpq_vec (fmpz ** tree, const fmpq * roots, slong len) |
These allocate, free, and fill a caller-allocated fmpz ** buffer, so they are —; allocation and
freeing are Drop’s job.
Roots
| FLINT | Malachite | |
|---|---|---|
| ✗ | void fmpz_poly_bound_roots (fmpz_t bound, const fmpz_poly_t poly) |
|
| ✗ | slong fmpz_poly_positive_root_upper_bound_2exp (const fmpz_poly_t pol) |
|
| ✗ | int fmpz_poly_has_real_root (const fmpz_poly_t pol) |
|
| ✗ | slong fmpz_poly_num_real_roots (const fmpz_poly_t pol) |
|
| ✗ | slong fmpz_poly_num_real_roots_sturm (const fmpz_poly_t pol) |
|
| ✗ | slong fmpz_poly_num_real_roots_vca (const fmpz_poly_t pol) |
|
| ✗ | slong fmpz_poly_num_real_roots_0_1 (const fmpz_poly_t pol) |
|
| ✗ | slong fmpz_poly_num_real_roots_0_1_sturm (const fmpz_poly_t pol) |
|
| ✗ | slong fmpz_poly_num_real_roots_0_1_vca (const fmpz_poly_t pol) |
|
| ✗ | void fmpz_poly_isolate_real_roots (fmpz * exact_roots, slong * n_exact, fmpz * c_array, slong * k_array, slong * n_interval, const fmpz_poly_t pol) |
|
| ✗ | void fmpz_poly_isolate_positive_roots (fmpz * exact_roots, slong * n_exact, fmpz * c_array, slong * k_array, slong * n_interval, const fmpz_poly_t pol) |
bound_roots is Fujiwara’s bound on the absolute values of the complex roots, and
positive_root_upper_bound_2exp returns an exponent \(e\) such that \(2^e\) bounds the positive
roots. The isolation functions return the exact integer roots and dyadic intervals
\((c \cdot 2^k, (c+1) \cdot 2^k)\) through five output parameters, and the counting functions
assume a square-free input.
Minimal polynomials
| FLINT | Malachite | |
|---|---|---|
| ✗ | void fmpz_poly_cyclotomic (fmpz_poly_t poly, ulong n) |
|
| ✗ | ulong fmpz_poly_is_cyclotomic (const fmpz_poly_t poly) |
|
| ✗ | void fmpz_poly_cos_minpoly (fmpz_poly_t poly, ulong n) |
|
| ✗ | void fmpz_poly_swinnerton_dyer (fmpz_poly_t poly, ulong n) |
is_cyclotomic returns the index \(n\), or 0 when the polynomial is not cyclotomic.
cos_minpoly gives the minimal polynomial of \(2\cos(2\pi/n)\), not \(\cos(2\pi/n)\), so that
it is monic with integer coefficients, and swinnerton_dyer has degree \(2^n\).
Orthogonal polynomials
| FLINT | Malachite | |
|---|---|---|
| ✗ | void fmpz_poly_chebyshev_t (fmpz_poly_t poly, ulong n) |
|
| ✗ | void fmpz_poly_chebyshev_u (fmpz_poly_t poly, ulong n) |
|
| ✗ | void fmpz_poly_legendre_pt (fmpz_poly_t poly, ulong n) |
|
| ✗ | void fmpz_poly_hermite_h (fmpz_poly_t poly, ulong n) |
|
| ✗ | void fmpz_poly_hermite_he (fmpz_poly_t poly, ulong n) |
hermite_h and hermite_he are the two Hermite conventions, \(H_n\) and \(He_n\), related by
\(He_n(x) = 2^{-n/2} H_n(x/\sqrt 2)\). legendre_pt is the shifted Legendre polynomial
\(\tilde{P}_n(x) = P_n(2x-1)\); the ordinary Legendre polynomials, which do not have integer
coefficients, are in fmpq_poly.
Fibonacci polynomials
| FLINT | Malachite | |
|---|---|---|
| ✗ | void fmpz_poly_fibonacci (fmpz_poly_t poly, ulong n) |
FLINT’s convention is \(F_0 = 0\), \(F_1 = 1\), \(F_n(x) = x F_{n-1}(x) + F_{n-2}(x)\), a
recurrence that can be run with
mul_power_of_x
and +. \(F_n(1)\) is the \(n\)th Fibonacci number, which
Fibonacci
provides directly.
Eulerian numbers and polynomials
| FLINT | Malachite | |
|---|---|---|
| ✗ | void fmpz_poly_eulerian_polynomial (fmpz_poly_t res, ulong n) |
\(A_n(x) = \sum_m A(n, m) x^m\), where the Eulerian number \(A(n, m)\) counts permutations of \(n\) elements with \(m\) descents; these are not the Euler numbers and polynomials.
Modular forms and q-series
| FLINT | Malachite | |
|---|---|---|
| ✗ | void fmpz_poly_eta_qexp (fmpz_poly_t f, slong r, slong n) |
|
| ✗ | void fmpz_poly_theta_qexp (fmpz_poly_t f, slong r, slong n) |
eta_qexp gives the \(q\)-expansion of \(\prod_{k \geq 1}(1 - q^k)^r\) (eta without its
fractional power of \(q\)) and theta_qexp that of \(\vartheta(q)^r\), with
\(\vartheta(q) = 1 + 2\sum_{k \geq 1} q^{k^2}\), both truncated to \(n\) terms. The exponent
\(r\) may be negative, and \(r = -1\) in eta_qexp gives the partition numbers. For
\(r \geq 0\), raising the \(r = 1\) series to the \(r\)th power with
pow_truncated
gives the same result.
CLD bounds
| FLINT | Malachite | |
|---|---|---|
| ✗ | void fmpz_poly_CLD_bound (fmpz_t res, const fmpz_poly_t f, slong n) |
fmpz_poly_CLD_bound bounds the \(n\)th coefficient of \(fg'/g\) for every factor \(g\) of
\(f\); it serves van Hoeij’s recombination step in factorisation.