Malachite for FLINT Users: Rationals
This page maps the functions of FLINT’s rational number type, fmpq_t, onto their Malachite
counterpart:
Rational, from
the malachite-q crate. It follows the organization of the
fmpq.h chapter of the FLINT manual, as of FLINT 3.6.0. It
is a companion to Malachite for FLINT Users: Integers on the FLINT
side and to Malachite for GMP Users: Rationals on the type’s side,
since both map onto the same Rational; the mapping index lists the whole family.
The conventions of the GMP rationals page and
the fmpz page, including word types and aliasing, apply
here as well. Functions whose names begin with an underscore are omitted.
Conventions
Canonical form, three ways
FLINT defines canonical form as Rational does: numerator and denominator coprime, a positive
denominator, and a denominator of one when the numerator is zero. GMP leaves canonicalization to
the caller after several assignment functions, as described on
the GMP rationals page. Every fmpq function assumes canonical inputs
and produces canonical outputs, but editing a component through fmpq_numref or fmpq_denref
leaves the caller responsible until fmpq_canonicalise is called. In Malachite component access
is mediated, so a non-canonical
Rational
cannot be built or observed, and the mapping below carries no canonicalization caveats.
The fmpq representation
An fmpq is a pair of fmpzs, each storing small values inline. A
Rational is a
sign and two
Naturals, each
inline below \(2^{64}\). The visible difference is where the sign lives: FLINT’s numerator is a
signed integer, while Malachite’s numerator and denominator are magnitudes with the sign held
separately, as discussed in
the accessor section of the
GMP rationals page.
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
The types are covered under Conventions.
| FLINT | Malachite | |
|---|---|---|
| ≈ | fmpz * fmpq_numref (const fmpq_t x) |
numerator_ref, mutate_numerator |
| ≈ | fmpz * fmpq_denref (const fmpq_t x) |
denominator_ref, mutate_denominator |
fmpq_numref, fmpq_denref. As for GMP’s mpq_numref and mpq_denref
(discussion): reading is
numerator_ref and denominator_ref, with the sign asked for separately; writing goes through
the mutate_* closures, which reduce the value when the closure returns, so the
canonicalisation FLINT leaves to the caller after such an edit is automatic.
Memory management
| FLINT | Malachite | |
|---|---|---|
| ✓ | void fmpq_init (fmpq_t x) |
Rational::ZERO |
| — | void fmpq_clear (fmpq_t x) |
fmpq_init, fmpq_clear. let x = Rational::ZERO;, the canonical zero, 0/1, that
fmpq_init produces; Default
also returns it. Dropping replaces clearing, as
on the GMP page.
Canonicalisation
| FLINT | Malachite | |
|---|---|---|
| — | void fmpq_canonicalise (fmpq_t res) |
|
| — | int fmpq_is_canonical (const fmpq_t x) |
Neither is needed, since a non-canonical
Rational
cannot exist: the
mutate_* closures
reduce on the way out, and panic rather than leave a zero denominator. Values arriving from
outside are checked: deserialization
validates canonical form.
Basic assignment
| FLINT | Malachite | |
|---|---|---|
| ✓ | void fmpq_set (fmpq_t dest, const fmpq_t src) |
Clone |
| — | void fmpq_swap (fmpq_t op1, fmpq_t op2) |
|
| ✓ | void fmpq_neg (fmpq_t dest, const fmpq_t src) |
Neg, NegAssign |
| ✓ | void fmpq_abs (fmpq_t dest, const fmpq_t src) |
Abs, AbsAssign |
| ✓ | void fmpq_zero (fmpq_t res) |
ZERO |
| ✓ | void fmpq_one (fmpq_t res) |
ONE |
dest = src.clone(), or dest.clone_from(&src) to reuse dest’s allocations;
std::mem::swap for the exchange;
-src and src.abs(), with their Assign forms in place; and res = Rational::ZERO or
Rational::ONE.
Comparison
The discussions on the GMP rationals page, of
Ordering replacing the
sign-carrying int and of the
Ord/PartialOrd
split, carry over. FLINT’s _fmpz, _si, and _ui forms compare against plain integers,
which the mixed
PartialOrd and
PartialEq implementations
take directly.
| FLINT | Malachite | |
|---|---|---|
| ✓ | int fmpq_is_zero (const fmpq_t res) |
PartialEq |
| ✓ | int fmpq_is_one (const fmpq_t res) |
PartialEq |
| ✓ | int fmpq_is_pm1 (const fmpq_t res) |
EqAbs |
| ✓ | int fmpq_equal (const fmpq_t x, const fmpq_t y) |
PartialEq |
| ✓ | int fmpq_equal_fmpz (const fmpq_t x, const fmpz_t y) |
PartialEq |
| ✓ | int fmpq_equal_si (fmpq_t x, slong y) |
PartialEq |
| ✓ | int fmpq_equal_ui (fmpq_t x, ulong y) |
PartialEq |
| ✓ | int fmpq_sgn (const fmpq_t x) |
Sign |
| ✓ | int fmpq_cmp (const fmpq_t x, const fmpq_t y) |
Ord |
| ✓ | int fmpq_cmp_fmpz (const fmpq_t x, const fmpz_t y) |
PartialOrd |
| ✓ | int fmpq_cmp_si (const fmpq_t x, slong y) |
PartialOrd |
| ✓ | int fmpq_cmp_ui (const fmpq_t x, ulong y) |
PartialOrd |
| ✓ | void fmpq_height (fmpz_t height, const fmpq_t x) |
Rational::to_height, Rational::into_height |
| ✓ | flint_bitcnt_t fmpq_height_bits (const fmpq_t x) |
Rational::height_significant_bits |
The predicates and comparisons. x == 0, x == 1, and x.eq_abs(&1) for the pm1 test;
== against another
Rational, an
Integer, or
any primitive; x.sign(); and < and friends for the orderings.
fmpq_height, fmpq_height_bits. The height is the larger of |p| and q. to_height
takes a reference and into_height consumes the value. height_significant_bits is
fmpq_height_bits, computed without materializing the height. Do not confuse it with
significant_bits,
which is the sum of the components’ bit counts.
Conversion
| FLINT | Malachite | |
|---|---|---|
| ✓ | void fmpq_set_fmpz_frac (fmpq_t res, const fmpz_t p, const fmpz_t q) |
from_integers |
| ≈ | void fmpq_get_mpz_frac (mpz_t a, mpz_t b, fmpq_t c) |
to_numerator_and_denominator |
| ✓ | void fmpq_set_si (fmpq_t res, slong p, ulong q) |
from_signeds, from_sign_and_unsigneds |
| ✓ | void fmpq_set_ui (fmpq_t res, ulong p, ulong q) |
from_unsigneds |
| — | void fmpq_set_mpq (fmpq_t dest, const mpq_t src) |
|
| ✓ | int fmpq_set_str (fmpq_t dest, const char * s, int base) |
FromStringBase, FromStr |
| ≈ | double fmpq_get_d (const fmpq_t f) |
RoundingFrom, TryFrom |
| — | void fmpq_get_mpq (mpq_t dest, const fmpq_t src) |
|
| ✓ | int fmpq_get_mpfr (mpfr_t dest, const fmpq_t src, mpfr_rnd_t rnd) |
from_rational_prec_round |
| ✓ | char * fmpq_get_str (char * str, int b, const fmpq_t x) |
ToStringBase, Display |
| — | void flint_mpq_init_set_readonly (mpq_t z, const fmpq_t f) |
|
| — | void flint_mpq_clear_readonly (mpq_t z) |
|
| — | void fmpq_init_set_readonly (fmpq_t f, const mpq_t z) |
|
| — | void fmpq_clear_readonly (fmpq_t f) |
The fraction constructors. fmpq_set_fmpz_frac is Rational::from_integers(p, q), and the
word-sized forms are from_unsigneds and from_signeds; all reduce on the way in, and a zero
denominator panics. fmpq_set_si takes a signed p over an unsigned q, and a q above
i64::MAX does not fit from_signeds; from_sign_and_unsigneds(p >= 0, p.unsigned_abs(), q)
covers the full range.
fmpq_get_mpz_frac. to_numerator_and_denominator, or into_numerator_and_denominator to
avoid the copy; the ≈ is the sign placement, FLINT’s a being signed where Malachite returns
magnitudes.
fmpq_get_d. Truncation toward zero: f64::rounding_from(&f, Down). Out of double range,
where FLINT’s result is “system dependent”, the
defined behavior described for mpq_get_d
applies.
fmpq_get_mpfr. Float::from_rational_prec_round(src, prec, rnd); the returned
Ordering is the sign of the
rounding that fmpq_get_mpfr returns.
fmpq_set_str, fmpq_get_str. Base 10 is
FromStr and
Display; other bases, 2 through
62, are from_string_base and to_string_base, as described on
the GMP rationals page. fmpq_set_str stores the
parsed numerator and denominator as given, leaving "2/4" unreduced and accepting a zero
denominator, where from_string_base reduces and returns None for a zero denominator. A bad
string is a -1 return there and None here, and fmpq_get_str’s allocated result becomes a
String.
The GMP boundary. fmpq_set_mpq, fmpq_get_mpq, and the four readonly functions are the
mpq_t edition of the boundary
described on the fmpz page: Malachite is not built on GMP,
so nothing corresponds, and interop routes through numerators and denominators, strings, or
serde.
Input and output
| FLINT | Malachite | |
|---|---|---|
| ✓ | int fmpq_fprint (FILE * file, const fmpq_t x) |
Display |
| ✓ | int fmpq_print (const fmpq_t x) |
Display |
fmpq_print, fmpq_fprint. print!("{x}"), or write!(f, "{x}") for any
Write, as
on the fmpz page; the success-or-failure int
becomes a Result. The formats agree exactly, including a bare integer when the denominator is
one (which FLINT’s manual does not mention).
Random number generation
The flint_rand_t state maps as it did
on the fmpz page: Malachite’s generators take a
Seed and return
infinite iterators. They live in
rational::random,
behind the random feature.
| FLINT | Malachite | |
|---|---|---|
| ≈ | void fmpq_randtest (fmpq_t res, flint_rand_t state, flint_bitcnt_t bits) |
random_rationals, striped_random_rationals |
| ≈ | void fmpq_randtest_not_zero (fmpq_t res, flint_rand_t state, flint_bitcnt_t bits) |
random_nonzero_rationals |
| ✓ | void fmpq_randbits (fmpq_t res, flint_rand_t state, flint_bitcnt_t bits) |
get_random_natural_with_bits, from_sign_and_naturals |
fmpq_randtest, fmpq_randtest_not_zero. FLINT caps the components at bits bits and
mixes in special values; Malachite’s generators draw component sizes from a geometric
distribution around a mean, with no hard cap, and the corner-case values come from the striped
generators, described on the GMP integers page.
random_nonzero_rationals is the not_zero variant.
fmpq_randbits. Draw the numerator and denominator with get_random_natural_with_bits,
choose a sign, and assemble with from_sign_and_naturals. As in FLINT, reduction can leave the
components “slightly smaller than bits bits”.
Arithmetic
As for GMP’s rationals, results are returned,
the *Assign traits cover the in-place case, and every operator has borrowing forms.
| FLINT | Malachite | |
|---|---|---|
| ✓ | void fmpq_add (fmpq_t res, const fmpq_t op1, const fmpq_t op2) |
Add, AddAssign |
| ✓ | void fmpq_sub (fmpq_t res, const fmpq_t op1, const fmpq_t op2) |
Sub, SubAssign |
| ✓ | void fmpq_mul (fmpq_t res, const fmpq_t op1, const fmpq_t op2) |
Mul, MulAssign |
| ✓ | void fmpq_div (fmpq_t res, const fmpq_t op1, const fmpq_t op2) |
Div, DivAssign |
| ✓ | void fmpq_add_si (fmpq_t res, const fmpq_t op1, slong c) |
Add |
| ✓ | void fmpq_sub_si (fmpq_t res, const fmpq_t op1, slong c) |
Sub |
| ✓ | void fmpq_add_ui (fmpq_t res, const fmpq_t op1, ulong c) |
Add |
| ✓ | void fmpq_sub_ui (fmpq_t res, const fmpq_t op1, ulong c) |
Sub |
| ✓ | void fmpq_add_fmpz (fmpq_t res, const fmpq_t op1, const fmpz_t c) |
Add |
| ✓ | void fmpq_sub_fmpz (fmpq_t res, const fmpq_t op1, const fmpz_t c) |
Sub |
| ✓ | void fmpq_mul_si (fmpq_t res, const fmpq_t op1, slong c) |
Mul |
| ✓ | void fmpq_mul_ui (fmpq_t res, const fmpq_t op1, ulong c) |
Mul |
| ✓ | void fmpq_addmul (fmpq_t res, const fmpq_t op1, const fmpq_t op2) |
AddMul, AddMulAssign |
| ✓ | void fmpq_submul (fmpq_t res, const fmpq_t op1, const fmpq_t op2) |
SubMul, SubMulAssign |
| ✓ | void fmpq_inv (fmpq_t dest, const fmpq_t src) |
Reciprocal, ReciprocalAssign |
| ✓ | void fmpq_pow_si (fmpq_t res, const fmpq_t op, slong e) |
Pow, PowAssign |
| ✓ | int fmpq_pow_fmpz (fmpq_t a, const fmpq_t b, const fmpz_t e) |
Pow, TryFrom |
| ✓ | void fmpq_mul_fmpz (fmpq_t res, const fmpq_t op, const fmpz_t x) |
Mul |
| ✓ | void fmpq_div_fmpz (fmpq_t res, const fmpq_t op, const fmpz_t x) |
Div |
| ✓ | void fmpq_mul_2exp (fmpq_t res, const fmpq_t x, flint_bitcnt_t exp) |
Shl, ShlAssign |
| ✓ | void fmpq_div_2exp (fmpq_t res, const fmpq_t x, flint_bitcnt_t exp) |
Shr, ShrAssign |
| ✓ | void fmpq_gcd (fmpq_t res, const fmpq_t op1, const fmpq_t op2) |
Gcd, GcdAssign |
| ≈ | void fmpq_gcd_cofactors (fmpq_t g, fmpz_t abar, fmpz_t bbar, const fmpq_t a, const fmpq_t b) |
ExtendedGcd |
The operators and mixed forms. op1 + op2 through op1 / op2, with division by zero a
panic where FLINT raises an error, and FLINT’s blanket aliasing permission answered by the
assign and by-value forms as
on the fmpz page. The ten mixed rows are one habit:
op1 + Rational::from(c), for c of any primitive or
Integer size,
with a by-value Integer donating its storage to the numerator.
fmpq_addmul, fmpq_submul. res += op1 * op2, or res.add_mul_assign(op1, op2);
neither library fuses the two steps.
fmpq_inv, fmpq_pow_si, fmpq_pow_fmpz. src.reciprocal(), and op.pow(e) with a
signed exponent; both libraries take \(0^0 = 1\). fmpq_pow_fmpz takes the exponent as a full
integer and reports failure instead of building an impossibly large result; as for
fmpz_pow_fmpz, convert with i64::try_from(&e),
let the conversion’s Err play the failure return, and handle the bases 0 and ±1 before
converting.
fmpq_mul_2exp, fmpq_div_2exp. x << exp and x >> exp, both exact.
fmpq_gcd, fmpq_gcd_cofactors. Gcd uses FLINT’s definition, the canonical form of
\(\gcd(ps, qr)/(qs)\) for \(p/q\) and \(r/s\), which for canonical values is
\(\gcd(p, r)/\operatorname{lcm}(q, s)\). The cofactor row is ≈ because the cofactors differ:
FLINT returns the integer quotients \(a/g\) and \(b/g\), while ExtendedGcd returns integer
Bézout cofactors \(u\) and \(v\) with \(ua + vb = g\). FLINT’s quotients are the exact divisions
a / &g and b / &g.
Modular reduction and rational reconstruction
| FLINT | Malachite | |
|---|---|---|
| ✓ | int fmpq_mod_fmpz (fmpz_t res, const fmpq_t x, const fmpz_t mod) |
ModInverse, ModMul |
| ✓ | int fmpq_reconstruct_fmpz_2 (fmpq_t res, const fmpz_t a, const fmpz_t m, const fmpz_t N, const fmpz_t D) |
Rational::reconstruct_with_bounds |
| ✓ | int fmpq_reconstruct_fmpz (fmpq_t res, const fmpz_t a, const fmpz_t m) |
Rational::reconstruct |
fmpq_mod_fmpz. The residue a with \(n \equiv a d \pmod m\): reduce the denominator,
invert it, and multiply by the reduced numerator, as on
the fmpz_mod page. FLINT’s failure return is
ModInverse’s
None: FLINT fails exactly when
the denominator has no inverse.
fmpq_reconstruct_fmpz_2, fmpq_reconstruct_fmpz. Given a residue a modulo m and
positive bounds N, D with \(2ND < m\), reconstruction finds the unique fraction n/d with
\(|n| \le N\), \(0 < d \le D\), \(\gcd(n, d) = 1\), and \(n \equiv ad \pmod m\), if one exists;
the shorter form uses \(N = D = \lfloor\sqrt{(m-1)/2}\rfloor\).
Rational::reconstruct_with_bounds_ref
and
Rational::reconstruct_ref
take their arguments by reference. FLINT’s success flag and out-parameter become an
Option: None is FLINT’s 0.
The residue is a
Natural, so
\(a \ge 0\) is carried by the type; the other preconditions, \(a < m\), positive bounds, and \(m > 2\) for the balanced form, are
panics. Within \(2ND < m\) the two libraries agree value for value. Outside it the answer is not
unique; there the mapped functions return what FLINT’s reference implementation,
_fmpq_reconstruct_fmpz_2_naive, returns, which fmpq_reconstruct_fmpz_2 may not.
Rational enumeration
FLINT’s next functions become infinite iterators in
rational::exhaustive,
each step an iterator’s next.
| FLINT | Malachite | |
|---|---|---|
| ✓ | void fmpq_next_minimal (fmpq_t res, const fmpq_t x) |
exhaustive_non_negative_rationals_by_height |
| ✓ | void fmpq_next_signed_minimal (fmpq_t res, const fmpq_t x) |
exhaustive_rationals_by_height |
| ✓ | void fmpq_next_calkin_wilf (fmpq_t res, const fmpq_t x) |
exhaustive_non_negative_rationals |
| ✓ | void fmpq_next_signed_calkin_wilf (fmpq_t res, const fmpq_t x) |
exhaustive_rationals |
| ✓ | void fmpq_farey_neighbors (fmpq_t l, fmpq_t r, const fmpq_t x, const fmpz_t Q) |
Rational::farey_neighbors |
| ≈ | void fmpq_simplest_between (fmpq_t x, const fmpq_t l, const fmpq_t r) |
SimplestRationalInInterval |
fmpq_next_calkin_wilf, fmpq_next_signed_calkin_wilf, fmpq_next_minimal,
fmpq_next_signed_minimal. Each iterator yields FLINT’s sequence term for term, from the
leading 0 on.
fmpq_farey_neighbors.
Rational::farey_neighbors
returns both neighbors as a pair; FLINT’s Q is max_denominator. FLINT’s throw on an input
whose denominator exceeds Q becomes a panic. Both libraries extend the Farey sequence to all
of \(\mathbb{Q}\), so the input may be negative or exceed 1.
fmpq_simplest_between. Rational::simplest_rational_in_closed_interval(&l, &r). The ≈ is
the tie-break when the minimal denominator is achieved more than once: FLINT takes the least
signed numerator, returning \(-1\) for \([-1, 1]\) and \(-7\) for \([-7, -3]\), while Malachite
prefers the numerator closest to zero and then the positive sign, returning 0 and \(-3\). When
only one fraction in the interval has the minimal denominator, the two agree.
Continued fractions
| FLINT | Malachite | |
|---|---|---|
| ✓ | slong fmpq_get_cfrac (fmpz * c, fmpq_t rem, const fmpq_t x, slong n) |
ContinuedFraction |
| ⚙ | slong fmpq_get_cfrac_naive (fmpz * c, fmpq_t rem, const fmpq_t x, slong n) |
ContinuedFraction |
| ✓ | void fmpq_set_cfrac (fmpq_t x, const fmpz * c, slong n) |
from_continued_fraction |
| — | slong fmpq_cfrac_bound (const fmpq_t x) |
fmpq_get_cfrac, fmpq_get_cfrac_naive. x.continued_fraction() returns the floor as an
Integer and
the remaining terms as an iterator of
Naturals,
where FLINT writes all coefficients into one vector with the possibly-negative \(c_0\) first.
FLINT’s incremental extraction, taking n terms and feeding the remainder back in, is the
suspended iterator. Both libraries generate the shorter of the two expansions every rational
has.
fmpq_set_cfrac. Rational::from_continued_fraction(floor, terms), with a _ref variant
that borrows the terms. FLINT asks that the coefficients after \(c_0\) be nonnegative, while
Malachite requires them positive.
fmpq_cfrac_bound. A preallocation bound for the coefficient vector; an iterator allocates
nothing ahead of time, so there is nothing to bound.
Special functions
| FLINT | Malachite | |
|---|---|---|
| ✓ | void fmpq_harmonic_ui (fmpq_t x, ulong n) |
Rational::harmonic_number(n) |
fmpq_harmonic_ui. Both libraries reject \(n \geq 2^{63}\).
arith_harmonic_number maps to the same
function.
Dedekind sums
| FLINT | Malachite | |
|---|---|---|
| ✓ | void fmpq_dedekind_sum (fmpq_t s, const fmpz_t h, const fmpz_t k) |
Rational::dedekind_sum(&h, &k) |
| — | void fmpq_dedekind_sum_naive (fmpq_t s, const fmpz_t h, const fmpz_t k) |
fmpq_dedekind_sum. The results agree exactly; both libraries return 0 for \(k \leq 2\),
negative \(k\) included.
fmpq_dedekind_sum_naive. A slow reference implementation of the defining sum; Malachite
keeps such implementations out of its public API.