Malachite for FLINT Users: Rational Vectors

This page maps the functions of FLINT’s rational vector module, fmpq_vec.h, onto their Malachite counterpart: RationalVector, from the malachite-q crate. It follows the organization of the fmpq_vec.h chapter of the FLINT manual, as of FLINT 3.6.0. It is a companion to Malachite for FLINT Users: Integer Vectors, whose conventions apply here as well, and to Malachite for FLINT Users: Rationals; the mapping index lists the whole family.

Every section of the chapter is mapped below: 13 rows across 8 sections, of which 8 are ✓, 3 ≈, 1 —, and 1 ✗. All of the chapter’s functions have names beginning with an underscore, and all are included (see Representation). The one ✗ row is a random generator, _fmpq_vec_randtest_uniq_sorted.

Conventions

Representation

fmpq_vec.h has no vector object. Every function works on a bare array, an fmpq * together with a separate slong length, which the caller allocates, tracks, and frees, and every function name begins with an underscore. As on the integer vector page, those functions are mapped here.

RationalVector is a single public field, elements, of type Vec<Rational>. Both libraries store the elements entrywise: each element is a rational number of its own, in lowest terms, rather than a numerator over a denominator shared by the whole vector, as in fmpq_poly. to_numerators_and_denominator gives the common-denominator form when it is wanted.

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.

Memory management

	FLINT	Malachite
✓	fmpq * _fmpq_vec_init(slong n)	zero
—	void _fmpq_vec_clear(fmpq * vec, slong n)

_fmpq_vec_init returns n zeros, each with denominator 1, which is zero, the Vector method that returns the zero vector of a given dimension: RationalVector::zero(n). _fmpq_vec_clear is Drop, which runs when the vector goes out of scope.

Randomisation

	FLINT	Malachite
≈	void _fmpq_vec_randtest(fmpq * f, flint_rand_t state, slong len, flint_bitcnt_t bits)	random_rational_vectors_with_dimension, striped_random_rational_vectors_with_dimension, random_rational_vectors_with_dimension_from_iterator
✗	void _fmpq_vec_randtest_uniq_sorted(fmpq * vec, flint_rand_t state, slong len, flint_bitcnt_t bits)

_fmpq_vec_randtest fills a vector of length len, drawing each element with fmpq_randtest, which caps the numerator and denominator at bits bits. Half the time it makes the vector sparse, exactly as _fmpz_vec_randtest does. Malachite’s counterparts are infinite iterators of vectors of a given dimension. The elements of the first two come from random_rationals or striped_random_rationals, which take a mean bit length with no cap, and there is no sparse mode, so the distributions differ. The third takes its elements from any iterator, so a bounded element stream, such as random_rational_range, gives a hard bound on the values.

_fmpq_vec_randtest_uniq_sorted produces distinct elements in ascending order. It draws a vector with _fmpq_vec_randtest, then repeatedly sorts it and redraws any element equal to its neighbour until none are. Malachite has no generator of distinct sorted vectors yet. The implementation throws an error unless bits is at least four times the bit length of len, a requirement the manual does not state; since FLINT counts the bit length of 0 as 1, this means bits must be at least 4 even when len is 0 or 1.

Bit sizes and heights

	FLINT	Malachite
✓	void _fmpq_vec_max_height(fmpz_t height, const fmpq * vec, slong len)	Height, HeightRef
✓	flint_bitcnt_t _fmpq_vec_max_height_bits(const fmpq * vec, slong len)	height_significant_bits

The height of a rational number \(p/q\) in lowest terms is \(\max(|p|, q)\), and max_height is the largest height of any element, with max_height_bits its bit length. These are Height’s to_height (or into_height) and height_significant_bits. Since every element is kept in lowest terms, the height is the numerator or denominator of one of the elements, so HeightRef lends it rather than building it. The index of an element of largest height, which this chapter does not provide, is height_index.

As in FLINT, the height of the 0-dimensional vector is 0. Every other vector has height at least 1, since every denominator is at least 1; a vector of zeros has height 1, the height of \(0 = 0/1\). Malachite’s RationalPolynomial gives its zero polynomial, which has no coefficients, height 1 rather than 0.

Comparison

	FLINT	Malachite
✓	int _fmpq_vec_equal(const fmpq * vec1, const fmpq * vec2, slong len)	PartialEq

_fmpq_vec_equal compares two arrays over a length the caller supplies; PartialEq on RationalVector also requires the dimensions to match. Since every element is kept in lowest terms, two vectors are equal exactly when their elements are identical. A RationalVector can also be compared with an IntegerVector, NaturalVector, or UnsignedVector, which it equals when it has the same dimension and the same values.

Sorting

	FLINT	Malachite
✓	void _fmpq_vec_sort(fmpq * vec, slong len)	sort

The manual does not say in which order _fmpq_vec_sort sorts; the implementation uses the C library’s qsort with fmpq_cmp, so the order is ascending by value, as for _fmpz_vec_sort. It is sort, a Vector method, which sorts in place by value.

Conversions

	FLINT	Malachite
✓	void _fmpq_vec_set_fmpz_vec(fmpq * res, const fmpz * vec, slong len)	From<IntegerVector>
✓	void _fmpq_vec_get_fmpz_vec_fmpz(fmpz * num, fmpz_t den, const fmpq * a, slong len)	to_numerators_and_denominator

_fmpq_vec_set_fmpz_vec converts each integer to a rational with denominator 1, which is From<IntegerVector>; the conversion takes the IntegerVector by value, so clone it first if it is still needed. The reverse, TryFrom<RationalVector> for IntegerVector, succeeds when every element is an integer, and has no counterpart in this chapter.

_fmpq_vec_get_fmpz_vec_fmpz writes a vector over a common denominator: the least common multiple of the elements’ denominators, with each numerator scaled to it. It is 1 for the empty vector. to_numerators_and_denominator computes the same denominator and numerators, returning them as an IntegerVector and a Natural; into_numerators_and_denominator consumes the vector instead of cloning its elements, and from_numerators_and_denominator converts back, a direction this chapter does not provide. fmpq_vec.h declares _fmpq_vec_get_fmpz_vec_fmpz twice, with identical prototypes.

Dot product

	FLINT	Malachite
✓	void _fmpq_vec_dot(fmpq_t res, const fmpq * vec1, const fmpq * vec2, slong len)	Dot

_fmpq_vec_dot sets res to \(\sum_i a_i b_i\), which is \(0\) for the empty vector. It is Dot’s v.dot(w) for RationalVector, with each vector taken by value or by reference; the vectors must have the same dimension. FLINT computes it with one fmpq_addmul per pair, each reducing to lowest terms (see fmpq_addmul). Dot instead writes each vector as integer numerators over a common denominator, takes one integer dot product, and reduces once. Unlike _fmpz_vec_dot, there is no _fmpq_vec_dot_general with an initial term, subtraction, or reversal.

Input and output

	FLINT	Malachite
≈	int _fmpq_vec_fprint(FILE * file, const fmpq * vec, slong len)	Display, Serialize
≈	int _fmpq_vec_print(const fmpq * vec, slong len)	Display, Serialize

The vector formats differ, hence ≈, as for integer vectors. FLINT writes the length, two spaces, and then the elements separated by single spaces, so \((1/2, -2, 3)\) is 3 1/2 -2 3 and the empty vector is 0. Malachite’s Display writes (1/2, -2, 3), with () for the 0-dimensional vector. The elements themselves are written the same way by both libraries, as p/q, or as just p when the denominator is 1. With the serde feature, RationalVector is serialized as a plain list of its elements.

Unlike fmpz_vec.h, this chapter has no functions for reading a vector. Malachite’s FromStr reads the form that Display writes, and Deserialize reads the serialized form.