NewYour coding agent can read the release notes before it upgrades.Set up the MCP server →
crates.io
crates.io, #3201 most downloaded on crates.io
A collection of utilities, including new arithmetic traits and iterators that generate all values of a type.
Latest stable
0.14.0
Last release 1 months ago
13 Oct 2026
Release timing varies
gaps range from 2 weeks to 5 months
Nearly every release is documented
notes for 44 of 44 stable releases
4 versions withdrawn
withdrawn after publishing
4 years old
48 releases · first in 2022
Drag across the ruler to compare, or tap a release to open it.
The headline of this release is vectors: four new types that bring most of FLINT's vector modules (fmpz_vec, fmpq_vec, fmpz_mod_vec, and nmod_vec) to
The headline of this release is vectors: four new types that bring most of FLINT's vector modules (fmpz_vec, fmpq_vec, fmpz_mod_vec, and nmod_vec) to Malachite. It also fixes a large slowdown in big-integer multiplication on x86 that has been present since 0.7.0.
The full list of changes is in the changelog.
UnsignedVector<T> (in malachite-base, over primitive unsigned integers), NaturalVector and IntegerVector (in malachite-nz), and RationalVector (in malachite-q).
elements field.(1, -2, 3), plus LaTeX, Typst, and serde.Vector trait, like Polynomial for the polynomial types: construction (zero, standard_basis_vector), dimension, is_zero, push, set_dimension, sort, max_bits, height_index, and more.AddMul/SubMul; reduction (Mod, BalancedMod, ModPowerOf2); and the full set of modular operations for UnsignedVector and NaturalVector.Dot, a DotSign that usually avoids computing the dot product at all, ElementSum, ElementProduct, ElementLcm, Content and the primitive part, Height, the ℓ¹ norm, the squared norm, and Chinese remaindering of residue vectors.EntrywiseAbs, EntrywiseMax/Min, EntrywiseDivRound, EntrywiseShrRound). They return only the vector, never a summary Ordering, since entries may round in different directions.The new vector mapping pages list FLINT's vector functions next to their Malachite counterparts. All but 7 of the 137 functions have a counterpart, or need none in Rust. The remaining 7 include reversed dot products and batch modular inversion, and are planned for the next release.
Since 0.7.0, Malachite has multiplied large integers with a port of FLINT's small-prime FFT. That algorithm relies on fused multiply-add and vector rounding instructions, which a defaultcargo build for x86_64 does not enable. Without them, the FFT was making a library call for every fused multiply-add, which made large multiplications several times slower on x86 than on aarch64.
The FFT kernels are now compiled twice on x86. At run time, Malachite checks whether the CPU supports AVX2 and FMA, and uses the fast kernels if it does. A default build now gets the same performance as one made with -C target-cpu=native. Other architectures, no_std builds, and builds that already enable these features are unaffected.
This change adds a small amount of unsafe code to malachite-nz, confined to one module: the CPU-checked entry into the AVX2 kernels and the vector type they use. The crate's forbid(unsafe_code) is now deny(unsafe_code), with an exception for that module only. The other crates still forbid unsafe entirely.
OrdProduct, OrdProducts, and their _neg variants compare $ab$ with $c$, or $ab$ with $cd$, for Natural, Integer, and Rational. Cheap checks decide most cases, and a multiplication happens only when they can't. The ports follow Azurite's compareProduct and compareProducts.Natural:
ModAddMul, ModSubMul, ModAddMulShl, and their power-of-2 forms);ModSum, ModProduct, and their power-of-2 forms), which UnsignedPolynomial and NaturalPolynomial also implement;ModPowerOf2Sqrt);BalancedModPowerOf2).AddMulShl and SubMulShl for Natural, Integer, and Rational, computing $x \pm yz2^k$.Product for Natural over iterators of primitive unsigned integers, which packs adjacent factors into words before multiplying.malachite_base::num::arithmetic::traits. On IntegerPolynomial and RationalPolynomial, primitive_part no longer normalizes the sign; the old behavior, with a non-negative leading coefficient as in FLINT, is now canonical_primitive_part.exhaustive_vecs does. The order of their outputs has changed, and about half of the outputs are now constants.PrimitiveUnsigned and PrimitiveInt require more traits, covering the new modular and balanced operations above. This only affects code that implements these traits for types outside Malachite.wide version is now 1.7.1.Your coding agent can read these notes before it upgrades. Set up the MCP server →
malachite-nz now contains unsafe code, in one module: the AVX2 instantiation of the FFT
multiplication (natural/arithmetic/mul/fft/avx2.rs). The crate-level forbid(unsafe_code) has
become deny(unsafe_code), with allow on that module and on the two functions that enter it
after checking the CPU. Everything else is unchanged.exhaustive_vecs_with_last and its _min_length, _length_range, _length_inclusive_range,
and _from_length_iterator variants now step through the lengths with a ruler_sequence, as
exhaustive_vecs does, instead of a bit_distributor_sequence, so the lengths grow
logarithmically rather than as the cube root of the iteration number. The exhaustive polynomial
generators (exhaustive_unsigned_polynomials, exhaustive_natural_polynomials,
exhaustive_integer_polynomials, exhaustive_rational_polynomials, and their _min_degree and
_from_iterators variants) change with them: half of their output is now constants. The
bit-distributor rate generated many long polynomials whose coefficients were all 0s and 1s.malachite_base::num::arithmetic::traits. malachite_base::polynomial::Content, PrimitivePart,
PrimitivePartAssign, and ContentAndPrimitivePart are gone; Content and the plain
PrimitivePart, PrimitivePartAssign, and ContentAndPrimitivePart live in
num::arithmetic::traits, alongside the new CanonicalPrimitivePart,
CanonicalPrimitivePartAssign, and ContentAndCanonicalPrimitivePart.primitive_part, primitive_part_assign, and content_and_primitive_part on IntegerPolynomial
and RationalPolynomial no longer normalize the sign: they divide by the content and leave every
coefficient's sign alone, so $p = \operatorname{cont}(p)\operatorname{pp}(p)$ exactly. The old
behavior, with a non-negative leading coefficient as in FLINT's fmpz_poly_primitive_part, is
now canonical_primitive_part, canonical_primitive_part_assign, and
content_and_canonical_primitive_part. On UnsignedPolynomial<T> and NaturalPolynomial the two
agree.CanonicalUnitIPow docs now describe what the power of $i$ brings a number into as its
canonical Gaussian-unit form: the Gaussian associate, under the units $\pm 1$ and $\pm i$ of the
Gaussian integers, whose argument lies in $(-\pi/4, \pi/4]$. They used to call it the canonical
unit form, which since 0.13.0 is 1 for every nonzero element of a field, so that for Rational,
GaussianRational, and Float the two no longer agreed. The functions themselves are unchanged.PrimitiveInt now requires BalancedModPowerOf2, PrimitiveUnsigned requires it with a signed
output, and PrimitiveSigned requires BalancedModPowerOf2<Output = Self> and
BalancedModPowerOf2Assign, as they already required BalancedMod. A type outside Malachite that
implements these traits must now implement the new ones too.PrimitiveUnsigned now requires ModPowerOf2Sqrt<Output = Self>, as it already required
ModPowerOf2Inverse. A type outside Malachite that implements PrimitiveUnsigned must now
implement it too.PrimitiveUnsigned now requires ModPowerOf2AddMul, ModPowerOf2AddMulAssign,
ModPowerOf2SubMul, and ModPowerOf2SubMulAssign, as it already required ModPowerOf2Mul. A
type outside Malachite that implements PrimitiveUnsigned must now implement them too.PrimitiveUnsigned now requires ModAddMul, ModAddMulAssign, ModSubMul, and
ModSubMulAssign, as it already required ModMul. A type outside Malachite that implements
PrimitiveUnsigned must now implement them too.PrimitiveUnsigned now requires ModPowerOf2AbsSquared<Output = Self>,
ModPowerOf2AbsSquaredAssign, ModAbsSquared<Self, Output = Self>, and
ModAbsSquaredAssign<Self>. A type outside Malachite that implements PrimitiveUnsigned must now
implement them too.PrimitiveUnsigned now requires ModProduct<Self, Self> and for<'a> ModProduct<&'a Self, Self>.
A type outside Malachite that implements PrimitiveUnsigned must now implement them too.PrimitiveUnsigned now requires ModPowerOf2Product and for<'a> ModPowerOf2Product<&'a Self>.
A type outside Malachite that implements PrimitiveUnsigned must now implement them too.PrimitiveUnsigned now requires ModSum<Self, Self> and for<'a> ModSum<&'a Self, Self>. A
type outside Malachite that implements PrimitiveUnsigned must now implement them too.PrimitiveUnsigned now requires ModPowerOf2Sum and for<'a> ModPowerOf2Sum<&'a Self>. A type
outside Malachite that implements PrimitiveUnsigned must now implement them too.PrimitiveUnsigned now requires ModAddMulShl, ModAddMulShlAssign, ModSubMulShl, and
ModSubMulShlAssign. A type outside Malachite that implements PrimitiveUnsigned must now
implement them too.PrimitiveUnsigned now requires ModPowerOf2AddMulShl, ModPowerOf2AddMulShlAssign,
ModPowerOf2SubMulShl, and ModPowerOf2SubMulShlAssign. A type outside Malachite that implements
PrimitiveUnsigned must now implement them too.exhaustive_vecs_with_index_generator and exhaustive_vecs_with_last_with_index_generator,
which generate all [Vec]s, the second with its last element drawn from a different iterator
than the rest, with the lengths stepped by a caller-supplied iterator of indices, such as a
bit_distributor_sequence. exhaustive_vecs and exhaustive_vecs_with_last are these with a
ruler_sequence.Vector trait in malachite_base::vector, for what every vector type has in common, as
Polynomial is for the polynomial types. It has an Element associated type and the methods
from_elements, from_owned_elements, zero, standard_basis_vector, to_elements,
into_elements, elements_ref, dimension, is_zero, pivot, pivot_index, height_index,
standard_basis_index, max_bits, sum_max_bits, push, set_dimension, set_zero, and
sort; the vector types implement these through the trait, so calling them takes use malachite_base::vector::Vector;. zero(dimension) returns the zero vector of a given dimension,
like FLINT's fmpz_vec_init, and standard_basis_vector(dimension, index) returns the vector
with a 1 at index and 0 elsewhere. push appends an element, like FLINT's fmpz_vec_append,
and set_dimension truncates or pads with zeros, like fmpz_vec_set_length. set_zero sets
every element to zero, keeping the dimension, like _fmpz_vec_zero and _nmod_vec_zero, and
is_zero tests for the zero vector, like _fmpz_vec_is_zero. sort sorts the elements in
ascending order, like _fmpz_vec_sort and _fmpq_vec_sort. standard_basis_index returns the
index of the 1 in a standard basis vector, and None for any other vector. height_index returns
the index of the first element of largest height, like FLINT's _fmpz_vec_height_index.
max_bits returns the bit length of the height together with whether any element is negative, the
two facts that FLINT's _fmpz_vec_max_bits combines into one signed count. sum_max_bits returns
the bit lengths of the sum of the absolute values of the elements and of the height, like
_fmpz_vec_sum_max_bits.ContentChained<T> trait in malachite_base::num::arithmetic::traits, for the GCD of a value
and the content of another, which accumulates the common content of several values one at a
time.WideningElementProduct<T> trait in malachite_base::num::arithmetic::traits, for the product
of the elements of a vector as a value of a wider type T, so that it cannot overflow, with
to_widening_element_product and into_widening_element_product.ModPowerOf2ElementProduct and ModElementProduct traits in
malachite_base::num::arithmetic::traits, for the product of the elements of a vector modulo
$2^k$ or modulo $m$, as a single element, with to_ and into_ forms. The elements must already
be reduced.ModPowerOf2ElementSum and ModElementSum traits in malachite_base::num::arithmetic::traits,
for the sum of the elements of a vector modulo $2^k$ or modulo $m$, as a single element, with
to_ and into_ forms. The elements must already be reduced.OrdProductsNeg trait in malachite_base::num::comparison::traits, whose associated function
cmp_products_neg(&a, &b, &c, &d) compares $ab$ with $-cd$ (the sign of $ab + cd$) without
computing the negative.OrdProductNeg trait in malachite_base::num::comparison::traits, whose associated function
cmp_product_neg(&a, &b, &c) compares $ab$ with $-c$ (the sign of $ab + c$) without computing
the negative.OrdProducts trait in malachite_base::num::comparison::traits, whose associated function
cmp_products(&a, &b, &c, &d) compares $ab$ with $cd$ without computing the products unless
cheaper checks cannot decide.OrdProduct trait in malachite_base::num::comparison::traits, whose associated function
cmp_product(&a, &b, &c) compares $ab$ with $c$ without computing the product unless cheaper
checks cannot decide.ModPowerOf2AbsSquared, ModPowerOf2AbsSquaredAssign, ModAbsSquared, and ModAbsSquaredAssign
traits in malachite_base::num::arithmetic::traits, for the squared absolute value modulo $2^k$
or modulo $m$, implemented for every primitive unsigned type. For a real number this is the
modular square; the traits are for types where it is not, such as vectors.ModPowerOf2Dot and ModDot traits in malachite_base::num::arithmetic::traits, for the dot
product of two vectors modulo $2^k$ or modulo $m$. The elements must already be reduced.DotSign trait in malachite_base::num::arithmetic::traits, for the sign of the dot product of
two vectors, as its ordering against 0, without computing the dot product when it can be avoided.Dot trait in malachite_base::num::arithmetic::traits, for the dot product of two vectors.ElementLcm trait in malachite_base::num::arithmetic::traits, for the LCM of the elements
of a vector, with to_element_lcm and into_element_lcm.ElementProduct trait in malachite_base::num::arithmetic::traits, for the product of the
elements of a vector, as a single element, with to_element_product and into_element_product.ElementSum trait in malachite_base::num::arithmetic::traits, for the sum of the elements of
a vector, as a single element, with to_element_sum and into_element_sum. It is distinct from
Sum, which adds vectors to each other.L1Norm trait in malachite_base::num::arithmetic::traits, for the $\ell^1$ norm of a value:
the sum of the absolute values of the parts it is built from, such as the elements of a vector.
It has to_l1_norm, into_l1_norm, and l1_norm_significant_bits, mirroring Height.SelectCoordinates and SelectCoordinatesAssign traits in malachite_base::vector, for
selecting the coordinates of a vector by a list of indices, which may repeat and appear in any
order, so that projection, permutation, and duplication of coordinates are all selections. The
by-value and in-place forms move elements rather than cloning them wherever possible: strictly
increasing indices are handled in place, and otherwise an element is cloned only once for each
extra time it is selected. Implemented for UnsignedVector<T>.UnsignedVector<T>, a vector whose elements are primitive unsigned integers. Its elements
field is public, since every [Vec] is a valid vector. It implements Vector, Index and
IndexMut, and has conversions to and from strings ((1, 2, 3), with () for the 0-dimensional
vector), LaTeX and Typst, and serde. It does not implement Ord; the ShortlexUnsignedVector
and ShortlexUnsignedVectorRef wrappers order vectors by dimension and then lexicographically.
Generators: exhaustive_unsigned_vectors, random_unsigned_vectors, and
striped_random_unsigned_vectors, each with a _with_dimension variant.IntoIterator (by value, by reference, and by mutable reference), FromIterator, and Extend
for UnsignedVector<T>, so that a vector can be iterated over with for, collected from an
iterator, and extended by one.Height for UnsignedVector<T>: the largest element, like FLINT's _fmpz_vec_height, with
height_significant_bits like _nmod_vec_max_bits.SignificantBits for UnsignedVector<T>: the sum of the numbers of significant bits of the
elements.SignificantBits for UnsignedPolynomial<T>: the sum of the numbers of significant bits of the
coefficients.random_unsigned_vectors_from_iterator and
random_unsigned_vectors_with_dimension_from_iterator, which take the elements of
UnsignedVector<T>s from any iterator, for example one with bounded elements. The other
UnsignedVector<T> generators are built on them.ModPowerOf2 (by value and by reference), ModPowerOf2Assign, and ModPowerOf2IsReduced for
UnsignedVector<T>, reducing every element modulo $2^k$ while keeping the dimension, and checking
whether every element is less than $2^k$.Rem, RemAssign, Mod, and ModAssign for UnsignedVector<T> with a T modulus, reducing
every element modulo $m$ and keeping the dimension; and ModIsReduced<T> for UnsignedVector<T>,
checking whether every element is less than $m$.ModPowerOf2Neg (by value and by reference) and ModPowerOf2NegAssign for UnsignedVector<T>,
negating every element modulo $2^k$.ModAdd<_, T> and ModAddAssign<_, T> for UnsignedVector<T>, in every combination of value
and reference, adding two vectors of the same dimension modulo $m$.ModSub<_, T> and ModSubAssign<_, T> for UnsignedVector<T>, in every combination of value
and reference, subtracting two vectors of the same dimension modulo $m$.ModNeg<T> (by value and by reference) and ModNegAssign<T> for UnsignedVector<T>, negating
every element modulo $m$.ModPowerOf2Add and ModPowerOf2AddAssign for UnsignedVector<T>, in every combination of
value and reference, adding two vectors of the same dimension modulo $2^k$.ModPowerOf2Sub and ModPowerOf2SubAssign for UnsignedVector<T>, in every combination of
value and reference, subtracting two vectors of the same dimension modulo $2^k$.PrimitivePartAssign, CanonicalPrimitivePart, CanonicalPrimitivePartAssign, and
ContentAndCanonicalPrimitivePart traits. The canonical primitive part is the primitive part in
canonical unit form, as CanonicalizeUnit chooses it: for polynomials over the integers or
rationals, the one with a non-negative leading coefficient; for vectors, the one whose first
nonzero element is positive; for Gaussian integers and rationals, the one whose argument lies in
$(-\pi/4, \pi/4]$.Content, PrimitivePart, PrimitivePartAssign, ContentAndPrimitivePart, and their canonical
counterparts for UnsignedVector<T>, and the canonical ones for UnsignedPolynomial<T>.CanonicalizeGaussianUnit and CanonicalizeGaussianUnitAssign, which multiply a number by the
power of $i$ that CanonicalUnitIPow finds, bringing it into canonical Gaussian-unit form; for a
real number that is its absolute value. Implemented for the primitive integers and floats,
Natural, Integer, Rational, Float, GaussianInteger, and GaussianRational. For
GaussianInteger this is canonicalize_unit; for GaussianRational it is what
canonicalize_unit did before 0.13.0.CanonicalizeSign and CanonicalizeSignAssign, which negate a value if it is negative; for a
vector, "negative" means that its pivot is. Implemented for IntegerVector and RationalVector.BalancedModPowerOf2 and BalancedModPowerOf2Assign traits in
malachite_base::num::arithmetic::traits, the power-of-2 counterparts of BalancedMod and
BalancedModAssign, as ModPowerOf2 is of Mod. The balanced remainder modulo $2^k$ lies in
$(-2^{k-1}, 2^{k-1}]$, with the tie positive, so it equals balanced_mod with modulus $2^k$.
Implemented for the primitive integers, unsigned types returning the signed type of the same
width; a result that does not fit, $2^{W-1}$, panics.EntrywiseAbs, EntrywiseAbsAssign, and EntrywiseUnsignedAbs traits in
malachite_base::num::arithmetic::traits, which replace every entry of a value, such as every
element of a vector, by its absolute value. They are separate from Abs, which for a vector
would be its Euclidean length.EntrywiseMax and EntrywiseMaxAssign traits in malachite_base::num::arithmetic::traits, for
the value whose every entry is the larger of the corresponding entries of two values, such as
two vectors of the same dimension, and EntrywiseMin and EntrywiseMinAssign for the smaller.
Implemented for UnsignedVector<T>, in every combination of value and reference.EntrywiseShlRound, EntrywiseShlRoundAssign, EntrywiseShrRound, and
EntrywiseShrRoundAssign traits in malachite_base::num::arithmetic::traits, for shifting every
entry of a vector and rounding each according to a RoundingMode. Unlike ShlRound and
ShrRound, they return no Ordering, since entries may round in different directions.ModPowerOf2Sqrt trait in malachite_base::num::arithmetic::traits, for the least square root
of a number modulo $2^k$, implemented for every primitive unsigned type by 2-adic Newton
iteration on the odd part, following Azurite's AzZModPow2.sqrt?.ModPowerOf2AddMul, ModPowerOf2AddMulAssign, ModPowerOf2SubMul, and
ModPowerOf2SubMulAssign traits in malachite_base::num::arithmetic::traits, for computing
$x + yz$ and $x - yz$ modulo $2^k$, implemented for every primitive unsigned type. All three
arguments must already be reduced.AddMulShl, AddMulShlAssign, SubMulShl, and SubMulShlAssign traits in
malachite_base::num::arithmetic::traits, for computing $x + yz2^k$ and $x - yz2^k$, the scalar
operations behind FLINT's _fmpz_vec_scalar_addmul_si_2exp and _fmpz_vec_scalar_submul_si_2exp.ModPowerOf2AddMulShl, ModPowerOf2AddMulShlAssign, ModPowerOf2SubMulShl, and
ModPowerOf2SubMulShlAssign traits in malachite_base::num::arithmetic::traits, for computing
$x + yz2^b$ and $x - yz2^b$ modulo $2^k$, implemented for every primitive unsigned type. All
three arguments must already be reduced.ModPowerOf2Product trait in malachite_base::num::arithmetic::traits, for multiplying together
the numbers in an iterator modulo $2^k$, like Product, for iterators of values or of
references; implemented for every primitive unsigned type. Every number must already be reduced,
and the product of no numbers is 1 reduced modulo $2^k$. It returns as soon as the partial
product is zero, without examining the remaining numbers.ModProduct trait in malachite_base::num::arithmetic::traits, for multiplying together the
numbers in an iterator modulo another number, like Product, for iterators of values or of
references; implemented for every primitive unsigned type, reusing the data for multiplying
modulo $m$. Every number must already be reduced, the modulus must be positive, the product of no
numbers is 1 reduced modulo $m$, and it returns as soon as the partial product is zero.ModSum trait in malachite_base::num::arithmetic::traits, for adding up the numbers in an
iterator modulo another number, like Sum, for iterators of values or of references; implemented
for every primitive unsigned type. Every number must already be reduced, and the modulus must be
positive.ModPowerOf2Sum trait in malachite_base::num::arithmetic::traits, for adding up the numbers
in an iterator modulo $2^k$, like Sum, for iterators of values or of references; implemented
for every primitive unsigned type. Every number must already be reduced.ModAddMulShl, ModAddMulShlAssign, ModSubMulShl, and ModSubMulShlAssign traits in
malachite_base::num::arithmetic::traits, for computing $x + yz2^b$ and $x - yz2^b$ modulo $m$,
implemented for every primitive unsigned type. All three arguments must already be reduced.ModAddMul, ModAddMulAssign, ModSubMul, and ModSubMulAssign traits in
malachite_base::num::arithmetic::traits, for computing $x + yz$ and $x - yz$ modulo $m$,
implemented for every primitive unsigned type. All three arguments must already be reduced.EntrywiseDivRound and EntrywiseDivRoundAssign traits in
malachite_base::num::arithmetic::traits, for dividing every entry of a value, such as a vector,
by a scalar and rounding each quotient according to a RoundingMode. Unlike DivRound, they
return no Ordering, since entries may round in different directions.ModPowerOf2Mul and ModPowerOf2MulAssign of UnsignedVector<T> by a T, multiplying every
element modulo $2^k$. The elements and the scalar must already be reduced.ModPowerOf2AddMul, ModPowerOf2AddMulAssign, ModPowerOf2SubMul, and
ModPowerOf2SubMulAssign for UnsignedVector<T>, adding or subtracting a T multiple of one
vector to or from another modulo $2^k$. The elements and the scalar must already be reduced.ModPowerOf2AddMulShl, ModPowerOf2AddMulShlAssign, ModPowerOf2SubMulShl, and
ModPowerOf2SubMulShlAssign for UnsignedVector<T>, adding or subtracting a T multiple of one
vector, shifted left, to or from another modulo $2^k$. The elements and the scalar must already
be reduced.ModPowerOf2ElementProduct and ModElementProduct for UnsignedVector<T>: the product of the
elements modulo $2^k$ or modulo $m$, as a T. The product of the 0-dimensional vector is 1,
reduced, and it returns as soon as the partial product is zero.ModPowerOf2AbsSquared and ModAbsSquared for UnsignedVector<T>: the squared norm modulo $2^k$
or modulo $m$, computed as the modular dot product of the vector with itself.ModPowerOf2Dot and ModDot for UnsignedVector<T>: the dot product modulo $2^k$ (a wrapping
sum of wrapping products, masked once) or modulo $m$ (like FLINT's _nmod_vec_dot, the products
summed exactly in one to three words and reduced once).ModPowerOf2ElementSum and ModElementSum for UnsignedVector<T>: the sum of the elements
modulo $2^k$ or modulo $m$, as a T. The sum of the 0-dimensional vector is 0.ModSum for UnsignedVector<T>, for iterators of vectors or of references, with a T
modulus: the entrywise sum modulo $m$ of vectors of the same dimension. An empty iterator
panics.ModPowerOf2Sum for UnsignedVector<T>, for iterators of vectors or of references: the
entrywise sum modulo $2^k$ of vectors of the same dimension. An empty iterator panics, since the
dimension of its sum is unknown.ModAddMulShl, ModAddMulShlAssign, ModSubMulShl, and ModSubMulShlAssign for
UnsignedVector<T>, adding or subtracting a T multiple of one vector, shifted left, to or from
another modulo a T. The elements and the scalar must already be reduced.ModAddMul, ModAddMulAssign, ModSubMul, and ModSubMulAssign for UnsignedVector<T>,
adding or subtracting a T multiple of one vector to or from another modulo a T, like FLINT's
_nmod_vec_scalar_addmul_nmod. The elements and the scalar must already be reduced.ModMul and ModMulAssign of UnsignedVector<T> by a T modulo a T, multiplying every
element modulo $m$ with the multiplication data for $m$ computed once, like FLINT's
_nmod_vec_scalar_mul_nmod. The elements and the scalar must already be reduced.ModPowerOf2Shl and ModPowerOf2ShlAssign for UnsignedVector<T>, by any primitive unsigned
type, shifting every element left modulo $2^k$. The elements must already be reduced.ModShl and ModShlAssign for UnsignedVector<T>, by any primitive unsigned type, modulo a
T, computing $2^k \bmod m$ once and multiplying every element by it. The elements must already
be reduced.Shr (by value and by reference) and ShrAssign for UnsignedVector<T>, by any primitive
unsigned type, taking the floor of every element; shifting by at least T::WIDTH zeroes every
element. There is no non-modular left shift, since it could overflow.EntrywiseShrRound (by value and by reference) and EntrywiseShrRoundAssign for
UnsignedVector<T>, by any primitive unsigned type, rounding every element according to a
RoundingMode.DivExact (by value and by reference) and DivExactAssign of UnsignedVector<T> by a T,
dividing every element by a scalar that divides it exactly.Div (by value and by reference) and DivAssign of UnsignedVector<T> by a T, rounding every
quotient down, and EntrywiseDivRound (by value and by reference) and EntrywiseDivRoundAssign
by a T, rounding every quotient according to a RoundingMode.Naturals (and the FFT multiplication of
IntegerPolynomials) now detects AVX2 and FMA at run time and uses kernels compiled for them. The
small-prime FFT depends on fused multiply-adds and vector rounding; a default cargo build for
x86_64 enables neither, so every one of them had been a library call, which made the FFT several
times slower than on aarch64. Such builds now run the same code twice compiled: once for the
features the crate is built with and once for AVX2 and FMA, selecting the second when the CPU has
them. Builds with -C target-feature=+avx2,+fma or -C target-cpu=native, builds without std
(which provides the detection), and other architectures are unaffected. The FFT module is split
into fft/mod.rs (contexts, tables, dispatch), fft/body.rs (the kernels), fft/baseline.rs
and fft/avx2.rs (the vector primitives of each backend), and fft/avx2_body.rs, a generated
copy of body.rs with #[target_feature] on every function, kept in sync by a test.wide's simd_gt, simd_lt, and
select), as FLINT does. Large multiplications are about 2% faster on aarch64. This raises the
minimum wide version to 1.7.1, which is where that API appeared.NaturalVector and IntegerVector, with the same API as UnsignedVector<T>: public
elements, the Vector trait, Index, strings, LaTeX, Typst, serde, Shortlex* wrappers, and
exhaustive, random, and striped random generators.IntoIterator (by value, by reference, and by mutable reference), FromIterator, and Extend
for NaturalVector and IntegerVector, so that a vector can be iterated over with for,
collected from an iterator, and extended by one.SelectCoordinates (by value and by reference) and SelectCoordinatesAssign for NaturalVector
and IntegerVector.Height and HeightRef for NaturalVector and IntegerVector: the largest absolute value of an
element, like FLINT's _fmpz_vec_height. The height of the 0-dimensional vector is 0.AbsSquared for NaturalVector, IntegerVector, and RationalVector: the squared norm, the sum
of the squares of the elements, as a Natural (for the natural and integer vectors) or a
Rational. It is the dot product of the vector with itself, which squares each element rather
than multiplying it by itself; the rational version works over a common denominator and reduces
once.DotSign for IntegerVector, with as few multiplications as possible: the terms are split by
sign, and an empty side, one term on each side (Natural::cmp_products), or bit lengths far
enough apart decide without any product; otherwise the largest term is weighed against the dot
product of the rest with Integer::cmp_product_neg.DotSign for NaturalVector: Greater exactly when some coordinate is nonzero in both vectors,
found in one pass with no multiplication, following Azurite's dotSign.Dot for NaturalVector and IntegerVector, like FLINT's _fmpz_vec_dot, summing small products
in a three-limb accumulator and the rest in limb buffers. The vectors must have the same
dimension.ElementLcm for NaturalVector and IntegerVector: the LCM of the elements' absolute values,
like FLINT's _fmpz_vec_lcm. The LCM of the 0-dimensional vector is 1, and it is 0, found as
soon as a zero element is reached, if any element is 0.ElementProduct for NaturalVector and IntegerVector: the product of the elements, like
FLINT's _fmpz_vec_prod, multiplied in a balanced tree and stopping at a zero element. The
product of the 0-dimensional vector is 1.Product<T> and Product<&T> for Natural, for every unsigned primitive integer type T: the
product of the integers in an iterator as a Natural, like FLINT's _fmpz_ui_vec_prod. Adjacent
factors are multiplied as words while their product fits in one, the words are combined in a
balanced tree, and it stops at a zero factor.ContentChained for UnsignedVector<T>, NaturalVector, IntegerVector, and RationalVector:
the GCD of a given number and the elements, like FLINT's _fmpz_vec_content_chained, stopping as
soon as it reaches 1.WideningElementProduct<Natural> for UnsignedVector<T>: the product of the elements as a
Natural, through the Product above.ModPowerOf2ElementProduct and ModElementProduct for NaturalVector: the product of the
elements modulo $2^k$ or modulo $m$, as a Natural, with the modulus by value or by reference.
The product of the 0-dimensional vector is 1, reduced, and it returns as soon as the partial
product is zero.OrdProducts and OrdProductsNeg for Rational, comparing $wx$ with $yz$ or $-yz$ without
forming either product: after the signs, the eight numerator and denominator factors are screened
by bit lengths and pairwise comparisons, following Azurite's AzRat compareProducts.OrdProduct and OrdProductNeg for Rational, comparing $xy$ with $z$ or $-z$ without reducing
a product: after the signs, the six numerator and denominator factors are screened by bit
lengths and pairwise comparisons before any multiplication, following Azurite's AzRat
compareProduct.OrdProducts and OrdProductsNeg for Integer: the signs decide every case except two nonzero
products of the same sign, which Natural::cmp_products decides, following Azurite's AzInt
compareProducts.OrdProduct and OrdProductNeg for Integer: the signs decide every case except a nonzero product
and $c$ of the same sign, which Natural::cmp_product decides, following Azurite's AzInt
compareProduct.OrdProducts for Natural, deciding by a zero factor, by either pairing of the factors, or by the
bit lengths before multiplying, following Azurite's compareProducts.ModPowerOf2AbsSquared, ModPowerOf2AbsSquaredAssign, ModAbsSquared, and ModAbsSquaredAssign
for Natural, which are the modular squares.OrdProduct for Natural, deciding by a zero or unit factor, a factor at least $c$, or the bit
lengths before multiplying, following Azurite's compareProduct.ModPowerOf2AbsSquared and ModAbsSquared for NaturalVector: the squared norm modulo $2^k$ or
modulo $m$, computed as the modular dot product of the vector with itself.ModPowerOf2Dot and ModDot for NaturalVector, like FLINT's _fmpz_mod_vec_dot: word
arithmetic when the modulus fits in a limb, and otherwise the exact dot product reduced once.ModPowerOf2ElementSum and ModElementSum for NaturalVector: the sum of the elements modulo
$2^k$ or modulo $m$, as a Natural, with the modulus by value or by reference. The sum of the
0-dimensional vector is 0.ElementSum for NaturalVector and IntegerVector: the sum of the elements, like FLINT's
_fmpz_vec_sum. The sum of the 0-dimensional vector is 0.L1Norm for NaturalVector and IntegerVector: the sum of the absolute values of the elements,
as a Natural. l1_norm_significant_bits adds the elements in two words while each fits in one,
like FLINT's _fmpz_vec_sum_max_bits.SignificantBits for NaturalVector and IntegerVector: the sum of the numbers of significant
bits of the elements.SignificantBits for NaturalPolynomial and IntegerPolynomial: the sum of the numbers of
significant bits of the coefficients.random_natural_vectors_from_iterator, random_integer_vectors_from_iterator, and their
_with_dimension_from_iterator variants, which take the elements from any iterator, for example
one with bounded elements. The other NaturalVector and IntegerVector generators are built on
them.From<UnsignedVector<T>> for NaturalVector and IntegerVector, and From<NaturalVector> for
IntegerVector.TryFrom<NaturalVector> and TryFrom<&NaturalVector> for UnsignedVector<T>, failing with
UnsignedVectorFromNaturalVectorError when an element is too large for T, and the matching
ConvertibleFrom<&NaturalVector>.TryFrom<IntegerVector> and TryFrom<&IntegerVector> for NaturalVector, failing with
NaturalVectorFromIntegerVectorError when an element is negative, and for UnsignedVector<T>,
failing with UnsignedVectorFromIntegerVectorError when an element is negative or too large for
T, each with the matching ConvertibleFrom<&IntegerVector>.PartialEq in both directions between UnsignedVector<T> and NaturalVector, between
UnsignedVector<T> and IntegerVector, and between NaturalVector and IntegerVector.ModPowerOf2 (by value and by reference) and ModPowerOf2Assign for NaturalVector, reducing
every element modulo $2^k$. Unlike for NaturalPolynomial, elements that reduce to zero are
kept, so the dimension is unchanged.ModPowerOf2IsReduced for NaturalVector, checking whether every element is less than $2^k$.ModPowerOf2Neg (by value and by reference) and ModPowerOf2NegAssign for NaturalVector,
negating every element modulo $2^k$.ModAdd and ModAddAssign for NaturalVector with a Natural modulus, in every combination
of value and reference, adding two vectors of the same dimension modulo $m$.ModSub and ModSubAssign for NaturalVector with a Natural modulus, in every combination
of value and reference, subtracting two vectors of the same dimension modulo $m$.ModNeg and ModNegAssign for NaturalVector with a Natural modulus, in every combination of
value and reference, negating every element modulo $m$.ModPowerOf2Add and ModPowerOf2AddAssign for NaturalVector, in every combination of value
and reference, adding two vectors of the same dimension modulo $2^k$.ModPowerOf2Sub and ModPowerOf2SubAssign for NaturalVector, in every combination of value
and reference, subtracting two vectors of the same dimension modulo $2^k$.Rem, RemAssign, Mod, and ModAssign for NaturalVector with a Natural modulus, in
every combination of value and reference, reducing every element modulo $m$ and keeping the
dimension; and ModIsReduced<Natural> for NaturalVector, checking whether every element is less
than $m$.Rem and Mod for NaturalVector with a primitive unsigned modulus of type T, by value and by
reference, returning the remainders as an UnsignedVector<T>.Mod for IntegerVector with a Natural modulus, in every combination of value and reference,
reducing every element into $[0, m)$ and returning a NaturalVector, like FLINT's
_fmpz_vec_scalar_mod_fmpz; and with a primitive unsigned modulus of type T, returning an
UnsignedVector<T>, like _fmpz_vec_get_nmod_vec.BalancedMod for NaturalVector with a Natural modulus, in every combination of value and
reference, reducing every element into $(-m/2, m/2]$ and returning an IntegerVector, like
_fmpz_vec_set_nmod_vec.BalancedMod and BalancedModAssign for IntegerVector with an Integer modulus, in every
combination of value and reference, reducing every element into $(-|m|/2, |m|/2]$, like FLINT's
_fmpz_vec_scalar_smod_fmpz.ModPowerOf2 for IntegerVector, by value and by reference, reducing every element into
$[0, 2^k)$ and returning a NaturalVector, like FLINT's _fmpz_vec_scalar_fdiv_r_2exp; and
RemPowerOf2 and RemPowerOf2Assign, which keep each element's sign.Rem and RemAssign for IntegerVector with an Integer modulus, in every combination of value
and reference, taking each element's truncating remainder.NaturalVector::multi_crt and IntegerVector::multi_balanced_crt, which combine one vector of
residues per word-sized modulus into the vector of canonical or balanced representatives by the
Chinese remainder theorem, doing the work that depends only on the moduli once. Like
Natural::multi_crt, they return None for unusable moduli and require reduced residues. This
is FLINT's _fmpz_vec_multi_CRT_ui.Content, PrimitivePart, PrimitivePartAssign, ContentAndPrimitivePart, and their canonical
counterparts for NaturalVector and IntegerVector; the canonical ones for NaturalPolynomial,
IntegerPolynomial, and GaussianInteger; and PrimitivePartAssign for GaussianInteger.Neg (by value and by reference) and NegAssign for IntegerVector.Add and AddAssign for NaturalVector and IntegerVector, in every combination of value and
reference. The vectors must have the same dimension.Sub and SubAssign for IntegerVector, in every combination of value and reference. The
vectors must have the same dimension.BalancedModPowerOf2 for Natural (returning an Integer), NaturalPolynomial (returning an
IntegerPolynomial), and NaturalVector (returning an IntegerVector); and BalancedModPowerOf2
and BalancedModPowerOf2Assign for Integer, IntegerPolynomial, and IntegerVector. Each is
balanced_mod with modulus $2^k$, computed by masking rather than dividing.EntrywiseAbs (by value and by reference) and EntrywiseAbsAssign for IntegerVector, like
FLINT's _fmpz_vec_scalar_abs, and EntrywiseUnsignedAbs, which returns a NaturalVector.EntrywiseMax and EntrywiseMaxAssign for NaturalVector and IntegerVector, in every
combination of value and reference, like FLINT's _fmpz_vec_max and _fmpz_vec_max_inplace;
and EntrywiseMin and EntrywiseMinAssign, like _fmpz_vec_min and _fmpz_vec_min_inplace.Mul and MulAssign of NaturalVector by Natural and of IntegerVector by Integer, in
every combination of value and reference, with the scalar on either side, like FLINT's
_fmpz_vec_scalar_mul_fmpz.AddMul (by value and by reference) and AddMulAssign for NaturalVector and IntegerVector,
adding a Natural or Integer multiple of one vector to another, in every combination of value
and reference, like FLINT's _fmpz_vec_scalar_addmul_fmpz; and SubMul and SubMulAssign for
IntegerVector, like _fmpz_vec_scalar_submul_fmpz. RationalVector has both AddMul and
SubMul, with a Rational scalar.ModPowerOf2Mul and ModPowerOf2MulAssign of NaturalVector by Natural, in every
combination of value and reference, multiplying every element modulo $2^k$. The elements and the
scalar must already be reduced.ModPowerOf2AddMul, ModPowerOf2AddMulAssign, ModPowerOf2SubMul, and
ModPowerOf2SubMulAssign for NaturalVector, adding or subtracting a Natural multiple of one
vector to or from another modulo $2^k$, with the arguments in every combination of value and
reference (with a borrowed receiver, all of them by reference). The elements and the scalar must
already be reduced.ModPowerOf2AddMulShl, ModPowerOf2AddMulShlAssign, ModPowerOf2SubMulShl, and
ModPowerOf2SubMulShlAssign for NaturalVector, adding or subtracting a Natural multiple of
one vector, shifted left, to or from another modulo $2^k$, with the arguments in every
combination of value and reference (with a borrowed receiver, all of them by reference). The
elements and the scalar must already be reduced.ModPowerOf2Product and ModProduct for UnsignedPolynomial<T> and NaturalPolynomial, for
iterators of polynomials or of references: the product modulo $2^k$ or modulo $m$. The product of
none is the constant 1, reduced (the zero polynomial when the modulus is 1). Since nonzero
polynomials can multiply to zero modulo a power of 2 or a composite number, it returns as soon as
the partial product is zero, without examining the remaining polynomials. The coefficients must
already be reduced.ModPowerOf2Sum and ModSum for UnsignedPolynomial<T> and NaturalPolynomial, for iterators
of polynomials or of references: the sum modulo $2^k$ or modulo $m$, coefficient by coefficient.
The summands may have different degrees, and the sum of none is zero. The coefficients must
already be reduced.Sum for NaturalVector, IntegerVector, and RationalVector, for iterators of vectors or of
references: the entrywise sum of vectors of the same dimension. Unlike Sum for numbers, an
empty iterator panics, since the dimension of its sum is unknown.ModSum for NaturalVector, for iterators of vectors or of references and a Natural modulus
by value or by reference: the entrywise sum modulo $m$ of vectors of the same dimension,
reducing each entry once at the end. An empty iterator panics.ModPowerOf2Sum for NaturalVector, for iterators of vectors or of references: the entrywise
sum modulo $2^k$ of vectors of the same dimension, reducing each entry once at the end. An empty
iterator panics.ModAddMulShl, ModAddMulShlAssign, ModSubMulShl, and ModSubMulShlAssign for
NaturalVector, adding or subtracting a Natural multiple of one vector, shifted left, to or
from another modulo a Natural, with the arguments in every combination of value and reference
(with a borrowed receiver, all of them by reference). The elements and the scalar must already be
reduced.ModAddMul, ModAddMulAssign, ModSubMul, and ModSubMulAssign for NaturalVector, adding
or subtracting a Natural multiple of one vector to or from another modulo a Natural, like
FLINT's _fmpz_mod_vec_scalar_addmul_fmpz_mod, with the arguments in every combination of value
and reference (with a borrowed receiver, all of them by reference). The elements and the scalar
must already be reduced.ModMul and ModMulAssign of NaturalVector by Natural modulo Natural, in every
combination of value and reference, with the multiplication data for the modulus computed once,
like FLINT's _fmpz_mod_vec_scalar_mul_fmpz_mod. The elements and the scalar must already be
reduced.ModPowerOf2Shl (by value and by reference) and ModPowerOf2ShlAssign for NaturalVector, by
any primitive unsigned type, shifting every element left modulo $2^k$. The elements must already
be reduced.ModShl and ModShlAssign for NaturalVector, by any primitive unsigned type, modulo a
Natural, in every combination of value and reference, computing $2^k \bmod m$ once and
multiplying every element by it. The elements must already be reduced.Shl (by value and by reference) and ShlAssign for NaturalVector and IntegerVector, by any
primitive unsigned or signed type, shifting every element left, like FLINT's
_fmpz_vec_scalar_mul_2exp; a negative amount shifts right, taking the floor.Shr (by value and by reference) and ShrAssign for NaturalVector and IntegerVector, by any
primitive unsigned or signed type, taking the floor of every element, like FLINT's
_fmpz_vec_scalar_fdiv_q_2exp.EntrywiseShrRound (by value and by reference) and EntrywiseShrRoundAssign for NaturalVector
and IntegerVector, by any primitive unsigned or signed type, and EntrywiseShlRound and
EntrywiseShlRoundAssign by any primitive signed type, rounding every element according to a
RoundingMode; with Down, entrywise_shr_round is FLINT's _fmpz_vec_scalar_tdiv_q_2exp.DivExact and DivExactAssign of NaturalVector by Natural and of IntegerVector by
Integer, in every combination of value and reference, dividing every element by a scalar that
divides it exactly, like FLINT's _fmpz_vec_scalar_divexact_fmpz.Div and DivAssign of NaturalVector by Natural and of IntegerVector by Integer, in
every combination of value and reference, rounding every quotient as the scalar / does (down for
Natural, toward zero for Integer), like FLINT's _fmpz_vec_scalar_tdiv_q_fmpz.ModPowerOf2Sqrt for Natural, by value and by reference: the least square root modulo $2^k$,
or None for a non-square, by 2-adic Newton iteration on the odd part, following Azurite's
AzZModPow2.sqrt?; powers up to the limb width use the primitive implementation.ModPowerOf2AddMul, ModPowerOf2AddMulAssign, ModPowerOf2SubMul, and
ModPowerOf2SubMulAssign for Natural, taking the arguments in every combination of value and
reference (with a borrowed receiver, all of them by reference); powers up to the limb width use
the primitive implementation.AddMulShl, AddMulShlAssign, SubMulShl, and SubMulShlAssign for Integer, taking the
arguments in every combination of value and reference (with a borrowed receiver, all of them by
reference).AddMulShl and AddMulShlAssign for Natural, taking the arguments in every combination of
value and reference (with a borrowed receiver, all of them by reference).AddMulShl, AddMulShlAssign, SubMulShl, and SubMulShlAssign for Rational, taking the
arguments in every combination of value and reference (with a borrowed receiver, all of them by
reference).AddMulShl, AddMulShlAssign, SubMulShl, and SubMulShlAssign for IntegerVector, adding
or subtracting an Integer multiple of one vector, shifted left, to or from another, like FLINT's
_fmpz_vec_scalar_addmul_si_2exp and _fmpz_vec_scalar_submul_si_2exp, with the arguments in
every combination of value and reference (with a borrowed receiver, all of them by reference).AddMulShl and AddMulShlAssign for NaturalVector, adding a Natural multiple of one vector,
shifted left, to another, with the arguments in every combination of value and reference (with a
borrowed receiver, all of them by reference).AddMulShl, AddMulShlAssign, SubMulShl, and SubMulShlAssign for RationalVector, adding
or subtracting a Rational multiple of one vector, shifted left, to or from another, with the
arguments in every combination of value and reference (with a borrowed receiver, all of them by
reference).ModPowerOf2AddMulShl, ModPowerOf2AddMulShlAssign, ModPowerOf2SubMulShl, and
ModPowerOf2SubMulShlAssign for Natural, taking the arguments in every combination of value
and reference (with a borrowed receiver, all of them by reference). Only the low $k - b$ bits of
the product are computed, and powers up to the limb width use the primitive implementation.ModPowerOf2Product for Natural, for iterators of values or of references; powers up to the
limb width use the primitive implementation, and larger ones reduce after every multiplication
with the low-half mod_power_of_2_mul, returning as soon as the partial product is zero.ModProduct for Natural, for iterators of values or of references and a modulus by value or by
reference; moduli that fit in a limb use the primitive implementation, and larger ones reduce
after every multiplication, reusing the data for multiplying modulo $m$ and returning as soon as
the partial product is zero.ModSum for Natural, for iterators of values or of references and a modulus by value or by
reference; moduli that fit in a limb use the primitive implementation, and larger ones reduce the
exact sum once at the end.ModPowerOf2Sum for Natural, for iterators of values or of references; powers up to the limb
width use the primitive implementation, and larger ones reduce the exact sum once at the end.ModAddMulShl, ModAddMulShlAssign, ModSubMulShl, and ModSubMulShlAssign for Natural,
taking the arguments in every combination of value and reference (with a borrowed receiver, all of
them by reference); moduli that fit in a limb use the primitive implementation.ModAddMul, ModAddMulAssign, ModSubMul, and ModSubMulAssign for Natural, taking the
arguments in every combination of value and reference (with a borrowed receiver, all of them by
reference); moduli that fit in a limb use the primitive implementation.EntrywiseDivRound and EntrywiseDivRoundAssign of NaturalVector by Natural and of
IntegerVector by Integer, in every combination of value and reference, rounding every quotient
according to a RoundingMode; with Floor, this is FLINT's _fmpz_vec_scalar_fdiv_q_fmpz.RationalVector, with the same API as NaturalVector. Its elements are held entrywise, each a
Rational in lowest terms, as in FLINT's fmpq_vec, rather than over a common denominator.
to_numerators_and_denominator gives the common-denominator form, with the least common
multiple of the denominators, and from_numerators_and_denominator converts back.IntoIterator (by value, by reference, and by mutable reference), FromIterator, and Extend
for RationalVector, so that a vector can be iterated over with for, collected from an
iterator, and extended by one.SelectCoordinates (by value and by reference) and SelectCoordinatesAssign for
RationalVector.Height and HeightRef for RationalVector: the largest height of an element, like FLINT's
_fmpq_vec_max_height. The height of the 0-dimensional vector is 0.ElementProduct for RationalVector: the product of the elements, as a Rational, multiplied
in a balanced tree and stopping at a zero element. The product of the 0-dimensional vector is 1.DotSign for RationalVector: two-dimensional vectors through Rational::cmp_products_neg;
otherwise the terms are split by sign, and an empty side, one term on each side, or sizes far
enough apart decide without any product; only then are the vectors written as integer numerators
over common denominators, whose dot product's sign IntegerVector::dot_sign finds.Dot for RationalVector, like FLINT's _fmpq_vec_dot: each vector is written as integer
numerators over a common denominator, so that one integer dot product and one reduction replace a
reduction per pair.RationalVector::into_numerators_and_denominator, the consuming form of
to_numerators_and_denominator, which scales each numerator in place.ElementSum for RationalVector: the sum of the elements, as a Rational. The sum of the
0-dimensional vector is 0.L1Norm for RationalVector: the sum of the absolute values of the elements, as a Rational.SignificantBits for RationalVector: the sum of the numbers of significant bits of the
elements, each counting the bits of its numerator and denominator, as for Rational.SignificantBits for RationalPolynomial: the sum of the numbers of significant bits of the
coefficients, each in lowest terms, so that a polynomial agrees with the RationalVector of its
coefficients.random_rational_vectors_from_iterator and
random_rational_vectors_with_dimension_from_iterator, which take the elements of
RationalVectors from any iterator, for example one with bounded elements. The other
RationalVector generators are built on them.From<UnsignedVector<T>>, From<NaturalVector>, and From<IntegerVector> for
RationalVector.TryFrom<RationalVector> and TryFrom<&RationalVector> for IntegerVector, failing with
IntegerVectorFromRationalVectorError when an element is not an integer; for NaturalVector,
failing with NaturalVectorFromRationalVectorError when an element is negative or not an
integer; and for UnsignedVector<T>, failing with UnsignedVectorFromRationalVectorError when an
element is negative, not an integer, or too large for T. Each comes with the matching
ConvertibleFrom<&RationalVector>.PartialEq in both directions between RationalVector and each of UnsignedVector<T>,
NaturalVector, and IntegerVector.Content, PrimitivePart, ContentAndPrimitivePart, CanonicalPrimitivePart, and
ContentAndCanonicalPrimitivePart for RationalVector, whose content is the GCD of the
numerators over the common denominator and whose primitive part is an IntegerVector; and the
canonical ones for RationalPolynomial and GaussianRational.Neg (by value and by reference) and NegAssign for RationalVector.Add and AddAssign for RationalVector, in every combination of value and reference. The
vectors must have the same dimension.Sub and SubAssign for RationalVector, in every combination of value and reference. The
vectors must have the same dimension.EntrywiseAbs (by value and by reference) and EntrywiseAbsAssign for RationalVector.EntrywiseMax, EntrywiseMaxAssign, EntrywiseMin, and EntrywiseMinAssign for
RationalVector, in every combination of value and reference.Mul and MulAssign of RationalVector by Rational, in every combination of value and
reference, with the scalar on either side.Div and DivAssign of RationalVector by Rational, in every combination of value and
reference, dividing every element by the scalar; dividing by zero panics.Shl, ShlAssign, Shr, and ShrAssign for RationalVector, with every unsigned and signed
primitive integer shift amount, taking the vector by value or by reference. Shl multiplies
every element by a power of 2 and Shr divides by one; a negative amount shifts the other way.Polynomials. Four new univariate polynomial types: UnsignedPolynomial (malachite-base), NaturalPolynomial and IntegerPolynomial (malachite-nz), and Ra
UnsignedPolynomial<T> (malachite-base), NaturalPolynomial and IntegerPolynomial (malachite-nz), and RationalPolynomial (malachite-q). They support arithmetic, including fast multiplication and powers, along with modular and mod-2^k variants, derivatives and integrals, evaluation, content and primitive part, and parsing and printing. Coverage follows FLINT's fmpz_poly, fmpq_poly, fmpz_mod_poly, and nmod_poly.Float. sinh, cosh, sinh_cosh, tanh, sech, csch, coth, asinh, acosh, atanh, asech, acsch, and acoth, all correctly rounded, each with a variant that takes Rational input.ToLatex and ToTypst traits write math-mode fragments for the primitive types, collections, and every Malachite number and polynomial type.enable_serde feature.Malachite is now also tested against Azurite, a bignum library written in Lean 4 whose operations are proven correct. An oracle executable reads the output of Malachite's demos, recomputes every line, and reports any disagreement. It covers many functions on naturals, integers, modular arithmetic, rationals, and floats, alongside the existing FLINT, GMP, MPFR, and num checks. However, overall coverage is still fairly low and will improve in the future. The new verification pages record, function by function, which independent implementations each operation is checked against. New mapping pages cover Azurite and FLINT's polynomial types.
Debug for the Gaussian and polynomial types now matches Display.Rational::to_height, into_height, and height_significant_bits moved to the new Height trait. Import malachite_base::num::arithmetic::traits::Height.canonicalize_unit now returns 1 for every nonzero element of a field (Rational, GaussianRational, Float, f32, f64).See CHANGELOG.md for the full list.
Debug for GaussianInteger, GaussianRational, UnsignedPolynomial<T>, NaturalPolynomial,
IntegerPolynomial, and RationalPolynomial is now the same as Display, as it already was for
Natural, Integer, and Rational, so that a Vec of them is written as, for example,
[x^2-3*x+2, 0, -5] rather than as a list of structs. They used to derive Debug, which wrote
out the fields, as in GaussianInteger { real: 2, imaginary: -3 }. Float is unchanged.Rational::to_height, Rational::into_height, and Rational::height_significant_bits are no
longer inherent methods; they are now the methods of the new Height trait, which several other
types also implement. Code that calls them needs
use malachite_base::num::arithmetic::traits::Height;, and nothing else changes — the
signatures and the results are the same.canonicalize_unit and canonicalize_unit_assign now return 1 for every unit of a field: a
nonzero Rational or GaussianRational, and a finite nonzero Float, f32, or f64 (a Float
keeping its precision). They used to return the absolute value, or, for a GaussianRational,
the associate rotated by a power of $i$. CanonicalizeUnit now means the canonical associate
under the units of the type's ring, and in a field every nonzero element is a unit. Values that
are not units are unchanged in behavior: zero stays zero, the infinities become $\infty$, and NaN
stays NaN. CanonicalUnitIPow is unchanged.A new ToLatex trait, for converting a value to a LaTeX math-mode fragment, along with the
LatexWrapper struct that its to_latex method returns. The output is a fragment rather than a
complete expression, carrying no $, \(, \[, or environment of its own and leaving those
to the caller, so that one fragment can be embedded in another. fmt_latex, the method
implementors define, takes a Formatter rather than returning a String, so that a value
built out of smaller values writes its parts into a single buffer instead of allocating once per
level of nesting. So far it is implemented for the primitive integers, where the fragment is
identical to the Display output, and for the primitive floats, where the infinities become
\infty and -\infty, NaN becomes \text{NaN}, the zeros keep their signs as 0.0 and
-0.0, and a finite value starts from its shortest round-tripping NiceFloat representation,
with an exponent rewritten in the form 1.0 \times 10^{-45}. It is also implemented for the
unit type, which becomes (); for bool, which becomes \text{T} or \text{F}; for
Ordering, which becomes the relation symbol it stands for, <, =, or >; and for
RoundingMode, which becomes its name in uppercase, such as \text{FLOOR} — there being no
conventional mathematical symbol for a rounding mode.
ToLatex for char, &str, and String. A fragment depicts the string rather than translating
it, and adds no quotation marks: ordinary characters are gathered into \text{...} groups and
typeset as themselves, with LaTeX's special characters escaped, while a character that LaTeX
spells with a math-mode macro is written as that macro outside any group, so that "100% α"
becomes \text{100\% }\alpha. Runs of spaces are preserved rather than collapsed, text-mode
ligatures are broken so that "--flag" does not acquire an en dash, and control words are braced
so that "\n" cannot become the undefined \textbackslashn. A run of superscript or subscript
characters becomes a single script, so that "2¹⁰" is two raised to the tenth rather than two
raised to the first and then to the zeroth, and "H₂O" becomes \text{H}_2\text{O}; a run of one
kind does not run into the next, since the two would stack rather than sit side by side. The three
superscript digits that Unicode puts in Latin-1 Supplement (¹²³) are respelled in math mode to
match the other seven, which pylatexenc spells in text mode, so that a run of them is unbroken. A
character with no LaTeX spelling is written literally, which needs an engine and a font that can
render it. The 1553-entry character table is adapted from
pylatexenc (MIT, © 2015-2023 Philippe Faist), which in
turn adapted it from latexcodec (MIT, © 2011-2014 Matthias C. M. Troffaes); both notices are
reproduced in the generated table.
A new ToTypst trait, for converting a value to a Typst math-mode fragment, along with the
TypstWrapper struct that its to_typst method returns. It mirrors ToLatex, with an
implementation for every type that has one: the primitive integers and floats, (), bool,
Ordering, RoundingMode, char, &str, String, and Option<T> whenever T: ToTypst. Typst
reads Unicode natively and a quoted string typesets its contents as text, so a string needs no
character table at all: it is one string literal, with only \ and " escaped and control
characters spelled rather than written, and "100% α" comes out as itself. A run of superscript
or subscript characters is the exception, and becomes a real script, since a text font often lacks
the Superscripts and Subscripts block. Where LaTeX writes \text{NaN}, \infty, \bot, and
\left[5\right], Typst writes "NaN", infinity, bot, and [5], the last of which Typst
grows to fit its contents without being asked. Every fragment the tests produce is compiled by
Typst itself, so a fragment Typst would reject cannot pass.
ToLatex::to_latex_string and ToTypst::to_typst_string, which give the fragment as a String
in one call rather than as a wrapper to be turned into one. A new use_to_string_variant lint
prefers them, and the rest of the to_*_string family, over the long ways of saying the same
thing: a to_latex or to_typst wrapper immediately turned into a String, and a format!
whose whole format string is a single {:?}, {:b}, {:o}, {:x}, or {:X}. A method's own
definition is left alone, since to_binary_string is written with format!("{self:b}") and
cannot be asked to call itself.
ToLatex and ToTypst for Never and for NiceFloat<T>. A Never cannot be instantiated, so
its implementations can never be called; they exist so that a type parameter bounded by either
trait may be Never, which is what lets Option<Never> have a fragment. A NiceFloat's fragment
is the wrapped float's own, since the float implementations already build their output from the
NiceFloat representation.
ToLatex and ToTypst for slices and for Vec<T>, whenever the element type has them. The
elements' fragments are separated by commas and wrapped in square brackets, as Option's are, so
that a sequence's fragment is built out of its elements' own: vec![1u8, 2, 3] becomes \left[1, 2, 3\right] and [1, 2, 3]. The brackets are not decoration; without them [1, 2] and [[1], [2]] would share a fragment. LaTeX's grow with \left and \right, and Typst's grow on their
own.
ToLatex and ToTypst for HashSet<T> and BTreeSet<T>, whenever the element type has them.
These are as the slice implementations are, but wrapped in braces, as a set is written in
mathematics: BTreeSet::from([3u8, 1, 2]) becomes \left\{1, 2, 3\right\} and {1, 2, 3}. A
HashSet's elements are sorted first, which is why its implementations ask for Ord where a
HashSet does not: a HashSet iterates in an order that depends on its hasher, so without
sorting two equal sets could have different fragments, and the same set could have a different
fragment in the next run. Sorting also makes a HashSet's fragment agree with the BTreeSet of
the same elements.
ToLatex and ToTypst for HashMap<K, V> and BTreeMap<K, V>, whenever the key and value types
have them. Each entry is written as its key, a "maps to" arrow, and its value; the entries are
separated by commas and wrapped in braces, as a map is a set of associations:
BTreeMap::from([(1u8, 10u8), (2, 20)]) becomes \left\{1 \mapsto 10, 2 \mapsto 20\right\} and
{1 |-> 10, 2 |-> 20}. Two-line matrix notation was considered and rejected, since it means a
permutation specifically. As for HashSet, a HashMap's entries are sorted by key first, so its
implementations ask for Ord where a HashMap does not.
ToLatex and ToTypst for tuples of one to eight elements, whenever every element type has them.
The elements' fragments are separated by commas and wrapped in parentheses, so (1u8, 2u8)
becomes \left(1, 2\right) and (1, 2); the elements need not share a type, and a tuple may hold
another. Rust has no way to write one implementation for every arity, so these stop at eight, as
the rest of this crate's tuple machinery does. Since the orphan rule keeps another crate from
implementing either trait for a longer tuple, the new latex_tuple! and typst_tuple! macros
write those fragments instead, as do the latex_tuple and typst_tuple functions they call,
which take their elements as trait objects. That works because fmt_latex and fmt_typst are
object-safe.
ToLatex and ToTypst for FoerSequence<T>, whenever the element type has them. The elements
are bracketed and comma-separated as a sequence's are, and the repeating part, if there is one,
goes under a vinculum: [1, 2, [3, 4]] becomes \left[1, 2, \overline{3, 4}\right] and [1, 2, overline(3 comma 4)]. Inside the Typst vinculum the elements are separated by Typst's comma
symbol rather than by a literal comma, since overline takes a single body and a literal comma
there would be read as an argument separator.
ToLatex and ToTypst for the union types, whenever every variant's type has them. The fragment
is the variant's letter, upright, followed by the wrapped value's own fragment in parentheses, so
Union2::A(2) becomes \text{A}\left(2\right) and "A"(2); the letter is what keeps two
variants holding equal values apart. The implementations are written by union_struct!, so a
Union3 or longer union defined outside this crate gets them too. They use fully qualified paths,
so the macro asks its callers for no new imports.
ToLatex and ToTypst for &T whenever T has them, so a reference is invisible: it writes
what its referent would, which is what lets a collection of references be written at all. &str
and slices keep implementations of their own rather than reaching the blanket one, since their
referents are unsized; they write the same fragments either way.
ToLatex and ToTypst for arrays [T; N], which write what the slice of them would. Before this
an array had no implementation at all: the to_latex and to_typst methods require Self: Sized, so an array could not reach the slice implementation by coercion.
ToLatex and ToTypst for Factors, writing a prime factorization as a product of prime powers:
the factorization of 90 becomes 2 \times 3^2 \times 5 and 2 times 3^2 times 5. An exponent of
1 is left off, as it is when a factorization is written by hand, and the factorization of 1, which
has no prime factors, becomes 1: the empty product, which is what it multiplies out to.
ToLatex and ToTypst for Natural, Integer, GaussianInteger, and the
ComparableGaussianInteger and ComparableGaussianIntegerRef wrappers. Each fragment is what
Display gives, which is already what math mode wants: decimal digits for a Natural, those with
a leading minus for an Integer, and for a GaussianInteger the usual 2-3i, with coefficients
of 1 and -1 elided and a purely real or imaginary value written as one term. The imaginary unit is
a plain i, set in italics as most mathematical writing sets it. The wrappers write what the
value they wrap does, since they exist to give an ordering.
ToLatex and ToTypst for Rational, GaussianRational, and the ComparableGaussianRational
and ComparableGaussianRationalRef wrappers. A value whose denominator is 1 is written as its
numerator alone, and otherwise as a fraction: \frac{22}{7} and frac(22, 7). A sign is written
outside the fraction, as -\frac{2}{3} rather than \frac{-2}{3}, since it belongs to the value
and not to its numerator. An imaginary term puts the imaginary unit in the numerator, so 5/6 times
i is \frac{5i}{6} rather than a fraction with an i hung off it, matching how Display writes
5i/6; coefficients of 1 are elided, giving \frac{i}{2}.
ToLatex and ToTypst for Float and the ComparableFloat and ComparableFloatRef wrappers,
written as the primitive floats are. A NaN becomes \text{NaN} and the infinities become \infty
and -\infty; a finite Float is written as Display writes it, with the exponent, if there is
one, lifted into a real power of ten, so 1.3e30 becomes 1.3 \times 10^{30}. As with Display,
the digit count follows the Float's precision rather than its value, and the two zeros are kept
apart.
A new vars module, holding schemes for naming variables. A polynomial's variables are numbered
rather than named, so something has to turn those numbers into names and names back into numbers;
the new VarScheme trait is that something, and it lets one polynomial be shown as $x_0 + x_1$,
or as $x + y$, or with whatever names a caller has in mind, while the polynomial itself knows
nothing about any of them. A scheme names a variable in three languages — as plain text, as
LaTeX, and as Typst — of which only the plain name is read back, by parse_var. VarScheme::var
gives a Var handle, a scheme together with an index, which implements Display, ToLatex, and
ToTypst, so that a variable can be written wherever any of those is expected; Var::new does
the same for a scheme behind a dyn, which the trait supports, so a scheme may be chosen at run
time. The trait's contract is that a name is never empty, holds no reserved character, belongs to
one variable alone, and reads back as that variable; the new char_is_reserved says which
characters are reserved, namely the digits, +, -, *, /, ^, (, ), ,, and
whitespace. Keeping those out of the names is what lets a polynomial be written without
separators and still be read back, since a name is then exactly a longest run of unreserved
characters. The design follows the Var and ParsableVar classes of Azurite, a separate project
of the author's, where the same four conditions are theorems rather than a contract; the n that
bounds a variable type there becomes the scheme's capacity, which a scheme with no bound
reports as None.
Nine naming schemes, one per module under vars: IndexedVars and IndexedCapsVars, which name
variables x₀, x₁, x₂, … and X₀, X₁, X₂, …, writing the index as a run of Unicode subscript
digits and, in LaTeX and Typst, as a real subscript, braced or parenthesized only when it is more
than one digit long; AbcVars and AbcCapsVars, the 26 letters in their usual order; XyzVars
and XyzCapsVars, the same 26 letters ordered as a mathematician reaches for them, x, y, z, w, v, …, a; GreekVars and GreekCapsVars, the 24 Greek letters, skipping the final sigma, which
is a second form of a letter already named, and the one code point Unicode leaves unassigned
among the capitals; and ListVars, which takes its names from the caller and checks them once,
when it is made, so that the scheme itself cannot fail. Only IndexedVars and IndexedCapsVars
have no capacity, since an index is written out rather than looked up. In LaTeX a Greek letter is
written with its macro where it has one and as the Latin letter it looks like where it does not,
since LaTeX has no \omicron or \Alpha; the spelling is read off the same character table that
ToLatex for char consults, rather than written out a second time. In Typst a Greek letter is
written as itself, which Typst reads natively. A name that is a single ASCII letter is written
bare in both languages, so that both set it in math italics as a variable should be, and a longer
name is set upright; that is what the trait's two markup methods do by default, which is why
ListVars needs only three methods and a scheme written outside this crate needs only the same
three.
chars::scripts, with fmt_subscript_digits and parse_subscript_digits, which write and read a
number as a run of Unicode subscript digits. The two are inverse: parsing accepts exactly what
writing produces and nothing else, rejecting the empty string, ASCII digits, a leading zero, and a
number too large for a u64, so that a number has one spelling rather than several. IndexedVars
is built on them.
ToLatex for Option<T> whenever T: ToLatex. None becomes \bot, and Some wraps its
value in square brackets written with \left and \right, so that they grow to fit a value
taller than one line: Some(5) becomes \left[5\right]. The brackets are not decoration:
without them Some(None) and None would share a fragment, and distinct values would be
indistinguishable. Braces would have served as well, but this crate's documentation already
spells the Iverson bracket with them.
Exhaustive generators of ordered [Vec]s, the fourth quadrant alongside all Vecs, unique
Vecs, and ordered unique Vecs: the elements of each Vec appear in the order of the source
iterator but may repeat, so the Vecs are the multisets of the elements, each written in source
order. exhaustive_ordered_vecs_fixed_length generates those of one length by pairing each
ordered unique Vec with the compositions that assign its elements multiplicities, which is how
exhaustive_unique_vecs is built from ordered unique Vecs and permutations, and
exhaustive_ordered_vecs_from_length_iterator runs that for each length an iterator produces, the
way exhaustive_vecs_from_length_iterator does; exhaustive_ordered_vecs, with _min_length,
_length_range, and _length_inclusive_range variants, are built on it, so that the lengths of
their output grow logarithmically, as the all-Vecs family's do. (Interleaving subsets rather
than lengths, whatever the index sequence, gives one subset a constant share of the output and
makes lengths grow linearly instead.) shortlex_ordered_vecs and its _min_length,
_length_range, and _length_inclusive_range variants generate them in order of increasing
length and lexicographically within each length; and lex_ordered_vecs_fixed_length,
_length_range, and _length_inclusive_range generate them lexicographically. There is no
unbounded lexicographic variant, since with repetition allowed it would produce [x], [x, x],
[x, x, x], and so on forever without reaching a second element — the same reason the all-Vecs
family has shortlex_vecs but no lex_vecs. The count for a fixed length $k$ from $n$ elements
is $\binom{n+k-1}{k}$, and over a nonempty source the unbounded generators are infinite.
Random generators of ordered [Vec]s, matching the new exhaustive ones: random_ordered_vecs,
with _fixed_length, _from_length_iterator, _min_length, _length_range, and
_length_inclusive_range variants. As for random ordered unique [Vec]s, "ordered" here means
sorted by [Ord] rather than by a source iterator's order, so each generator draws a random
[Vec] and sorts it. Unlike the unique versions, these place no demand on the element iterator:
since elements may repeat, the requested length is always reachable, and no iteration can hang
waiting for distinct values.
Exhaustive generators of [HashMap]s and [BTreeMap]s, in a new maps module. Each map is a set
of keys paired with an assignment of values to them, so they are generated by pairing the ordered
unique key [Vec]s with the length-matched value [Vec]s. Besides the plain generators there are
_fixed_size, _min_size, _size_range, and _size_inclusive_range variants restricting the
number of keys; _fixed_unique_value_count, _unique_value_count_range, and
_unique_value_count_inclusive_range variants restricting the number of distinct values; and
_size_and_unique_value_count_inclusive_range, which restricts both. A map with $k$ entries has
between 1 and $k$ distinct values, or 0 if $k$ is 0, so the two restrictions are intersected with
that range rather than applied independently.
Random generators of [HashMap]s and [BTreeMap]s, matching the new exhaustive ones:
random_hash_maps and random_b_tree_maps, with _fixed_size, _from_size_iterator,
_min_size, _size_range, and _size_inclusive_range variants, plus
_fixed_unique_value_count, _unique_value_count_range, _unique_value_count_inclusive_range,
and _size_and_unique_value_count_inclusive_range, which restrict the number of distinct values
as the exhaustive generators do. Sizes come from a geometric distribution, as lengths do
elsewhere, except where a size range is given and they are uniform. A map with $k$ entries has
between 1 and $k$ distinct values, or 0 if $k$ is 0, so the size is drawn first and the
distinct-value count is then drawn uniformly from those the size admits; when both are restricted,
the sizes are drawn only from those that admit an allowed count. Maps with the same size and
distinct-value count are not equally likely — those whose values are spread evenly over the keys
are favored — but every such map is reachable. Each entry consumes exactly one draw from the value
iterator, and a repeated key costs a key draw but no value draw; pairing keys with values by the
map's own iteration order instead would make a [HashMap]'s contents depend on the hasher, and so
differ between runs. As for random sets, the key iterator must be able to produce as many distinct
keys as the largest size requested — and, for the unique-value-count generators, the value
iterator as many distinct values as the largest count requested — or the generator will hang.
exhaustive_vecs_fixed_length_with_distinct_count_inclusive_range, generating the [Vec]s of a
fixed length whose number of distinct elements lies in a range. Filtering unrestricted [Vec]s
would not do: asking for one distinct element among length-$k$ [Vec]s over $n$ elements passes
roughly one in $n^{k-1}$. Instead each [Vec] is built from a restricted growth string, which
says which positions share an element, and a [Vec] of distinct elements, which says what the
string's symbols stand for in order of first appearance; every such [Vec] arises from exactly
one such pair.
restricted_growth_strings, generating the [Vec]s $(a_0, \ldots, a_{k-1})$ with $a_0 = 0$ and
$a_i \leq 1 + \max(a_0, \ldots, a_{i-1})$ that use a given number of distinct symbols. These
correspond to the partitions of $k$ labeled objects into a given number of nonempty blocks, so the
output length is a Stirling number of the second kind.
exhaustive_vecs_with_last and its _min_length, _length_range, and
_length_inclusive_range variants, along with exhaustive_vecs_with_last_fixed_length and
exhaustive_vecs_with_last_from_length_iterator: a family that builds each [Vec] from two
iterators, one supplying every element but the last and the other supplying the last. It exists
for the sequences whose final element is special — the coefficients of a polynomial, whose
leading coefficient may not be zero, are the motivating case. Generating all [Vec]s and
filtering is far too slow, since the fraction that survives shrinks with the length; pairing a
[Vec] of the earlier elements with a last element is unbalanced, since the pair generator
cannot see that one half is a [Vec] and grows it far more slowly than the other. These
generators instead reuse the length-two tuple machinery that exhaustive_vecs_fixed_length
already uses, with an output-type map that sends every slot but the last to the first iterator
and the last slot to the second, so that a last element is exactly as expensive as any other and
the bit-distribution logic is shared rather than reimplemented. The lengths are stepped by a
bit_distributor_sequence rather than a ruler_sequence: with the ruler sequence half of the
output has length one, which for polynomials means half of them are constants.
random_vecs_with_last and its _min_length, _length_range, and _length_inclusive_range
variants, along with random_vecs_with_last_fixed_length and
random_vecs_with_last_from_length_iterator, the random counterparts of the above. The lengths
come from a geometric distribution, as they do for random_vecs, except where a length range is
given and they are uniform.
A new UnsignedPolynomial<T> type, a univariate polynomial whose coefficients are unsigned
primitive integers, held as a
[Vec] in ascending order of degree with no trailing zero — so the zero polynomial has no
coefficients at all, and Eq, Hash, and Debug can be derived. It is the small-coefficient
member of the polynomial family, meant for polynomials modulo a small modulus, and it mirrors
NaturalPolynomial in malachite-nz. from_coefficients_asc normalizes a [Vec] by trimming
trailing zeros; coefficients_asc lends the coefficients back and into_coefficients_asc
hands them over; degree returns an Option<u64>, None for the zero polynomial, since zero
has no degree rather than a degree of zero; coefficient reads a coefficient at any index,
giving zero past the degree however far past, and leading_coefficient reads the last one,
giving zero for the zero polynomial. Unlike its bignum counterparts, which lend a reference,
both return a [u64] by value. mutate_coefficient allows a coefficient to be changed in
place, growing the polynomial with zeros if the index is past the degree and trimming it
afterwards, the way Rational::mutate_numerator does. Zero is implemented, with a const
ZERO, and one and two are provided as functions rather than constants, since a nonzero
constant polynomial owns a heap allocation. From is implemented for everything a [u64] can
be converted from.
Display and FromStr for UnsignedPolynomial, along with to_string_with and from_string_with,
which name the variable with any VarScheme rather than the default x. The format is the one
Azurite uses: terms in decreasing degree joined with +, an exponent of one elided, a
coefficient of one elided, and * between a coefficient and its variable, so that x^2+3*x+2
reads back as itself. The zero polynomial is 0. FromStr accepts the terms in any order and
tolerates a leading zero or an explicit ^1, but rejects anything Display would never write,
such as a zero coefficient in a term, two terms of the same degree, or a space.
ToLatex and ToTypst for UnsignedPolynomial, with to_latex_string_with and
to_typst_string_with for a named variable. Neither language writes the *, and LaTeX braces
an exponent of more than one digit while Typst parenthesizes it.
A new Polynomial trait, in malachite_base::polynomial, holding what every polynomial type has
in common: one, two, x, from_coefficients_asc, into_coefficients_asc, degree, len,
coefficient, leading_coefficient, mutate_coefficient, zero_coefficients, reverse,
reverse_assign, truncate, truncate_assign, to_string_with, to_latex_string_with,
to_typst_string_with, and from_string_with. len is the number of coefficients a polynomial
holds, like FLINT's fmpz_poly_length: one more than the degree, and 0 for the zero polynomial.
zero_coefficients(start, end) sets the coefficients of $x^i$ for $i$ in start..end to zero,
like fmpz_poly_zero_coeffs, lowering the degree when the range reaches the leading coefficient;
a RationalPolynomial is reduced to lowest terms again afterwards. reverse(len) and
reverse_assign(len) truncate or zero-pad a polynomial to len coefficients and reverse them,
like fmpz_poly_reverse, so that the result is $x^{len-1} (p \bmod x^{len})(1/x)$.
truncate(len) and truncate_assign(len) keep the first len coefficients, giving $p \bmod
x^{len}$, like fmpz_poly_set_trunc and fmpz_poly_truncate respectively; truncate returns a
new polynomial rather than shortening in place as Vec::truncate does. The trait is implemented
for UnsignedPolynomial, NaturalPolynomial, IntegerPolynomial, and RationalPolynomial, and
those functions are its methods rather than inherent ones, so code that calls them needs use malachite_base::polynomial::Polynomial;. A coefficient is returned as a CoefficientOutput,
which is a reference where a polynomial holds its coefficients as bignums and a value where a
coefficient is a primitive or has to be built, as a RationalPolynomial's is.
A new EqTruncated trait, in malachite_base::polynomial, with eq_truncated(&self, other, len), which determines whether two polynomials agree below $x^{len}$, like FLINT's
fmpz_poly_equal_trunc, without building either truncation. It is implemented for each of
UnsignedPolynomial, NaturalPolynomial, IntegerPolynomial, and RationalPolynomial against
itself and, in both orders, against each of the others.
New MulPowerOfX and MulPowerOfXAssign traits, in malachite_base::polynomial, which multiply
a polynomial by $x^n$, moving every coefficient up by $n$ places, like FLINT's
fmpz_poly_shift_left, fmpq_poly_shift_left, fmpz_mod_poly_shift_left, and
nmod_poly_shift_left. They are implemented for all four polynomial types, taking the polynomial
by value or by reference. The name avoids "shift", since << throughout Malachite scales by a
power of 2.
New DivPowerOfX and DivPowerOfXAssign traits, in malachite_base::polynomial, which divide a
polynomial by $x^n$ and discard the remainder, dropping the lowest $n$ coefficients, like FLINT's
fmpz_poly_shift_right, fmpq_poly_shift_right, fmpz_mod_poly_shift_right, and
nmod_poly_shift_right. They are implemented for all four polynomial types, taking the
polynomial by value or by reference. A RationalPolynomial result is reduced to lowest terms,
since the dropped coefficients can be the ones that kept the numerator coprime to the
denominator.
New ComposePowerOfX and ComposePowerOfXAssign traits, in malachite_base::polynomial, which
replace a polynomial $p$ with $p(x^k)$, moving the coefficient of $x^i$ to $x^{ik}$, like FLINT's
fmpz_poly_inflate, fmpz_mod_poly_inflate, and nmod_poly_inflate. They are implemented for
all four polynomial types, taking the polynomial by value or by reference. With $k = 0$ the result
is the constant $p(1)$; for UnsignedPolynomial<T> this panics if the sum of the coefficients
overflows T, and it is never reduced modulo anything.
A new ExponentGcd trait, in malachite_base::polynomial, whose exponent_gcd gives the
greatest common divisor of the exponents at which a polynomial has nonzero coefficients: the
largest $k$ such that $p(x) = q(x^k)$, when $p$ is not constant. It is like FLINT's
fmpz_poly_deflation, fmpz_mod_poly_deflation, and nmod_poly_deflation, except that a
nonzero constant gives 0 rather than 1, so the result is 0 exactly for the constants. It is
implemented for all four polynomial types.
New DeflatePowerOfX and DeflatePowerOfXAssign traits, in malachite_base::polynomial, which
replace a polynomial $p$ with the $q$ such that $q(x^n) = p(x)$, the inverse of
ComposePowerOfX, like FLINT's fmpz_poly_deflate, fmpz_mod_poly_deflate, and
nmod_poly_deflate. Where FLINT silently drops the coefficients at exponents that are not
multiples of $n$, these panic, as they do when $n$ is 0. They are implemented for all four
polynomial types, taking the polynomial by value or by reference.
Shl and ShlAssign for NaturalPolynomial and IntegerPolynomial, with every unsigned
primitive integer shift amount, taking the polynomial by value or by reference. Every coefficient
is shifted, multiplying the polynomial by a power of 2, like FLINT's fmpz_poly_scalar_mul_2exp.
Shl, ShlAssign, Shr, and ShrAssign for RationalPolynomial, with every unsigned and
signed primitive integer shift amount, taking the polynomial by value or by reference. Shl
multiplies by a power of 2 and Shr divides by one, and a negative shift does the opposite.
Factors of 2 are cancelled against the denominator, or against the numerator's coefficients,
before the rest of the shift is applied, so the result stays in lowest terms. RationalPolynomial
is the only polynomial type with Shr.
ModPowerOf2Shl and ModPowerOf2ShlAssign for NaturalPolynomial and UnsignedPolynomial,
with every unsigned primitive integer shift amount, taking the polynomial by value or by
reference. Every coefficient is shifted and reduced modulo $2^k$; the coefficients must already
be reduced.
ModShl and ModShlAssign for NaturalPolynomial, with every unsigned primitive integer shift
amount, taking the polynomial and the Natural modulus by value or by reference, and for
UnsignedPolynomial<T>, with every unsigned primitive integer shift amount and a T modulus.
$2^k \bmod m$ is computed once and every coefficient is multiplied by it; the coefficients must
already be reduced.
New Derivative, DerivativeAssign, ModDerivative, ModDerivativeAssign,
ModPowerOf2Derivative, and ModPowerOf2DerivativeAssign traits, in
malachite_base::polynomial. Derivative is implemented for IntegerPolynomial,
NaturalPolynomial, and RationalPolynomial, like FLINT's fmpz_poly_derivative and
fmpq_poly_derivative; the rational derivative is brought back to lowest terms. ModDerivative
and ModPowerOf2Derivative are implemented for NaturalPolynomial and UnsignedPolynomial, like
FLINT's fmpz_mod_poly_derivative and nmod_poly_derivative; the coefficients must already be
reduced, and the result is trimmed, since the derivative can lose any number of degrees.
New NthDerivative, NthDerivativeAssign, ModNthDerivative, ModNthDerivativeAssign,
ModPowerOf2NthDerivative, and ModPowerOf2NthDerivativeAssign traits, in
malachite_base::polynomial, implemented for the same types as the corresponding derivative
traits. NthDerivative is like FLINT's fmpz_poly_nth_derivative and fmpq_poly_nth_derivative.
FLINT has no modular $n$th derivative; the modular versions multiply each coefficient by its
falling factorial modulo $m$ or $2^k$, and return zero at once when the modulus divides $n!$.
New BitPack and BitUnpack traits, in malachite_base::polynomial, implemented for
IntegerPolynomial and NaturalPolynomial. bit_pack places the coefficient of $x^i$ at bit
$ib$ of an Integer or Natural: the value $p(2^b)$. It is like FLINT's fmpz_poly_bit_pack
when every coefficient fits in its field, except that it returns $p(1)$ rather than 0 for $b = 0$
and lets wider coefficients overlap rather than truncating them. bit_unpack is the inverse,
like FLINT's fmpz_poly_bit_unpack (signed fields, for IntegerPolynomial) and
fmpz_poly_bit_unpack_unsigned (for NaturalPolynomial), except that it panics when $b = 0$.
Multiplication of IntegerPolynomials: Mul and MulAssign, like FLINT's fmpz_poly_mul;
Square and SquareAssign, like fmpz_poly_sqr; and the new MulTruncated,
MulTruncatedAssign, SquareTruncated, and SquareTruncatedAssign traits, in
malachite_base::polynomial, which keep only the coefficients of $x^i$ for $i$ below a given
length, like fmpz_poly_mullow and fmpz_poly_sqrlow. They use schoolbook multiplication,
word-sized arithmetic when the coefficients and the product are small enough (FLINT's tiny
kernels), Karatsuba multiplication for short polynomials with large coefficients, Kronecker
substitution, which packs each polynomial into a single Natural and multiplies those, and, for
long polynomials whose product's coefficients fit, a number-theoretic transform modulo up to eight
word-sized primes (the polynomial counterpart of the small-prime FFT that Natural multiplication
already uses), and Schönhage–Strassen multiplication, a truncated transform over residues modulo
$2^N + 1$ that needs no multiplications, for coefficients of hundreds to thousands of bits,
choosing among them as FLINT does, except that Schönhage–Strassen is used over a wider, measured
range of lengths. When either factor is a constant, the forms that take the other
by value multiply its coefficients in place.
The same multiplication, squaring, and truncated multiplication and squaring for
NaturalPolynomials: Mul, MulAssign, Square, SquareAssign, MulTruncated,
MulTruncatedAssign, SquareTruncated, and SquareTruncatedAssign, taking each operand by
value or by reference. The algorithms and the choice among them are shared with
IntegerPolynomial, through code that is generic over the coefficient type, so with natural
coefficients they take the paths for non-negative coefficients.
Multiplication, squaring, and truncated multiplication and squaring of NaturalPolynomials
modulo $2^k$: ModPowerOf2Mul, ModPowerOf2MulAssign, ModPowerOf2Square, and
ModPowerOf2SquareAssign, and the new ModPowerOf2MulTruncated,
ModPowerOf2MulTruncatedAssign, ModPowerOf2SquareTruncated, and
ModPowerOf2SquareTruncatedAssign traits, in malachite_base::polynomial, like FLINT's
fmpz_mod_poly_mul, fmpz_mod_poly_sqr, and fmpz_mod_poly_mullow with the modulus $2^k$.
Every coefficient of the inputs must already be reduced modulo $2^k$. For short polynomials,
where it measured faster, the coefficient products are computed modulo $2^k$ too, with low-half
multiplication, by schoolbook or Karatsuba multiplication; for $k$ no greater than the word
width this is word arithmetic, through kernels in malachite-base that will also serve
UnsignedPolynomial. With 32- to 64-bit coefficients this is several times faster than the
full product.
Pow and PowAssign for IntegerPolynomial, NaturalPolynomial, and RationalPolynomial, with
a u64 exponent, like FLINT's fmpz_poly_pow and fmpq_poly_pow. The power is computed by the
binomial theorem, J. C. P. Miller's multinomial recurrence, an addition chain, or binary
exponentiation, chosen by criteria measured for Malachite's multiplication, after removing any
factor of $x^k$. New PowTruncated and PowTruncatedAssign traits, in
malachite_base::polynomial, implemented for all three like FLINT's fmpz_poly_pow_trunc and
fmpq_poly_pow_trunc, raise a polynomial to a power modulo $x^n$.
ModPow and ModPowAssign for NaturalPolynomial with a Natural modulus and for
UnsignedPolynomial<T> with a T modulus, like FLINT's fmpz_mod_poly_pow and nmod_poly_pow,
and new ModPowTruncated and ModPowTruncatedAssign traits, in malachite_base::polynomial,
implemented for both types like fmpz_mod_poly_pow_trunc and nmod_poly_pow_trunc. The
coefficients must already be reduced modulo $m$. As with the power-of-2 versions, the power is
computed by binary exponentiation with each step trimmed, or, for NaturalPolynomial, as by Pow
when no coefficient of the power over the integers can reach $m$.
ModPowerOf2Pow and ModPowerOf2PowAssign for NaturalPolynomial and UnsignedPolynomial<T>,
like FLINT's fmpz_mod_poly_pow and nmod_poly_pow with the modulus $2^k$, and new
ModPowerOf2PowTruncated and ModPowerOf2PowTruncatedAssign traits, in
malachite_base::polynomial, implemented for both types like fmpz_mod_poly_pow_trunc and
nmod_poly_pow_trunc. The coefficients must already be reduced modulo $2^k$. The power is
computed by binary exponentiation, trimming after each step since leading coefficients can vanish
modulo $2^k$; for NaturalPolynomial, when no coefficient of the power over the integers can
reach $2^k$, it is computed as by Pow instead.
New ModIntegral and ModIntegralAssign traits, in malachite_base::polynomial, implemented for
UnsignedPolynomial<T> with a T modulus, like FLINT's nmod_poly_integral, and for
NaturalPolynomial with a Natural modulus taken by value or by reference, which FLINT lacks: the
integral modulo m whose constant term is zero. An index needs to be a unit modulo m only where
the coefficient it divides is nonzero, unlike in FLINT, which needs every index up to the degree
plus 1 to be a unit (so FLINT cannot integrate $x^2$ modulo 8, but Malachite gives $3x^3$); all
the divisions share one modular inversion.
New ModPowerOf2Integral and ModPowerOf2IntegralAssign traits, in malachite_base::polynomial,
implemented for UnsignedPolynomial<T> and NaturalPolynomial: the integral modulo $2^k$ whose
constant term is zero, defined when every nonzero coefficient belongs to an even power of $x$.
FLINT has no counterpart, and its nmod_poly_integral cannot integrate anything of degree 1 or
more modulo $2^k$.
New Integral and IntegralAssign traits, in malachite_base::polynomial, implemented for
RationalPolynomial, like FLINT's fmpq_poly_integral: the integral whose constant term is
zero. The result is built in lowest terms coefficient by coefficient, each divisor first
cancelling what it shares with its coefficient, so no GCD of the whole polynomial is needed.
Multiplication, squaring, and truncated multiplication and squaring of RationalPolynomials:
Mul, MulAssign, Square, SquareAssign, MulTruncated, MulTruncatedAssign,
SquareTruncated, and SquareTruncatedAssign, taking each polynomial by value or by reference,
like FLINT's fmpq_poly_mul and fmpq_poly_mullow. The numerators are multiplied as
IntegerPolynomials. A product divides the GCD of each numerator's content and the other
denominator out of both before multiplying, as a TODO in FLINT's _fmpq_poly_mul suggests, so
that the multiplication works on smaller numbers; a square needs no GCD, and a truncated product
is reduced after truncation.
Multiplication, squaring, and truncated multiplication and squaring of UnsignedPolynomial<T>s
modulo a T: ModMul, ModMulAssign, ModSquare, ModSquareAssign, ModMulTruncated,
ModMulTruncatedAssign, ModSquareTruncated, and ModSquareTruncatedAssign, taking each
polynomial by value or by reference, like FLINT's nmod_poly_mul and nmod_poly_mullow. Every
coefficient of the inputs must already be reduced modulo the modulus. These use the word kernels
that NaturalPolynomial uses for word-sized moduli, by schoolbook or Karatsuba multiplication.
Multiplication, squaring, and truncated multiplication and squaring of UnsignedPolynomial<T>s
modulo $2^k$, for $k$ no greater than the width of T: ModPowerOf2Mul, ModPowerOf2MulAssign,
ModPowerOf2Square, ModPowerOf2SquareAssign, ModPowerOf2MulTruncated,
ModPowerOf2MulTruncatedAssign, ModPowerOf2SquareTruncated, and
ModPowerOf2SquareTruncatedAssign, taking each polynomial by value or by reference, like FLINT's
nmod_poly_mul and nmod_poly_mullow with the modulus $2^k$. Every coefficient of the inputs
must already be reduced modulo $2^k$. These use the word kernels above, by schoolbook or
Karatsuba multiplication.
Multiplication, squaring, and truncated multiplication and squaring of NaturalPolynomials
modulo a Natural: ModMul, ModMulAssign, ModSquare, and ModSquareAssign, and the new
ModMulTruncated, ModMulTruncatedAssign, ModSquareTruncated, and ModSquareTruncatedAssign
traits, in malachite_base::polynomial, taking each polynomial and the modulus by value or by
reference, like FLINT's fmpz_mod_poly_mul, fmpz_mod_poly_sqr, and fmpz_mod_poly_mullow.
Every coefficient of the inputs must already be reduced modulo the modulus. When the modulus fits
in a word and the polynomials are short enough, the product is computed by word kernels in
malachite-base that will also serve UnsignedPolynomial: as in FLINT's _nmod_poly_mul, each
coefficient is accumulated exactly in one, two, or three words, depending on how large it can
get, and reduced once, by schoolbook or Karatsuba multiplication. With moduli of 33 to 64 bits
this is two to eight times faster than the full product for short polynomials. Otherwise, as in
FLINT's fmpz_mod_poly functions, the product is computed exactly and its coefficients are then
reduced.
New L2NormSquared and FloorL2Norm traits, in malachite_base::polynomial: the exact sum of
the squares of a polynomial's coefficients, and the floor of its square root, like FLINT's
fmpz_poly_2norm. Both are implemented for &IntegerPolynomial and &NaturalPolynomial, with a
Natural result, and L2NormSquared also for &RationalPolynomial, with an exact Rational
result.
New AddTruncated, AddTruncatedAssign, SubTruncated, and SubTruncatedAssign traits, in
malachite_base::polynomial, which add or subtract two polynomials and keep only the
coefficients below $x^{len}$, like FLINT's fmpz_poly_add_series and fmpz_poly_sub_series.
They are implemented for IntegerPolynomial and RationalPolynomial, like FLINT's
fmpq_poly_add_series and fmpq_poly_sub_series for the latter, and AddTruncated and
AddTruncatedAssign also for NaturalPolynomial, taking each operand by value or by reference;
only the first len coefficients of each operand are read, and the result is trimmed. A
RationalPolynomial result is kept in lowest terms, which after a cut can mean dividing out more
than the GCD of the two denominators.
New ModPowerOf2AddTruncated, ModPowerOf2AddTruncatedAssign, ModPowerOf2SubTruncated, and
ModPowerOf2SubTruncatedAssign traits, in malachite_base::polynomial, which add or subtract two
polynomials modulo $2^k$ and keep only the coefficients below $x^{len}$, taking (other, len, pow), like FLINT's nmod_poly_add_series and nmod_poly_sub_series, and
fmpz_mod_poly_add_series and fmpz_mod_poly_sub_series, with the modulus $2^k$. They are
implemented for UnsignedPolynomial<T> and NaturalPolynomial, taking each operand by value or
by reference. As for every modular operation, both operands must already be reduced, and this is
checked for the whole of each, not only the part that is kept.
New ModAddTruncated, ModAddTruncatedAssign, ModSubTruncated, and ModSubTruncatedAssign
traits, in malachite_base::polynomial, which add or subtract two polynomials modulo $m$ and keep
only the coefficients below $x^{len}$, taking (other, len, m), like FLINT's
nmod_poly_add_series and nmod_poly_sub_series, and fmpz_mod_poly_add_series and
fmpz_mod_poly_sub_series. They are implemented for UnsignedPolynomial<T> modulo a T and
NaturalPolynomial modulo a Natural, taking each polynomial, and a Natural modulus, by value
or by reference. Both operands must already be reduced, and this is checked for the whole of each.
A new Evaluate trait, in malachite_base::polynomial, whose evaluate substitutes a value for
a polynomial's variable; the value's type decides the result's, through an associated Output
type. It is implemented for &IntegerPolynomial at an Integer and for &NaturalPolynomial at a
Natural, with the value taken by value or by reference, like FLINT's fmpz_poly_evaluate_fmpz:
Horner's rule, or divide and conquer, which keeps the operands of each multiplication balanced,
for polynomials that are long compared with the size of the value. Where FLINT switches at 50
coefficients whatever the value, Malachite's crossover, tuned, depends on both: about 1024
coefficients when the value fits in one limb, and otherwise when the length times the value's limb
count reaches 256. &IntegerPolynomial also evaluates at a Rational, like
fmpz_poly_evaluate_fmpq, giving a result in lowest terms; it works with the numerator of the
homogenized polynomial, so that the result needs reducing only when the leading coefficient shares
a factor with the denominator of the value. This makes it several times as fast as a direct
translation of FLINT's algorithms, and its choice between Horner's rule and divide and conquer is
tuned separately. &RationalPolynomial evaluates at a Rational and at an Integer too, like
fmpq_poly_evaluate_fmpq and fmpq_poly_evaluate_fmpz, giving a Rational in lowest terms: its
numerator's value divided by its denominator. It is not part of the Polynomial trait, since
UnsignedPolynomial does not implement it.
A new ModPowerOf2Evaluate trait, in malachite_base::polynomial, whose
mod_power_of_2_evaluate(x, pow) evaluates a polynomial at x modulo $2^{pow}$. It is
implemented for NaturalPolynomial at a Natural, taking the polynomial and the value each by
value or by reference, and panics unless every coefficient and x are already reduced modulo
$2^{pow}$. It uses Horner's rule, reducing after every step; taking the polynomial by value lets
the coefficient that is returned outright, or that starts Horner's rule, be moved rather than
cloned.
It is also implemented for UnsignedPolynomial<T> at a T, for pow up to the width of T,
with the same checks; there Horner's rule runs in wrapping arithmetic and reduces once at the end.
A new ModEvaluate trait, in malachite_base::polynomial, whose mod_evaluate(x, m) evaluates a
polynomial at x modulo m, like FLINT's fmpz_mod_poly_evaluate_fmpz. It is implemented for
NaturalPolynomial at a Natural modulo a Natural, taking each of the three by value or by
reference, and panics unless every coefficient and x are already reduced modulo m. It uses
Horner's rule with the modular multiplication's precomputed data for m computed once.
It is also implemented for UnsignedPolynomial<T> at a T modulo a T, like FLINT's
nmod_poly_evaluate_nmod, with the same checks; for a long enough polynomial and a modulus whose
top bit is clear, it multiplies by x with Shoup's method, lazily reduced when the modulus is at
most a third of T's range.
It is also implemented for &IntegerPolynomial at a u64 modulo a u64, like FLINT's
fmpz_poly_evaluate_mod: the coefficients may be any Integers and are reduced as the evaluation
goes, while x must be reduced.
A new EvaluateMany trait, in malachite_base::polynomial, whose evaluate_many(xs) evaluates a
polynomial at each value in a slice, like FLINT's fmpz_poly_evaluate_fmpz_vec. It is
implemented for &IntegerPolynomial at Integers and Rationals, &NaturalPolynomial at
Naturals, and &RationalPolynomial at Rationals and Integers, every combination for which
Evaluate is implemented.
A new ModEvaluateMany trait, whose mod_evaluate_many(xs, m) evaluates a polynomial at each
value in a slice modulo m, like FLINT's nmod_poly_evaluate_nmod_vec_iter and
fmpz_mod_poly_evaluate_fmpz_vec_iter. It is implemented for &UnsignedPolynomial<T> at Ts
modulo a T, which evaluates a block of points in each pass over the coefficients, and for
&NaturalPolynomial at Naturals modulo a Natural, taken by value or by reference, which
checks the polynomial and precomputes the modular-multiplication data once.
A new ModEvaluateGeometric trait, whose mod_evaluate_geometric(q, k, m) evaluates a
polynomial at $1, q, \ldots, q^{k-1}$ modulo m, like FLINT's
nmod_poly_evaluate_geometric_nmod_vec_iter and nmod_poly_evaluate_geometric_nmod_vec_fast
with $q = r^2$. It is implemented for &UnsignedPolynomial<T>. Long polynomials evaluated at many
points use Bluestein's trick, which turns the evaluation into one middle product (the coefficients
of a product from the middle on, like FLINT's _nmod_poly_mulmid, computed by a Karatsuba-style
algorithm), when q is a unit; it is up to 11.7 times as fast as evaluating at each power for
64-bit moduli with the top bit set, and up to 6.9 times as fast for smaller moduli.
New Content, PrimitivePart, PrimitivePartAssign, and ContentAndPrimitivePart traits, in
malachite_base::polynomial, like FLINT's fmpz_poly_content, fmpz_poly_primitive_part,
fmpq_poly_content, and fmpq_poly_primitive_part, with FLINT's sign convention: the content
is non-negative and the primitive part has a non-negative leading coefficient, so that
$p = \operatorname{sgn}(\operatorname{lc}(p)) \operatorname{cont}(p) \operatorname{pp}(p)$.
They are implemented for all four polynomial types, taking the polynomial by value or by
reference. The content of an UnsignedPolynomial<T> is a T; that of a NaturalPolynomial or
an IntegerPolynomial is a Natural, so its sign is stated by its type; and that of a
RationalPolynomial $A/d$ is the Rational $\operatorname{cont}(A)/d$, already in lowest terms.
The primitive part of a RationalPolynomial always has denominator 1, so it is an
IntegerPolynomial, and there is no PrimitivePartAssign for it. The GCD of the coefficients
stops early once it reaches 1, and content_and_primitive_part finds the content only once.
is_monic on the Polynomial trait, for all four polynomial types, like FLINT's
fmpq_poly_is_monic and nmod_poly_is_monic. The zero polynomial is not monic.
New MakeMonic and MakeMonicAssign traits, implemented for RationalPolynomial, like FLINT's
fmpq_poly_make_monic. For $p = A/d$ the monic multiple is
$\operatorname{pp}(A)/\operatorname{lc}(\operatorname{pp}(A))$, already in lowest terms; the zero
polynomial is returned unchanged.
New ModMakeMonic and ModMakeMonicAssign traits, implemented for UnsignedPolynomial<T> modulo
a T and for NaturalPolynomial modulo a Natural, like FLINT's nmod_poly_make_monic,
fmpz_mod_poly_make_monic, and fmpz_mod_poly_make_monic_f together. They return a Result:
when the leading coefficient has no inverse modulo m, the error is its GCD with m, a
nontrivial factor of m, where nmod_poly_make_monic aborts. The zero polynomial is returned
unchanged, and the coefficients must already be reduced.
Gcd and GcdAssign for Integer, with a Natural GCD, matching the Natural GCD that
ExtendedGcd for Integer already returns. $\gcd(x, y) = \gcd(|x|, |y|)$.
New FallingFactorial and CheckedFallingFactorial traits, computing the product
$x(x-1)\cdots(x-n+1)$ of the $n$ consecutive numbers counting down from $x$, or 1 when $n$ is 0.
Both are implemented for the primitive unsigned integers, where a zero factor gives an exact zero
even when the partial products before it would overflow, and FallingFactorial is implemented for
Natural and Integer. FLINT has no fmpz falling factorial; like its generic gr_falling_ui,
this computes the rising factorial of $x - n + 1$.
Neg and NegAssign for IntegerPolynomial and RationalPolynomial, like FLINT's
fmpz_poly_neg and fmpq_poly_neg. Negating by value or in place only flips signs, with no
allocation. A RationalPolynomial negates its numerator and keeps its denominator, which stays
canonical because the sign does not change the numerator's content.
ModPowerOf2Neg and ModPowerOf2NegAssign for UnsignedPolynomial<T> and NaturalPolynomial,
which negate a polynomial modulo $2^k$, like FLINT's nmod_poly_neg with the modulus $2^k$. As
for every modular operation, the coefficients must already be reduced, and this is checked. Each
nonzero coefficient $c$ becomes $2^k - c$, which is also nonzero, so the degree never changes.
ModPowerOf2Add, ModPowerOf2AddAssign, ModPowerOf2Sub, and ModPowerOf2SubAssign for
UnsignedPolynomial<T> and NaturalPolynomial, which add and subtract polynomials modulo $2^k$,
like FLINT's nmod_poly_add and nmod_poly_sub, and fmpz_mod_poly_add and fmpz_mod_poly_sub,
with the modulus $2^k$, taking each operand by value
or by reference. Both operands' coefficients must already be reduced, and this is checked. The
result is trimmed when the leading coefficients cancel modulo $2^k$.
ModNeg and ModNegAssign for UnsignedPolynomial<T> modulo a T and NaturalPolynomial
modulo a Natural, like FLINT's nmod_poly_neg and fmpz_mod_poly_neg. The coefficients must
already be reduced, and this is checked. Each nonzero coefficient $c$ becomes $m - c$, so the
degree never changes.
ModAdd, ModAddAssign, ModSub, and ModSubAssign for UnsignedPolynomial<T> modulo a T
and NaturalPolynomial modulo a Natural, like FLINT's nmod_poly_add and nmod_poly_sub, and
fmpz_mod_poly_add and fmpz_mod_poly_sub, taking each polynomial, and a Natural modulus, by
value or by reference. Both operands' coefficients must already be reduced, and
this is checked. The result is trimmed when the leading coefficients cancel modulo $m$.
CanonicalizeUnit and CanonicalizeUnitAssign for all four polynomial types, giving the
canonical associate under the units of each polynomial ring. The units of the polynomials over
the integers are $\pm 1$, so an IntegerPolynomial with a negative leading coefficient is
negated; a NaturalPolynomial or UnsignedPolynomial is already canonical, so theirs is the
identity; and the units of the polynomials over the rationals are the nonzero constants, so a
nonzero RationalPolynomial becomes its monic multiple, as make_monic gives.
Add and AddAssign for NaturalPolynomial, and Add, AddAssign, Sub, and SubAssign for
IntegerPolynomial, like FLINT's fmpz_poly_add and fmpz_poly_sub, taking each operand by
value or by reference. Taken by value, the longer operand's storage is reused, and subtracting a
longer polynomial negates it in place. An IntegerPolynomial result is trimmed when the leading
coefficients cancel; natural coefficients never cancel, so a sum of NaturalPolynomials has the
larger of the two degrees.
DivExact and DivExactAssign for IntegerPolynomial by an Integer, like FLINT's
fmpz_poly_scalar_divexact_fmpz, taking the polynomial and the divisor each by value or by
reference. Every coefficient must be divisible by the divisor; it panics on a zero divisor.
Add and AddAssign for RationalPolynomial, like FLINT's fmpq_poly_add, taking each operand
by value or by reference. The sum is kept in lowest terms, dividing out only the factor that the
denominators' GCD makes possible, and by value the storage of the operand with the longer
numerator is reused.
Sub and SubAssign for RationalPolynomial, like FLINT's fmpq_poly_sub, taking each
operand by value or by reference, with the same reduction and storage reuse as Add. Subtracting
a longer polynomial taken by value computes the reversed difference in its storage and negates
it.
Exhaustive and random UnsignedPolynomial generators, in unsigned_polynomial::exhaustive and
unsigned_polynomial::random: exhaustive_unsigned_polynomials and random_unsigned_polynomials, each with
_with_degree, _min_degree, _degree_range, and _degree_inclusive_range variants and a
_from_iterators form that takes the coefficient and leading-coefficient ite
This release adds every trigonometric and inverse trigonometric function, correctly rounded, to Float. It also adds two new complex types, GaussianInt
This release adds every trigonometric and inverse trigonometric function, correctly rounded, to Float. It also adds two new complex types, GaussianInteger and GaussianRational.
Float: sin, cos, tan, sec, csc, cot, and sin_cos, with their inverses asin, acos, atan, atan2, asec, acsc, and acot. Each of the fourteen comes in six forms: a Float or a Rational angle, measured in radians, in uths of a turn (_with_period), or in half-turns (_pi), and each also has a correctly rounded f32/f64 counterpart. This goes past MPFR, which has no secu, cscu, or cotu to match its sinu and cosu, no pi scalings of the reciprocal trio, and no asec, acsc, or acot at all. Also new: the Dottie number, the fixed point of the cosine, to any precision.GaussianInteger in malachite-nz and GaussianRational in malachite-q, each a pair of public real and imaginary fields. Arithmetic follows FLINT's fmpzi algorithms (Karatsuba and double-word multiplication, exact division, Euclidean div_rem with nearest-quotient rounding, GCD, powers, and exact square and nth roots) alongside canonicalization under the units ±1 and ±i, the full equality, ordering, and absolute-value comparison matrices against the real types, and a complete conversion matrix.Float is now in the malachite crate by default. The floats feature is on by default, so Float and the float module are re-exported at the crate root. This costs nothing extra to compile: malachite-float was already built by every default build.sin, cos, and sin_cos use the equivalent of MPFR's asymptotically fast binary-splitting tier at high precision, and multiplying any bignum by itself through aliased references (&x * &x) routes to the squaring algorithm.AbsSquared, Conjugate, MulI, DivI, MulIPow, IsGaussianInteger, IsReal, IsUnit, CanonicalizeUnit, CanonicalUnitIPow, the I and NegativeI constants, and ImaginaryFrom/ImaginaryInto, plus ContentAndPrimitivePart, Content, and PrimitivePart.PrimitiveInt and PrimitiveFloat have gained supertraits, so a type outside Malachite implementing either must now implement those too. Code that uses them only as bounds is unaffected, and gains the new methods on every primitive type.malachite crate enables floats by default, so a glob import of malachite alongside another Float is now ambiguous.malachite crate's std, random, enable_serde, and 32_bit_limbs features no longer drag the optional sub-crates into the build; each now configures whichever of naturals_and_integers, rationals, and floats is enabled, and those three build on one another. --no-default-features plus only a modifier feature now gets malachite-base alone.See the full changelog for details.
PrimitiveInt and PrimitiveFloat have gained supertraits, so a type outside Malachite that
implements either of them must now implement those too. Both gained AbsSquared,
AbsSquaredAssign, Conjugate, ConjugateAssign, IsGaussianInteger, IsReal, IsUnit,
CanonicalizeUnit, CanonicalizeUnitAssign, and CanonicalUnitIPow; PrimitiveInt also
gained IsPowerOf2, and PrimitiveFloat also gained DottieNumber. Code that uses these
traits only as bounds is unaffected, and gains the new methods on every primitive type.malachite crate now enables the floats feature by default, so Float and the float
module are re-exported at its root. This costs nothing to compile, since malachite-float was
already being built by every default build, but a glob import of malachite alongside another
Float is now ambiguous.malachite crate's std, random, enable_serde, and 32_bit_limbs features no longer
drag the optional sub-crates into the build; each now configures whichever of
naturals_and_integers, rationals, and floats is enabled. Those three build on one another
in turn, so asking for floats alone is now enough to get a usable Float. A build combining
--no-default-features with only a modifier feature, such as --features std, now gets
malachite-base alone instead of the whole workspace.I and NegativeI, and the conversion traits ImaginaryFrom and
ImaginaryInto.AbsSquared and AbsSquaredAssign traits for computing the squared absolute value of a
number, $|x|^2$, implemented for all numeric types. For real types this is the same as
squaring; for GaussianInteger and GaussianRational, abs_squared is the sum of the
squares of the real and imaginary parts (the norm), returned as an Integer or Rational
respectively, and abs_squared_assign replaces the value with the purely real $|x|^2$
embedded in the same type. Both traits are supertraits of PrimitiveInt and
PrimitiveFloat.Conjugate and ConjugateAssign traits for computing the complex conjugate of a number,
implemented for all numeric types. A real number is its own conjugate, so for the real types
these are the identity; the trivial implementations let generic code use conjugation
uniformly. For GaussianInteger and GaussianRational the sign of the imaginary part is
flipped. Both traits are supertraits of PrimitiveInt and PrimitiveFloat.IsGaussianInteger and IsReal traits alongside IsInteger, implemented for all
primitive types (and, in the other crates, all bignum types). For every type,
x.is_integer() == x.is_gaussian_integer() && x.is_real(); for floating-point types, NaN
and the infinities are neither real nor Gaussian integers.MulI, MulIAssign, DivI, and DivIAssign traits for multiplying or dividing a number
by $i$, the imaginary unit — quarter turns in the complex plane, which need no multiplication.
Nothing in malachite-base implements them; GaussianInteger and GaussianRational do.IsUnit, CanonicalUnitIPow, CanonicalizeUnit, and CanonicalizeUnitAssign traits,
ports of FLINT's fmpzi_is_unit, fmpzi_canonical_unit_i_pow, and fmpzi_canonicalise_unit:
a unit test, and canonicalization of a complex number under multiplication by $\pm 1$ and
$\pm i$, choosing the associate whose argument lies in $(-\pi/4, \pi/4]$. They are
implemented for all numeric types, so that generic code can normalize associates uniformly:
for a real type the units are $\pm 1$ (1 alone for unsigned types, and every finite nonzero
value for floats), the canonical form is the absolute value, and the power of $i$ is 2 for
negative values and 0 otherwise. All four are supertraits of PrimitiveInt and
PrimitiveFloat.IsPowerOf2 is now implemented for the signed primitive integers (negative values are never
powers of 2), and is a supertrait of PrimitiveInt rather than only of PrimitiveUnsigned.Natural, Integer, Rational, or Float by itself through aliased
references (&x * &x) now routes to the squaring algorithm, which is faster, and adding a
Float to itself through aliased references routes to a doubling shift. This extends an
existing convention: several operations, such as Integer and Natural addition and
Natural's modular operations, already detect aliased operands and take shortcuts.GaussianInteger type, parallel to Natural and Integer: a pair of public Integer
fields real and imaginary, always valid. So far it has the constants 0, 1, 2, -1, i, and
-i; Display and FromStr (strict about term structure, permissive about degenerate
coefficients like "1i" and "0i"); blanket From and ImaginaryFrom conversions from
every type that converts to Integer; serde support; and exhaustive, random, and
striped-random generators, wired into the demo, benchmark, and property-test machinery.
GaussianInteger also implements IsInteger, IsGaussianInteger, and IsReal (and
Named), and Natural and Integer implement the two new traits (trivially).Neg and NegAssign (negating both
parts), Conjugate and ConjugateAssign (flipping the sign of the imaginary part), and
componentwise addition and subtraction — Add, Sub, AddAssign, and SubAssign, in all
the usual ownership variants — and multiplication (Mul and MulAssign) for
GaussianInteger and GaussianRational. GaussianInteger multiplication uses FLINT's
fmpzi_mul strategy: double-word arithmetic when all four parts fit in a signed word, a
three-multiplication Karatsuba scheme for large balanced operands, and the fused
mul_add_mul/mul_sub_mul kernels otherwise; GaussianRational multiplication uses the
fused kernels. Both types also implement Square and SquareAssign; GaussianInteger
squaring uses FLINT's fmpzi_sqr strategy, which prefers squarings over general
multiplications and short-circuits purely real and purely imaginary values, and
GaussianRational squaring uses the same $a^2 - b^2$, $2ab$ scheme, profiting from the fact
that squaring a reduced fraction requires no GCD computations. Multiplying a Gaussian value
by itself through aliased references routes to the squaring algorithm automatically. Both
types also implement iterator Sum and Product (by value and by reference), mirroring
their component types' strategies: GaussianInteger sums by accumulating with += like
Integer, GaussianRational sums in a balanced binary-tree order like Rational, which
tends to keep intermediate denominators small, and both types multiply in a balanced
binary-tree order, short-circuiting to zero when any factor is zero, like all four real
bignum types.OrdAbs and PartialOrdAbs implementations for GaussianInteger (and, in malachite-q, for
GaussianRational), comparing absolute values — distances from the origin. Componentwise and
crosswise part comparisons decide most cases; the squared absolute values are only computed
when both pairings strictly conflict.PartialEq matrix for the Gaussian types, completing the equality-operator
convention that mixed-type comparisons get a full matrix: GaussianInteger can be compared
with Integer, Natural, primitive integers, and primitive floats;
GaussianRational (in malachite-q) with all of those plus Rational and GaussianInteger;
and Float (in malachite-float) with both Gaussian types. All comparisons work in both
directions. A Gaussian value equals a real one exactly when its imaginary part is zero and
its real part is equal; no Gaussian value equals an infinity or NaN.EqAbs, testing whether absolute values — for complex numbers, distances
from the origin — are equal, so that $3+4i$ is equal in absolute value to $5$. Comparisons
against other Gaussian values delegate to the OrdAbs screens, and comparisons against real
values only compute squared absolute values when both components are smaller in absolute
value than the real operand, mirroring the OrdAbs strategy of computing squares only as a
last resort. A non-integer float can never equal a Gaussian integer's absolute value (its odd
mantissa squares to an odd numerator), and infinities and NaN are never equal in absolute
value to anything.PartialOrdAbs, ordering by absolute value, so that $3+4i$ is greater in
absolute value than $4$ and less than $6$. The screens are the ordering counterparts of the
EqAbs ones: against a real value, a Gaussian value with two nonzero components is greater in
absolute value unless both components are smaller in absolute value than the real operand,
and only then are the squared absolute values compared; comparisons with a float square the
float exactly (as an odd square times a power of two, or as a Rational) rather than
rounding. NaN is incomparable to everything, and the infinities are greater in absolute value
than every Gaussian value.PowerOf2 and IsPowerOf2 for the Gaussian types: GaussianInteger::power_of_2(k) and
GaussianRational::power_of_2(k) (the latter also for negative k) produce purely real
powers of 2, and is_power_of_2 is true only for purely real, positive powers of 2 — $i$ and
its multiples do not count. Integer also gains IsPowerOf2, which Natural and Rational
already had; negative integers are never powers of 2 (and, in malachite-base, so does every
signed primitive integer).Shl and ShlAssign for GaussianInteger by any unsigned primitive integer, shifting both
parts (multiplying by a power of 2), in value, reference, and in-place variants. Signed shift
amounts are deliberately not supported for GaussianInteger, since a negative amount would
be a right shift and exact division by a power of 2 is not generally possible; in malachite-q,
GaussianRational supports both unsigned and signed shift amounts, a negative amount dividing
both parts exactly, and likewise Shr and ShrAssign by unsigned and signed amounts.MulI/MulIAssign and DivI/DivIAssign for both Gaussian types: multiplying by $i$ maps
$a + bi$ to $-b + ai$ and dividing by $i$ maps it to $b - ai$, by swapping the parts and
negating one of them.Reciprocal and ReciprocalAssign for GaussianRational: the conjugate divided by the squared
absolute value, with purely real and purely imaginary values reducing to a single Rational
reciprocal. Panics on zero, like Rational's.Div, DivAssign, and CheckedDiv for GaussianRational in all the usual ownership
variants. A purely real divisor divides both parts, a purely imaginary divisor does the same
and then turns the result a quarter turn, and any other divisor multiplies by its reciprocal
using the fused multiplication kernels. Division by zero panics; checked_div returns None.IsUnit, CanonicalUnitIPow, CanonicalizeUnit, and CanonicalizeUnitAssign for both
Gaussian types, matching FLINT's choices tie for tie, and for Natural, Integer (and, in
the other crates, Rational and Float), where canonical unit form is the absolute value.
GaussianInteger's units are $\pm 1$ and $\pm i$; GaussianRational is a field, so its
units are the nonzero values.SignificantBits for both Gaussian types, summing the significant bits of the real and
imaginary parts, and GaussianInteger::max_significant_bits, the larger of the two counts,
which is FLINT's fmpzi_bits and the size measure its algorithm selection uses.DivExact and DivExactAssign for GaussianInteger, a port of FLINT's fmpzi_divexact: a
purely real divisor divides both parts, a purely imaginary one does the same and turns the
result a quarter turn, quotients below $2^{45}$ are recovered by rounding a double-precision
evaluation of $x\bar{y}/N(y)$ (exact under the divisibility contract, with the operands scaled
down above 500 bits), and larger quotients go through the exact conjugate-and-norm formula.
Like the other div_exacts, an inexact division may panic or return a meaningless result.DivRem and DivAssignRem for GaussianInteger, a port of FLINT's fmpzi_divrem: the
quotient is the exact quotient with each part rounded to the nearest integer, ties up, so the
remainder satisfies $N(r) \leq N(y)/2$ (the Euclidean division of the Gaussian integers), and
a dividend more than two bits smaller than the divisor short-cuts to quotient zero./, /=, %, and %= operators and CheckedDiv for GaussianInteger, with the same
nearest-quotient rounding as div_rem; / skips computing the remainder.GaussianInteger::remove_one_plus_i and remove_one_plus_i_assign, a port of FLINT's
fmpzi_remove_one_plus_i: they divide out the largest power of $1 + i$, the Gaussian prime
above 2, by shifting out the common power of 2, fixing up the unit, and dividing once more by
$1 + i$ when the parts share a 2-adic valuation, returning the exponent; zero stays zero with
exponent 0.Gcd and GcdAssign for GaussianInteger, a port of FLINT's fmpzi_gcd without its lattice
tier: once all four parts fit in 50 bits the Euclidean algorithm runs entirely in double
precision, and until then it runs over an approximate nearest-quotient division. The result is
in canonical unit form, so it is unique; $\gcd(0, 0) = 0$.MulIPow and MulIPowAssign traits in malachite-base, multiplication by $i^k$ for a u64
exponent $k$ (only $k$ modulo 4 matters, and $i^{-k} = i^{3k}$), implemented for
GaussianInteger and GaussianRational as a port of FLINT's fmpzi_mul_i_pow_si;
canonicalize_unit is now defined through it.Pow<u64> and PowAssign<u64> for GaussianInteger, a port of FLINT's fmpzi_pow_ui: binary
exponentiation over the fused squaring and multiplication, with purely real and purely
imaginary bases reduced to an Integer power (times $i^n$ for the latter).Pow<u64>, Pow<i64>, and the matching PowAssigns for GaussianRational, structured like
the GaussianInteger version; a negative exponent takes the reciprocal, and zero to a negative
power panics, as for Rational.ContentAndPrimitivePart, Content, and PrimitivePart traits in malachite-base, for
elements of vector spaces over the rationals with a distinguished integer lattice, implemented
for GaussianInteger (content a Natural, the GCD of the parts) and GaussianRational (content
a Rational, primitive part a GaussianInteger with coprime parts). GaussianRational's power
is computed through the split, so the intermediate values carry no denominators and there is one
rational reduction per part at the end instead of several per squaring.CheckedSqrt for GaussianInteger, returning the principal square root (positive real part,
or zero real part and non-negative imaginary part) of a perfect square and None otherwise. The
root is read off the norm: $N = \sqrt{a^2 + b^2}$, then $x = \sqrt{(N + a) / 2}$ and
$y = \pm \sqrt{(N - a) / 2}$ with the sign of $b$. GaussianInteger::checked_sqrts returns
all the roots as a Vec: none, one for zero, or the principal root and its negative, in the
canonical order of ComparableGaussianInteger (lexicographic by real part, then imaginary).CheckedSqrt and checked_sqrts for GaussianRational too, by clearing denominators: with
$L$ the LCM of the denominators and $S = Lz$, $z$ is a square exactly when the Gaussian
integer $SL$ is, and $\sqrt{z} = \sqrt{SL} / L$.CheckedRoot<u64> and checked_roots for GaussianInteger. A nonzero Gaussian integer has
either no $n$th roots or exactly $\gcd(n, 4)$ of them; the principal one has argument in
$(-\pi/g, \pi/g]$ for $g = \gcd(n, 4)$, which is the unique root for odd $n$, the
checked_sqrt convention for $n \equiv 2 \pmod 4$, and the canonical unit form for
$4 \mid n$. The odd part of the exponent is handled exactly through the norm and a Gaussian
GCD, and the power of 2 by iterated square roots; no floating point is involved.CheckedRoot<u64> and checked_roots for GaussianRational, by clearing denominators: with
$L$ the LCM of the denominators and $S = Lz$, any root $w$ has $Lw$ integral, so $Lw$ is the
Gaussian integer root of $S L^{n-1}$.ComparableGaussianInteger and ComparableGaussianIntegerRef, wrappers around
GaussianInteger (by value and by reference) that implement Ord, comparing
lexicographically: first by real part, then by imaginary part. Since no total order on the
complex numbers is compatible with arithmetic, GaussianInteger itself does not implement
Ord; the wrappers provide a canonical order for sorting and for use as BTreeMap and
BTreeSet keys, in the spirit of malachite-float's ComparableFloat and
ComparableFloatRef.GaussianInteger and the real types, completing the conversion matrix:
TryFrom and ConvertibleFrom implementations for Integer (succeeding when the value is
real), Natural (real and non-negative), all primitive integers (real and representable),
and all primitive floats (real and exactly representable), plus TryFrom and
ConvertibleFrom from primitive floats (finite integers), mirroring the corresponding
Rational conversion families.GaussianRational type, parallel to GaussianInteger: public Rational fields real
and imaginary, always valid, with the same surface — constants, Display and FromStr
(imaginary terms attach i to the numerator, as in "i/2" and "2/3-5i/6"), From
conversions from every type that converts to Rational and componentwise conversions from
GaussianInteger, a blanket ImaginaryFrom, serde support,
and the full exhaustive/random/striped generator set with demo, benchmark, and property-test
plumbing. GaussianRational also implements IsInteger, IsGaussianInteger, and IsReal
(and Named), and Rational implements the two new traits.ComparableGaussianRational and ComparableGaussianRationalRef, wrappers around
GaussianRational that implement Ord lexicographically (real part first, then imaginary
part), mirroring malachite-nz's ComparableGaussianInteger wrappers: a canonical order for
sorting and for BTreeMap/BTreeSet keys.GaussianRational and the real types, completing the conversion matrix:
TryFrom and ConvertibleFrom implementations for Rational (succeeding when the value is
real), GaussianInteger (both parts integers), Integer (a real integer), Natural (a real
non-negative integer), all primitive integers (real and representable), and all primitive
floats (real and exactly representable), plus TryFrom and ConvertibleFrom from primitive
floats (finite values) and from GaussianInteger (componentwise, added earlier in this
cycle). Rational also gets TryFrom and ConvertibleFrom from GaussianInteger.Float implements the new IsGaussianInteger and IsReal traits; a Float is real unless
it is NaN or infinite.Cos and CosAssign (new traits in malachite-base) for
Float, with the usual cos_prec_round, cos_prec, cos_round, and _ref/_assign
variants. Arguments of magnitude 4 or more are reduced modulo $2\pi$, so the cost grows with
the input's exponent as well as with the precision. Inputs extremely close to an odd multiple
of $\pi/2$ take a dedicated path that computes the distance to that multiple exactly, so the
result is correct, and underflows correctly, even when the input agrees with the multiple to
more than $2^{30}$ bits (a regime MPFR's wider exponent range never reaches).Sin and SinAssign (new traits in malachite-base) for Float, with the usual
sin_prec_round, sin_prec, sin_round, and _ref/_assign variants: a port of mpfr_sin,
which derives the sine from the cosine as $\pm\sqrt{1-\cos^2 x}$ after reducing arguments of
magnitude 2 or more modulo $2\pi$. Inputs extremely close to a nonzero multiple of $\pi$ share
the cosine's exact near-zero path, so the result is correct, and underflows correctly, even
when the input agrees with the multiple to more than $2^{30}$ bits; the path is also taken as
soon as the argument reduction detects such an input, where MPFR keeps raising its working
precision instead.sin_rational_prec_round and sin_rational_prec (with _ref variants), the sine of a
Rational as a Float, alongside the cosine versions. Small inputs are handled by the sine
series in exact Rational arithmetic, so inputs too small to be Floats underflow correctly.sin_with_period_prec_round, sin_with_period_prec, and sin_with_period_round (with _ref
and _assign variants), a port of mpfr_sinu: the sine of a Float measured in $u$ths of a
turn. Multiples of a quarter of a turn are exact (a multiple of a half turn is a zero with the
sign of the input, as IEEE 754-2019's sinPi specifies), as are the twelfths whose sine is
$\pm1/2$, and thirds, sixths, eighths, and twentieths of a turn are computed from a single
correctly rounded constant ($\sqrt3$, $\sqrt2$, or $\varphi$). Inputs within $2^{-2^{30}}$ of a
half turn underflow correctly. sin_with_period_rational_prec_round and
sin_with_period_rational_prec (with _ref variants) take a Rational instead, reaching the
exact and closed-form cases directly, such as a twelfth or a twentieth of a turn.
primitive_float_sin_with_period and primitive_float_sin_with_period_rational give the
correctly rounded f32 or f64 results.sin_pi_prec_round, sin_pi_prec, and sin_pi_round (with _ref and _assign variants),
sin_pi_rational_prec_round and sin_pi_rational_prec (with _ref variants), and
primitive_float_sin_pi and primitive_float_sin_pi_rational: a port of mpfr_sinpi, the
sine in half-turns, delegating to the sin_with_period family with a period of 2.SinCos and SinCosAssign (new traits in malachite-base) for Float, with the usual
sin_cos_prec_round, sin_cos_prec, sin_cos_round, and _ref/_assign variants: a port of
mpfr_sin_cos, computing the sine and cosine together with one argument reduction. The two
results and their two ternary Orderings are returned as a 4-tuple, and the _assign variants
write the cosine to a second &mut Float. Inputs extremely close to a zero of either function
take that function's exact near-zero path, so the results are correct, and underflow correctly,
even when the input agrees with the zero to more than $2^{30}$ bits.
sin_cos_rational_prec_round and sin_cos_rational_prec (with _ref variants) take a
Rational instead, sharing the input rounding and, for inputs too large to be Floats, the
reduction modulo $2\pi$ that dominates their cost. primitive_float_sin_cos and
primitive_float_sin_cos_rational give the correctly rounded f32 or f64 pairs.sin_cos_with_period_prec_round, sin_cos_with_period_prec, and sin_cos_with_period_round
(with _ref and _assign variants): the sine and cosine of a Float measured in $u$ths of a
turn, together, with one argument reduction, one computation of $2\pi x/u$, and one sin_cos
per iteration. MPFR has no such function. The results are those of the sin_with_period and
cos_with_period families, including the exact quarter turns, the closed-form twelfths, sixths,
and eighths, and the near-zero paths, so inputs within $2^{-2^{30}}$ of a multiple of a quarter
turn underflow correctly. sin_cos_with_period_rational_prec_round and
sin_cos_with_period_rational_prec (with _ref variants) take a Rational instead, and
primitive_float_sin_cos_with_period and primitive_float_sin_cos_with_period_rational give
the correctly rounded f32 or f64 pairs. sin_cos_pi_prec_round, sin_cos_pi_prec, and
sin_cos_pi_round (with _ref and _assign variants), sin_cos_pi_rational_prec_round and
sin_cos_pi_rational_prec (with _ref variants), and primitive_float_sin_cos_pi and
primitive_float_sin_cos_pi_rational are the same in half-turns, delegating with a period of 2.Tan and TanAssign (new traits in malachite-base) for Float, with the usual
tan_prec_round, tan_prec, tan_round, and _ref/_assign variants: a port of mpfr_tan,
the sine and cosine together and their quotient in one Ziv loop. Unlike MPFR's, the result can
overflow (an input within $2^{-2^{30}}$ of an odd multiple of $\pi/2$) or underflow (within that
distance of a multiple of $\pi$); both are decided from exact brackets. tan_rational_prec_round
and tan_rational_prec (with _ref variants) take a Rational instead, with a direct series
bracket for tiny inputs, including those below the Float exponent range. primitive_float_tan
and primitive_float_tan_rational give the correctly rounded f32 or f64 tangent.tan_with_period_prec_round, tan_with_period_prec, and tan_with_period_round (with _ref
and _assign variants), a port of mpfr_tanu: the tangent of a Float measured in $u$ths of a
turn. Multiples of a quarter turn are exact: a multiple of a half turn is a zero (reached from
below, so that the function is odd), and an odd multiple of a quarter turn is a pole, returning
an infinity; odd multiples of an eighth of a turn are $\pm1$, and thirds, sixths, and twelfths
of a turn are computed from $\sqrt3$ or $\sqrt3/3$. Inputs within $2^{-2^{30}}$ of a multiple of
a quarter turn overflow or underflow correctly. tan_with_period_rational_prec_round and
tan_with_period_rational_prec (with _ref variants) take a Rational instead, reaching the
exact and closed-form cases directly and needing no argument reduction beyond the exact one.
primitive_float_tan_with_period and primitive_float_tan_with_period_rational give the
correctly rounded f32 or f64 tangent; a primitive float is never merely close enough to a
pole to overflow, but a Rational can be.Atan and AtanAssign (new traits in malachite-base) for Float, with the usual
atan_prec_round, atan_prec, atan_round, and _ref/_assign variants: a port of
mpfr_atan, the first of the inverse trigonometric functions. $\pm0.0$ gives $\pm0.0$, the only
exact case, and $\pm\infty$ gives $\pm\pi/2$; the arctangent is odd and bounded, so it never
overflows. atan_with_period_prec_round, atan_with_period_prec, atan_with_period_round, and
atan_with_period (with _ref and _assign variants) are a port of mpfr_atanu, measuring it
in $u$ths of a turn as $\arctan(x)u/(2\pi)$ — the inverse of the convention sin_with_period
uses for its input — where an infinite input gives a quarter turn, $\pm1$ an eighth, and a zero
input or a zero period a zero with the sign of $x$; those are the only exact cases, and the
result underflows for a tiny $x$ with a small $u$. atan_pi_prec_round, atan_pi_prec,
atan_pi_round, and atan_pi (with the usual variants) are that with $u = 2$: IEEE 754's
atanPi, whose exact cases hold at every precision. Each of the three has _rational variants
taking a Rational, which MPFR has no equivalent of, and primitive_float_* variants giving
correctly rounded f32 and f64 results.Atan2 and Atan2Assign (new traits in malachite-base) for Float, with the usual
atan2_prec_round, atan2_prec, atan2_round, and _val_ref/_ref_val/_ref_ref/_assign
variants: a port of mpfr_atan2, the angle of the point $(x,y)$ measured from the positive
$x$-axis. The twenty ISO C99 special cases are honored, with the sign of a zero argument choosing
the quadrant, and the zero results are the only exact ones. atan2_with_period_prec_round,
atan2_with_period_prec, and atan2_with_period_round are a port of mpfr_atan2u, measuring
the angle in $u$ths of a turn, where the axes and the quadrant diagonals are exact;
atan2_pi_prec_round, atan2_pi_prec, and atan2_pi_round are that with $u = 2$, IEEE 754's
atan2Pi and a port of mpfr_atan2pi. The result underflows for a positive $x$ with a tiny
$|y/x|$. Two deliberate divergences from MPFR: when $u$ is zero this returns a zero with the sign
of $y$ throughout, where mpfr_atan2u returns $\pm1$ for a negative $x$, contradicting its own
definition and its own answers when $y$ is zero or infinite; and a quotient beyond the exponent
range is answered from the turn fraction it approaches, where MPFR, whose widened range keeps the
quotient representable, can instead spend an unbounded amount of time separating that fraction
from the one beside it. With _rational and primitive_float_* variants throughout.Asin and AsinAssign (new traits in malachite-base) for Float, with the usual
asin_prec_round, asin_prec, asin_round, and _ref/_assign variants: a port of
mpfr_asin. NaN, either infinity, and any $|x|>1$ give NaN; $\pm0.0$ is exact and $\pm1$ gives
$\pm\pi/2$. The arcsine can neither overflow nor underflow. asin_with_period_prec_round,
asin_with_period_prec, asin_with_period_round, and asin_with_period (with the usual
variants) are a port of mpfr_asinu, measuring it in $u$ths of a turn, so that $u = 360$ gives
degrees, where $\pm1$ gives $\pm u/4$ and $\pm1/2$ gives $\pm u/12$ when $u$ is a multiple of 3;
asin_pi_prec_round and friends are a port of mpfr_asinpi, that with $u = 2$. One deliberate
divergence from MPFR: at $u = 0$ mpfr_asinu returns $+0$ for every $x$, although its own
$x = 0$ case keeps the sign so that the function stays odd; Malachite keeps it throughout, as
mpfr_atanu does. The _rational variants, which MPFR has no equivalent of, can underflow where
the Float ones cannot, a Rational reaching below the exponent range. With primitive_float_*
variants throughout.Acos and AcosAssign (new traits in malachite-base) for Float, with the usual
acos_prec_round, acos_prec, acos_round, and _ref/_assign variants: a port of
mpfr_acos. NaN, either infinity, and any $|x|>1$ give NaN; $\pm0.0$ gives $\pi/2$, $1$ gives
$0.0$, and $-1$ gives $\pi$. The zero at $x = 1$ is the only exact case — unlike the arcsine, a
zero input is not one, $\pi/2$ never being representable — and overflow is not possible, the
result lying in $[0,\pi]$. acos_with_period_prec_round, acos_with_period_prec,
acos_with_period_round, and acos_with_period (with the usual variants) are a port of
mpfr_acosu, measuring it in $u$ths of a turn, where a zero input gives $u/4$, $1$ gives $0.0$
following IEEE 754-2019's acosPi, $-1$ gives $u/2$, and $\pm1/2$ gives $u/6$ or $u/3$ when $u$
is a multiple of 3; acos_pi_prec_round and friends are a port of mpfr_acospi, that with
$u = 2$. The _rational variants can underflow where the Float ones cannot, a Rational being
able to lie within $2^{-2^{31}}$ of 1. With primitive_float_* variants throughout.Asec and AsecAssign (new traits in malachite-base) for Float, with the usual
asec_prec_round, asec_prec, asec_round, and _ref/_assign variants. MPFR has no
arcsecant, nor any of the forms below. NaN and every $|x|<1$, including the zeros, give NaN;
$\pm\infty$ gives $\pi/2$, the value the secant grows toward; $1$ gives $0.0$, the only exact
case; and $-1$ gives $\pi$. asec_with_period_prec_round, asec_with_period_prec,
asec_with_period_round, and asec_with_period (with the usual variants) measure it in $u$ths
of a turn, with the arccosine's exact cases seen through the reciprocal: $\pm\infty$ gives $u/4$,
$1$ gives $0.0$, $-1$ gives $u/2$, and $\pm2$ give $u/6$ and $u/3$ when $u$ is a multiple of 3.
asec_pi_prec_round and friends are that with $u = 2$, where $\pm2$ are no longer exact, a third
of a half-turn not being representable. The _rational variants can underflow, a Rational
being able to lie within $2^{-2^{31}}$ of 1. With primitive_float_* variants throughout.Acsc and AcscAssign (new traits in malachite-base) for Float, with the usual
acsc_prec_round, acsc_prec, acsc_round, and _ref/_assign variants. MPFR has no
arccosecant, nor any of the forms below. The arccosecant is odd. NaN and every $|x|<1$, including
the zeros, give NaN; $\pm\infty$ give $\pm0.0$, the only exact cases; and $\pm1$ give $\pm\pi/2$.
Neither overflow nor underflow is possible, a Float's bounded exponent keeping $1/|x|$ above
twice the smallest positive one. acsc_with_period_prec_round, acsc_with_period_prec,
acsc_with_period_round, and acsc_with_period (with the usual variants) measure it in $u$ths
of a turn, with the arcsine's exact cases seen through the reciprocal: a zero period gives a zero
with the sign of $x$, $\pm1$ give $\pm u/4$, and $\pm2$ give $\pm u/12$ when $u$ is a multiple of
3. acsc_pi_prec_round and friends are that with $u = 2$, where $\pm2$ are no longer exact, a
sixth of a half-turn not being representable. Unlike the arccosecant alone, the periodic forms
underflow, a small $u$ carrying the quotient below the smallest positive Float. With
_rational and primitive_float_* variants throughout.Acot and AcotAssign (new traits in malachite-base) for Float, with the usual
acot_prec_round, acot_prec, acot_round, and _ref/_assign variants. MPFR has no
arccotangent, nor any of the forms below. This is the odd branch,
$\operatorname{acot} x = \arctan(1/x)$, with range $(-\pi/2,\pi/2]$: the one that makes the
arcsecant, arccosecant and arccotangent a uniform family of inverses of reciprocal arguments,
that inverts cot on its own signed behaviour ($\cot(\pm0)=\pm\infty$ and so
$\operatorname{acot}(\pm\infty)=\pm0$), and that Mathematica uses; the continuous branch
$\pi/2-\arctan x$ with range $(0,\pi)$ is not provided. NaN gives NaN; $\pm\infty$ give $\pm0.0$,
the only exact cases; $\pm0.0$ give $\pm\pi/2$, the sign choosing the side of the jump; and
$\pm1$ give $\pm\pi/4$. Neither overflow nor underflow is possible.
acot_with_period_prec_round, acot_with_period_prec, acot_with_period_round, and
acot_with_period (with the usual variants) measure it in $u$ths of a turn, where a zero period
gives a zero with the sign of $x$, $\pm0.0$ give $\pm u/4$ — the jump's two sides, which a period
makes exact — and $\pm1$ give $\pm u/8$. acot_pi_prec_round and friends are that with $u = 2$,
which unlike the arcsecant's and arccosecant's half-turns loses no exact case, a half and a
quarter each needing one bit. The periodic forms underflow for a large enough $|x|$. A Rational
zero has no sign, so the _rational variants give it the positive side. With primitive_float_*
variants throughout.Cot and CotAssign (new traits in malachite-base) for Float, with the usual
cot_prec_round, cot_prec, cot_round, and _ref/_assign variants: a port of mpfr_cot,
MPFR's generic reciprocal template with the tangent. MPFR's tangent is itself a quotient of a
sine and a cosine, so the cotangent is taken as $\cos x/\sin x$ directly, which saves the middle
rounding and treats the two ends of the exponent range alike. Unlike the secant and the cosecant,
the cotangent is not bounded away from zero, so it both overflows, within $2^{-2^{30}}$ of a
multiple of $\pi$, and underflows, within $2^{-2^{30}}$ of an odd multiple of $\pi/2$; each end
is decided from an exact bracket. MPFR's shortcut for a tiny input is kept and is load-bearing:
there $\cot x$ is $1/x - x/3 + \ldots$, so rounding $1/x$ settles the result, except when $x$ is
a power of 2 and $1/x$ is exact, where the true value lies one step short of it, toward zero.
Without it the Ziv loop would face an exactly representable quotient that no working precision
could certify. cot(\pm0.0) is $\pm\infty$, and the function is odd.
primitive_float_cot gives the correctly rounded f32 or f64 cotangent, which neither the
standard library nor libm provides; it overflows for a small enough input.
cot_rational_prec_round and cot_rational_prec (with _ref variants) take a Rational
instead, with a direct bracket for a tiny input, inverting the tangent's own series bracket; that
also covers inputs below the Float exponent range, which no other path could round, and the
powers of 2, whose reciprocals are exactly representable and which the Ziv loop could therefore
never certify. primitive_float_cot_rational gives the correctly rounded f32 or f64
cotangent of a Rational.cot_with_period_prec_round, cot_with_period_prec, cot_with_period_round, and
cot_with_period (with _ref and _assign variants), the cotangent of a Float measured in
$u$ths of a turn. MPFR has no cotu; this is cot with the sine and cosine taken in turns, which
reduces the argument exactly and so reaches the exact and closed-form cases the radian version
cannot see. These are the tangent's, reciprocated: odd multiples of $1/8$ of a turn give exactly
$\pm1$, odd multiples of $1/4$ give exactly $\pm0.0$, and thirds and sixths give
$\pm\sqrt3/3$ while twelfths give $\pm\sqrt3$. Multiples of a half turn are the poles, where
the sine is a zero carrying the sign of $x$ and the cosine is $\pm1$, so the infinity takes the
sign of $x$ at an even multiple and the opposite at an odd one; keeping that identity is what
makes the function odd. primitive_float_cot_with_period gives the correctly rounded f32 or
f64 cotangent in $u$ths of a turn.
cot_with_period_rational_prec_round and cot_with_period_rational_prec (with _ref variants)
take a Rational instead, reaching the exact and closed-form cases directly and needing no
argument reduction beyond the exact one. A Rational fraction of a turn can be small enough, or
close enough to a multiple of a half turn, to overflow, and as close to an odd quarter turn to
underflow; each end is decided from an exact bracket.
primitive_float_cot_with_period_rational gives the correctly rounded f32 or f64 cotangent
of a Rational fraction of a turn.cot_pi_prec_round, cot_pi_prec, cot_pi_round, and cot_pi (with _ref and _assign
variants), the cotangent of a Float measured in half-turns, delegating to cot_with_period
with a period of 2; MPFR has no cotpi to match its sinpi and cospi. Integers are poles and
give $\pm\infty$, with the sign of $x$ at an even integer and the opposite at an odd one;
half-integers give $\pm0.0$, odd multiples of $1/4$ give $\pm1$, odd multiples of $1/6$ give
$\pm\sqrt3$, and multiples of $1/3$ that are not integers give $\pm\sqrt3/3$.
cot_pi_rational_prec_round and cot_pi_rational_prec (with _ref variants) take a Rational
instead, and primitive_float_cot_pi and primitive_float_cot_pi_rational give the correctly
rounded f32 or f64 cotangent.Csc and CscAssign (new traits in malachite-base) for Float, with the usual
csc_prec_round, csc_prec, csc_round, and _ref/_assign variants: a port of mpfr_csc,
MPFR's generic reciprocal template with the sine. The cosecant never underflows, since its
magnitude is at least 1, but unlike MPFR's it can overflow: within $2^{-2^{30}}$ of a multiple of
$\pi$, and for any input whose reciprocal alone leaves the range. MPFR's shortcut for a tiny
input is kept, where $\csc x$ is $1/x + x/6 + \ldots$ and rounding $1/x$ settles the result
except when $x$ is a power of 2; without it the Ziv loop could never certify an exactly
representable reciprocal. csc(\pm0.0) is $\pm\infty$, and the function is odd.
primitive_float_csc gives the correctly rounded f32 or f64 cosecant, which overflows for a
small enough input.
csc_rational_prec_round and csc_rational_prec (with _ref variants) take a Rational
instead, with a direct bracket for a tiny input, inverting a bracket on the sine; that also
covers inputs below the Float exponent range, which no other path could round.
primitive_float_csc_rational gives the correctly rounded f32 or f64 cosecant of a
Rational.csc_with_period_prec_round, csc_with_period_prec, csc_with_period_round, and
csc_with_period (with _ref and _assign variants), the cosecant of a Float measured in
$u$ths of a turn. MPFR has no cscu; this is csc with the sine taken in turns, which reduces
the argument exactly and so reaches the exact and closed-form cases the radian version cannot
see: odd quarter turns give $\pm1$, odd twelfths give $\pm2$, eighths give $\pm\sqrt2$, thirds
and sixths give $\pm2\sqrt3/3$, and twentieths give $\pm2\varphi$ or $\pm2(\varphi-1)$, where
$\varphi$ is the golden ratio. Multiples of a half turn are poles, where the sine is a zero
carrying the sign of the input and the cosecant is its reciprocal, an infinity with that sign;
keeping that identity is what makes the function odd everywhere, at the cost of period $u$ at a
pole alone. Unlike the secant's, this cosecant can overflow away from a pole, since a tiny angle
has a huge cosecant; such a result is decided from an exact bracket on the sine.
primitive_float_csc_with_period gives the correctly rounded f32 or f64 cosecant in $u$ths
of a turn, which does overflow for a small enough angle.
csc_with_period_rational_prec_round and csc_with_period_rational_prec (with _ref variants)
take a Rational instead, reaching the exact and closed-form cases directly and needing no
argument reduction beyond the exact one. The radian version's shortcut for a tiny input has no
counterpart here: in turns the angle is never a Float, so by Niven's theorem the sine past the
closed-form cases is irrational and its reciprocal is never exactly representable, which is what
stalls the radian loop. A Rational fraction of a turn can be small enough, or close enough to a
multiple of a half turn, that the sine falls below the Float exponent range; the bracket reads
that as the overflow it is. primitive_float_csc_with_period_rational gives the correctly
rounded f32 or f64 cosecant of a Rational fraction of a turn.csc_pi_prec_round, csc_pi_prec, csc_pi_round, and csc_pi (with _ref and _assign
variants), the cosecant of a Float measured in half-turns, delegating to csc_with_period with
a period of 2; MPFR has no cscpi to match its sinpi and cospi. Integers are poles and give
$\pm\infty$ with the sign of $x$, half-integers give $\pm1$, odd multiples of $1/6$ give
$\pm2$, odd multiples of $1/4$ give $\pm\sqrt2$, and multiples of $1/3$ that are not integers
give $\pm2\sqrt3/3$. csc_pi_rational_prec_round and csc_pi_rational_prec (with _ref
variants) take a Rational instead, and primitive_float_csc_pi and
primitive_float_csc_pi_rational give the correctly rounded f32 or f64 cosecant.Sec and SecAssign (new traits in malachite-base) for Float, with the usual
sec_prec_round, sec_prec, sec_round, and _ref/_assign variants: a port of mpfr_sec,
which instantiates MPFR's generic reciprocal template with the cosine. The secant never
underflows, since its magnitude is at least 1, but unlike MPFR's it can overflow, for an input
within $2^{-2^{30}}$ of an odd multiple of $\pi/2$; such a result is decided from an exact
bracket on the cosine. primitive_float_sec gives the correctly rounded f32 or f64 secant,
which neither the standard library nor libm provides.
sec_rational_prec_round and sec_rational_prec (with _ref variants) take a Rational
instead, with a direct series bracket for a tiny input: there the cosine rounds toward zero to
the Float just below 1, whose reciprocal ties back to 1 at every working precision, so the Ziv
loop would not terminate without it. primitive_float_sec_rational gives the correctly rounded
f32 or f64 secant of a Rational.sec_with_period_prec_round, sec_with_period_prec, sec_with_period_round, and
sec_with_period (with _ref and _assign variants), the secant of a Float measured in $u$ths
of a turn. MPFR has no secu; this is sec with the cosine taken in turns, which reduces the
argument exactly and so reaches the exact and closed-form cases the radian version cannot see:
even multiples of a half turn give $1$ and odd ones $-1$, thirds and sixths give $\pm2$, eighths
give $\pm\sqrt2$, twelfths give $\pm2\sqrt3/3$, and fifths and tenths give $\pm2\varphi$ or
$\pm2(\varphi-1)$, where $\varphi$ is the golden ratio. Odd multiples of a quarter turn are poles,
where the cosine is $+0.0$ and the secant is its reciprocal, $\infty$; keeping that identity is
what makes the function even everywhere. primitive_float_sec_with_period gives the correctly
rounded f32 or f64 secant in $u$ths of a turn; like the tangent's, it can only reach an
infinity at an exact pole, never through overflow.
sec_with_period_rational_prec_round and sec_with_period_rational_prec (with _ref variants)
take a Rational instead, reaching the exact and closed-form cases directly and needing no
argument reduction beyond the exact one. primitive_float_sec_with_period_rational gives the
correctly rounded f32 or f64 secant of a Rational fraction of a turn.sec_pi_prec_round, sec_pi_prec, sec_pi_round, and sec_pi (with _ref and _assign
variants), the secant of a Float measured in half-turns, delegating to sec_with_period with a
period of 2; MPFR has no secpi to match its sinpi and cospi. Even integers give $1$ and odd
ones $-1$, half-integers are poles and give $\infty$, odd multiples of $1/4$ give $\pm\sqrt2$,
and multiples of $1/3$ give $\pm2$. sec_pi_rational_prec_round and sec_pi_rational_prec (with
_ref variants) take a Rational instead, and primitive_float_sec_pi and
primitive_float_sec_pi_rational give the correctly rounded f32 or f64 secant.tan_pi_prec_round, tan_pi_prec, tan_pi_round, and tan_pi (with _ref and _assign
variants), a port of mpfr_tanpi: the tangent of a Float measured in half-turns, delegating to
tan_with_period with a period of 2. Integers give a signed zero, half-integers are poles and
give an infinity, odd multiples of a quarter give $\pm1$, and thirds and sixths give $\pm\sqrt3$
or $\pm\sqrt3/3$. tan_pi_rational_prec_round and tan_pi_rational_prec (with _ref variants)
take a Rational instead, and primitive_float_tan_pi and primitive_float_tan_pi_rational
give the correctly rounded f32 or f64 tangent.sin_with_period, cos_with_period, tan_with_period, sin_cos_with_period, sin_pi,
cos_pi, and sin_cos_pi on Float (each with _ref and _assign variants), rounding to the
precision of the input and to the nearest Float. This is the tier that sin, cos, tan, and
sin_cos already had through their traits; a function that takes a period cannot go through one,
since Sin and its siblings take no extra argument, so these are inherent methods.dottie_number_prec_round and
dottie_number_prec on Float, correctly rounded to any precision (Newton's method with a
certified final bracket), and as a DottieNumber trait with constants for primitive floats.sin, cos, and sin_cos now use MPFR's asymptotically fast tier (mpfr_sincos_fast, binary
splitting of the Taylor series over chunks of the reduced argument, combined by the angle-addition
formulas) at and above a tuned precision threshold (25285 bits), as MPFR does at its
MPFR_SINCOS_THRESHOLD, bringing their cost from $O(n^{3/2})$ to $O(n \log^3 n)$ word
operations up to log factors. The tuner (-g tune_sincos in the malachite-float binary)
shares its crossover machinery with malachite-nz's, now in
malachite_base::test_util::bench::tune.cos_with_period_rational_prec_round taking a working precision of billions of bits for a
tiny negative input, and cos_with_period_prec_round doing the same for a Float just below a
multiple of its period: the fraction of a turn is now reduced to $[-1/2, 1/2]$, where the
small-input shortcut applies.primitive_float_sin and primitive_float_sin_rational, the correctly rounded sine of an f32
or f64, or of a Rational as an f32 or f64.primitive_float_cos and primitive_float_cos_rational, the correctly rounded cosine of an
f32 or f64, or of a Rational as an f32 or f64, alongside the existing
primitive_float_exp and primitive_float_exp_rational.Float remainders (rem and ieee_remainder families) by a divisor of more than
$2^{30}$ bits with an odd mantissa, which overflowed to infinity: the integer remainder was
rounded to a Float before the final shift brought it back into range. cos of an argument
with a near-maximal exponent reduces modulo such a $2\pi$ and was affected.cos_with_period_prec_round, cos_with_period_prec, and cos_with_period_round (with _ref and _assign variants),
a port of mpfr_cosu: the cosine of a Float measured in $u$ths of a turn, so that u = 360
is degrees. Multiples of a quarter or a sixth of a turn are exact (an odd quarter turn is
$+0.0$, as IEEE 754-2019's cosPi specifies), and eighths, twelfths, fifths, and tenths of a
turn are computed from a single correctly rounded constant ($\sqrt2$, $\sqrt3$, or $\varphi$)
rather than from $\pi$ and a cosine. Inputs within $2^{-2^{30}}$ of an odd quarter turn
underflow correctly. cos_with_period_rational_prec_round and cos_with_period_rational_prec
(with _ref variants) take a Rational instead, reaching the exact and closed-form cases
directly, such as a third or an eighth of a turn. primitive_float_cos_with_period and
primitive_float_cos_with_period_rational give the correctly rounded f32 or f64 results.cos_pi_prec_round, cos_pi_prec, and cos_pi_round (with _ref and _assign variants),
cos_pi_rational_prec_round and cos_pi_rational_prec (with _ref variants), and
primitive_float_cos_pi and primitive_float_cos_pi_rational: a port of mpfr_cospi, the
cosine in half-turns, delegating to the cos_with_period family with a period of 2.cos_rational_prec_round and cos_rational_prec (with _ref variants), the correctly
rounded cosine of a Rational as a Float, alongside the exp_rational_* family. Since
cosine is not monotonic, the result is bracketed by a Lipschitz bound around the cosine of a
Float approximation rather than by bracketing the input, with exact Rational handling near
odd multiples of $\pi/2$ and for inputs too large to be Floats.Float and the Gaussian types: TryFrom and ConvertibleFrom
implementations converting GaussianInteger and GaussianRational to Float (real and, for
the rational case, dyadic; minimal precision) and Float to either Gaussian type (finite,
and integral for GaussianInteger).FromStr docs for Natural, Integer, and Rational now mention the accepted leading
'+' (and, for Rational, the '+' allowed on the denominator), which the parsers had
always accepted.This release brings a large batch of number-theoretic functions, broad new MPFR coverage for Float, upgrades to the num-bigint compatibility crate, an
This release brings a large batch of number-theoretic functions, broad new MPFR coverage for Float, upgrades to the num-bigint compatibility crate, and new documentation for users coming from other bignum libraries.
Natural/Integer): the Chinese remainder theorem, modular division and modular square roots, Bell numbers, Landau's function, rising factorials, and Dedekind sums, plus Rational GCD, rational reconstruction, harmonic numbers, and a redesign of the denominators-in-interval functions that makes some of them hundreds of times faster.Float: correctly rounded sums, products, and dot products; fused multiply-adds (add_mul, mul_add_mul); hypot, compound, min/max, remainders, and the round-to-integer family; can_round and subnormalize (enabling faithful emulation of IEEE formats such as quad precision); random samplers matching MPFR bit for bit; and new constants (Euler's γ, Catalan's, and the digit-defined Liouville, Champernowne, and Copeland–Erdős constants) completing coverage of MPFR's constants.serde, rand, arbitrary, and quickcheck features that match num-bigint 0.4.8 exactly (identical serialization format, bit-identical random streams), behavioral fixes for num-bigint parity, and a completed API surface.Average, Compound, RisingFactorial, MulAddMul/MulSubMul, and OrdDouble, plus GMP-style formatting via gmp_format!.Float::increment and Float::decrement are now precision-preserving neighbor steps, matching IEEE nextUp/nextDown and MPFR's mpfr_nextabove/nextbelow.+ flag or fill/alignment specifiers now follows the standard library's rules.Roots for BigInt truncates toward zero on negative inputs and modinv returns None instead of panicking, both matching num-bigint.Ten pages documenting, function by function, how Malachite corresponds to the libraries you may be coming from:
Or start from the overview.
See the full changelog for details.
The main themes of this release are a large batch of number-theoretic functions (CRT, modular
division and square roots, rational reconstruction, and a family of combinatorial sequences),
broad new MPFR coverage for Float (correctly rounded sums, products, and fused operations;
remainders and rounding functions; bit-exact random samplers; and the constants that complete
the MPFR constants section), ten transition-mapping pages on the website documenting how
Malachite corresponds to GMP, MPFR, FLINT, and num, and a substantial upgrade of the num-bigint
compatibility crate.
Float::increment and Float::decrement are now precision-preserving neighbor steps,
matching IEEE nextUp/nextDown, MPFR's mpfr_nextabove/nextbelow, and Rust's
f64::next_up/next_down. Previously they were full-ulp steps that could change a value's
precision at binade boundaries and collapsed precision-1 powers of 2 to zero. If the old
behavior is needed, write x ± x.ulp().Natural/Integer div_mod, div_rem, and div_exact return
a quotient of 1 when both operands were zero.Integer (or a signed primitive through BaseFmtWrapper) with the +
flag, a fill/alignment specifier, or a plain width now follows the standard library's rules.
Previously {:+} printed a stray plus after the minus sign and any width forced zero-padding,
ignoring fill and alignment. Zero-padded forms like {:08} are unchanged.Roots for BigInt now truncates toward zero on negative inputs instead
of flooring, and modinv returns None instead of panicking when the value is a multiple of
the modulus — both matching num-bigint.Average (floor and ceiling midpoints, implemented everywhere),
Compound/CompoundAssign, RisingFactorial, MulAddMul/MulSubMul (fused
x * y ± z * w), and the comparison family PartialOrdDouble/PartialOrdAbsDouble/
OrdDouble (compare a number against twice another without computing the double — the shape
of a round-to-nearest decision).gmp_format! and friends, with %Z, %Q, and %R conversions
rendering Integer, Rational, and Float values, plus GMP-compatible string conversions
to back them.Sum and Product (balanced_fold), improving both
accuracy and speed of long reductions.multi_crt and balanced variants), modular
division (ModDiv, mod_div_list), modular square roots (ModSqrt), Bell numbers (single
and vector forms), Landau's function, rising factorials, and completed Fibonacci and Lucas
sequences with improved subfactorials. A Kronecker symbol edge case was also fixed.mul_shr_round (a fused (x * y) >> k with rounding, via a Mulders short
product) and MulAddMul/MulSubMul for Natural and Integer, and AddMul/SubMul are
now faster than their unfused equivalents.mpfr_can_round_raw port with 32-bit limbs (a latent bug in MPFR itself
on 32-bit-limb builds): a carry absorbed by a truncated limb was misread as a binade change,
letting Float::can_round claim an undecidable rounding was decided.Rational GCD and extended GCD (in the lattice sense), rational reconstruction (recovering
p/q from its residue mod m), Dedekind sums, harmonic numbers, and height functions
(to_height, into_height, height_significant_bits).simplest_rational_in_interval now uses FLINT's algorithm, and the related
denominators-in-interval functions were redesigned around a mediant heap, making some of them
hundreds of times faster.AddMul and SubMul implementations, sequence utilities, and GMP-style string conversions.Sum, Product, and dot products (ports of mpfr_sum and
mpfr_dot, without the latter's abort on extreme exponents), add_mul/sub_mul (fused
multiply-add rounded once), mul_add_mul/mul_sub_mul (mpfr_fmma/fmms), and
Float-valued factorials.hypot, compound (with an upstream MPFR rounding bug found and
corrected in the port), positive_difference (mpfr_dim), min/max, remainders (rem,
IEEE remainder, and quotient-bit variants), the round-to-integer family including
fractional_part and integer/fraction decomposition, can_round, and subnormalize
(enabling faithful emulation of IEEE formats such as quad precision).Float/Rational variants throughout (fused operations, remainders, min/max,
positive_difference), treating the Rational operand exactly.Float generators for
testing.ToStringBase and additional string-conversion functions.f32/f64 functions in the primitive_float_* family, computed
exactly via Float and rounded once, including sums, products, and dot products of slices.increment/decrement semantics change listed above.Roots, modinv).serde (identical wire format,
cross-deserializable with num-bigint), rand (RandBigInt, RandomBits,
UniformBigInt/UniformBigUint, producing bit-identical value streams from identically
seeded RNGs), arbitrary, and quickcheck.DoubleEndedIterator for U32Digits, Mul for Sign, and overrides
of num_integer::Integer's default methods (div_mod_floor in one division, div_ceil,
gcd_lcm, extended_gcd_lcm, next/prev_multiple_of, dec/inc), with
Euclid/CheckedEuclid forwarded to Malachite's Euclidean-division operations.DOC-CONVENTIONS.md), plus refreshed front-page examples.With this release, Floats are no longer considered experimental! I've added
With this release, Floats are no longer considered experimental! I've added
In the process of porting MPFR functions to Malachite, I discovered several bugs in MPFR. I've reported them and they're being fixed.
What's next:
Reconstructed retroactively. The two big themes were Float elementary functions — the
exponential and power families, correctly rounded at any precision — and a complete rewrite of
Float-string interconversion.
Float's Display, Debug, and the other string conversions were rewritten on a port of
MPFR's get_str. Output became correctly rounded scientific decimal at every exponent (the
old implementation bailed out above |exponent| > 10000), with MPFR's precision-dependent
digit counts, so many outputs differ textually from 0.9.2.RationalSequence in malachite-base was renamed to FoerSequence (a sequence that is Finite
Or Eventually Repeating), freeing the old name from the misreading that it had something to
do with Rational.Float exponential family: exp, exp_x_minus_1, power_of_2, power_of_10, and
their _x_minus_1 companions, with Rational-argument versions and Float-valued outputs
for primitive inputs.Float power family: Float raised to Float, signed and unsigned integer powers, IEEE
powr, and roots — sqrt, cbrt, and nth roots (root_u, root_s) — including
Float-valued square roots, cube roots, and logarithms of unsigned integers.Float parsing (a port of set_str, bases 2 through 62), to_sci_string, and
serde support for Float, alongside the get_str rewrite above.f32/f64 emulation machinery
(primitive_float_*) in malachite-float.Euclidean division for primitive ints, Naturals, and Integers
This release advances Float development.
This release advances Float development.
Rationals and returning a Float result.Rem trait (and Mod and CeilingMod, just like Integers). We define x % y to be x - y * sign(x * y) * floor(|x/y|), though the implementaton is slightly faster than the naive one.This release adds functionality for taking the square root of Floats, and for taking the reciprocal square root of Floats (that is, raising them to th
This release adds functionality for taking the square root of Floats, and for taking the reciprocal square root of Floats (that is, raising them to the power of -1/2). It also adds several new constants that may be computed to arbitrary precision. Also, thanks to Dasaav-dsv for adding the as_limbs_asc function to Naturals, allowing users to take a reference to a Natural's limbs.
Breaking changes:
2026 will be a big year for Floats!
Primitive unsigned integers no longer implement these traits, which is a breaking change. (If you were using these for some reason, just use normal co…
Float::log_2_prec and Float::log_2_prec_round.Division of Floats by Floats and reciprocation of Floats now handle overflow and underflow correctly (same as MPFR)
I've rewritten integer multiplication a second time. The latest implementation is derived from Daniel Schultz's small-prime FFT multiplication impleme
I've rewritten integer multiplication a second time. The latest implementation is derived from Daniel Schultz's small-prime FFT multiplication implementation in FLINT. It's considerably faster than before, though still a bit slower than GMP's implementation. Malachite now depends on the wide crate for SIMD; once wide 0.8.0 is released, I should be able to improve Malachite's multiplication performance further still. I'm going to hold off making concrete performance claims until then.
Unfortunately, I've discovered that, at least on my machine, Malachite is considerably slower when built using no_std (though still pretty fast!); the main culprit is the libm::fma function, which is considerably slower than the std-only equivalent mul_add. Since I want Malachite to have the best performance possible by default, I've decided to make no_std opt-in. Malachite will build with an std feature by default, and to build it with no_std you will need to disable default features.
Thanks to Will Youmans for implementing some functions around perfect powers, and to all the other contributors to this release.
Next I will focus my attention back on Floats, which have been neglected.
Fixed a rare panic during an extended GCD computation.
Fixed a rare panic during an extended GCD computation.
To resolve this, the Malachite functions were renamed to get_digit or get_limb, depending on the iterator. This is a breaking change.
get function on the Itertools traits and various get functions on some iterators in Malachite. To resolve this, the Malachite functions were renamed to get_digit or get_limb, depending on the iterator. This is a breaking change.syn crate in malachite-bigint.added primitive root computation for a prime number of primitive int type
I am reinstating some import changes that I reverted in 0.4.x, since they were breaking changes there. I'm also changing the constants in the platform…
I am reinstating some import changes that I reverted in 0.4.x, since they were breaking changes there. I'm also changing the constants in the platform module to pub(crate), since I only want the types to be visible.
I recently changed the way the malachite crate re-exported its sub-crate items, in this commit. This was a breaking change and caused some failures in…
I recently changed the way the malachite crate re-exported its sub-crate items, in this commit. This was a breaking change and caused some failures in downstream crates, so I'm reverting it in this release and in a few hours I will re-release it in v0.5.0.
Tweaked the documentation just a bit more. Should be good now.
Tweaked the documentation just a bit more. Should be good now.
Some of the documentation for the top-level malachite crate didn't work as intended in the v0.4.19 release, so I'm releasing again.
Some of the documentation for the top-level malachite crate didn't work as intended in the v0.4.19 release, so I'm releasing again.
This is a small release to address the following issues:
This is a small release to address the following issues:
https://github.com/mhogrefe/malachite/issues/39 https://github.com/mhogrefe/malachite/issues/56 https://github.com/mhogrefe/malachite/issues/57
Also, I've made some changes to how the main malachite crate re-exports the sub-crate items. The items from malachite-base are now under a base module, and the platform module from malachite-nz, containing items like Limb, is now exported.
My attempt at publishing 0.4.17 failed, and I am forced to increment the version to try again.
My attempt at publishing 0.4.17 failed, and I am forced to increment the version to try again.
I wasn't planning on releasing today, but after pishleback found a multiplication bug I wanted to push out a fix ASAP. I also released the partially-c
I wasn't planning on releasing today, but after pishleback found a multiplication bug I wanted to push out a fix ASAP. I also released the partially-completed work that I've been doing on Malachite in the last few months.
IsPrime trait, you can write 5509785649208481923u64.is_prime(), which evaluates to true. I tested this function on hundreds of thousands of random u64s, and found that it completed in less than 1.5 milliseconds for every u64, whereas a naive approach based on trial division could take up to 1 second for a single u64. I will eventually implement IsPrime for u128 and Natural as well.Float now creates a Float with the minimum precision necessary to represent the original value. Previously, some less obvious precision choices were made. If you want some precision other than the default, you can always use Float::from_unsigned_prec, Float::from_unsigned_prec_round, etc.AbsDiff implementation for Rational.This release adds efficient Float division, as well as efficient multiplication of Floats by Rationals, division of Floats by Rationals, and division
This release adds efficient Float division, as well as efficient multiplication of Floats by Rationals, division of Floats by Rationals, and division of Rationals by Floats. Conversion from Rationals to Floats is also more efficient, because it now uses Float division. The Reciprocal trait, and related functions, are also now implemented for Floats. Taking the reciprocal with these functions is slightly faster than computing 1/x using the division functions.
Now that the four basic arithmetic functions are supported for Floats, I'm able to move on to more interesting functions. Apart from the square root function and efficient string conversion functions, the functions that have yet to be implemented have simpler implementations in MPFR than the functions that have already been translated for Malachite, so you can generally expect the development of Floats to speed up a bit.
Other changes include
Float::from_natural_min_prec and related functions, which convert from Naturals or Integers to Floats using the minimum precision necessary.Float::from_natural_prec_round_ref is now smarter: if converting from a large Natural with low precision, only the few most-significant bits that are needed are copied.Float functions are now tested against the rug library.Natural, Integer, and Rational generators are added.Float constants are added (not actually constants, since you need to specify a precision and optionally a rounding mode). They are the prime constant and the Thue-Morse constant. They're not very useful; I just added them because I like constants. More useful constants are coming soon!This is a small release. Its purpose is mostly to include this pull request, which specifies the minimum supported Rust version. There is a more subst
This is a small release. Its purpose is mostly to include this pull request, which specifies the minimum supported Rust version. There is a more substantial release coming in the next weeks, which will contain efficient implementations of Float division and reciprocation.
This release includes
AbsDiff for IntegerEqAbs between Rationals and other numeric typesSum and Product implementations on Rationalmalachite-base. This is purely proactive; no bugs have been foundAdded multiplication and squaring for Floats. Implementations for multiplying a Float by a Rational were also added, but the implementations are naive
Added multiplication and squaring for Floats. Implementations for multiplying a Float by a Rational were also added, but the implementations are naive; to use the same technique as MPFR we need Float division, which Malachite can't do yet. But that's what I'll be working on next!
Another performance improvement from florian1345, this time for multiplication.
Thanks to florian1345 for some addition and subtraction optimizations that significantly improve performance on a Windows target.
Updated PyO3 conversion code to use the new PyO3 v0.21 API (by Antonio Mamić).
Fixes a PyO3 dependency issue. Incorporates feedback from some new Clippy lints. Adds AbsDiff and AbsDiffAssign implementations for Natural.
Fixes a PyO3 dependency issue. Incorporates feedback from some new Clippy lints. Adds AbsDiff and AbsDiffAssign implementations for Natural.
This release makes the pyo3-build-config dependency optional. Thanks to Ihor Ranchynskyi for surfacing this issue and Antonio Mamić for fixing it.
This release makes the pyo3-build-config dependency optional. Thanks to Ihor Ranchynskyi for surfacing this issue and
Antonio Mamić for fixing it.
This is a fairly minor release. I've made significant progress on Float multiplication and squaring, but that work isn't included here. Here's what is
This is a fairly minor release. I've made significant progress on Float multiplication and squaring, but that work isn't included here. Here's what is:
Shl, ShlAssign, Shr, and ShrAssign implementations for FloatsEqAbs implementationsAdded more copyright notices, including giving credit to individual authors of GMP, FLINT, and MPFR whenever their code was translated for inclusion i
Added more copyright notices, including giving credit to individual authors of GMP, FLINT, and MPFR whenever their code was translated for inclusion into Malachite.
Implemented Float addition and subtraction. The code is derived from MPFR and is highly optimized (which is one reason it took so long). The is functi
Implemented Float addition and subtraction. The code is derived from MPFR and is highly optimized (which is one reason it took so long). The is functionality for providing a rounding mode, an output precision, or both. The defaults are RoundingMode::Nearest and the maximum precision of the inputs. There are also implementations for adding and subtracting a Float and a Rational; any numeric type apart from Rational can be losslessly converted to Float, so there are no implementations for e.g. Float + Natural, though in principle such an implementation could still be worthwhile since it would save some memory usage.
Next up: Float multiplication, squaring, and bit shifting (that is, multiplication and division by powers of 2).
Malachite is now no_std, unless the random, test_build, or bin_build features are enabled. Thanks to shekohex for initiating this work!
Various minor improvements.
no_std, unless the random, test_build, or bin_build features are enabled. Thanks to shekohex for initiating this work!twos_complement_limb_count method has been added to Integer.malachite meta-crate did not have a 32_bit_limbs feature to propagate to its sub-crates. Now it does, along with a random feature.Integer now implements CheckedDiv. Natural now implements PartialOrdAbs for primitive floats. I added some tests for the AbsDiff trait in malachite-base in preparation for implementing it for Natural, Integer, and Rational.Float generators were producing floats whose exponents were off by 1. That has been fixed.Most of my work in the last few months has been implementing addition and subtraction for Floats. This is a lot less trivial than it sounds, because I'm translating MPFR's code, which is very optimized and has many special cases for addition and subtraction. Counterintuitively, implementing more advanced functions will take less time. I'm wrapping up the addition and subtraction work, so that will be released soon.
New release to fix incorrect dependencies.
New release to fix incorrect dependencies.
Fixed the multiplication bug described in https://github.com/mhogrefe/malachite/issues/29.
Natural (and by extension, Integer and Rational) parsing according to the suggestion in https://github.com/mhogrefe/malachite/issues/27.random feature; see https://github.com/mhogrefe/malachite/issues/26.CheckedDiv implemented for Natural. It was already implemented for Rational, and soon I'll add an Integer implementation as well.This release adds several const functions that can be used to initialize Naturals, Integers, and Rationals:
This release adds several const functions that can be used to initialize Naturals, Integers, and Rationals:
Natural::const_from_unsignedInteger::const_from_unsignedInteger::const_from_signedRational::const_from_unsignedRational::const_from_signedRational::const_from_unsignedsRational::const_from_signedsThe last two functions construct a Rational from a numerator and denominator. They use a const GCD function to reduce their arguments.
I'm continuing to work on a larger release that will include Float addition and subtraction, among other things.
This is a small release to fix rustdocs for the malachite crate. Thanks to konstin for the fix.
This is a small release to fix rustdocs for the malachite crate. Thanks to konstin for the fix.
Work for 0.4.2 is well underway. It will include addition and subtraction for Floats, and several ergonomic improvements to other parts of Malachite.
I created the malachite-float crate and the Float type. Floats are currently very incomplete; hardly any arithmetic is implemented yet. However, there
malachite-float crate and the Float type. Floats are currently very incomplete; hardly any arithmetic is implemented yet. However, there is a full complement of functions for comparison and conversion between between Floats and other numeric types. Those functions are extensively tested and documented. But note that the current functions for converting to and from strings are not stable; eventually I will implement them in a way that matches MPFR's behavior, but that requires division and logarithms, which are not yet implemented.RoundingMode now also return an Ordering indicating whether the rounded value is less than, greater than, or equal to the notional exact value. If you currently use these functions (for example, rounding_from or shr_round), you may need to append an .0 after the function call to extract the rounded value and ignore the Ordering.One, Two, and NegativeOne traits for NonZero* types.CheckedDiv for Rationals. In the next release I'll implement it for Naturals and Integers as well.Iverson trait for the Iverson bracket, which converts booleans to numbers. I replaced this with From<bool> everywhere once I realized that it was already implemented for primitive integers.LimbIterator behaved incorrectly (Issue 18). Although it was thoroughly tested like all of Malachite's features, I didn't realize what the correct behavior should have been when I originally wrote the tests. Thanks to qingshi163 for catching this.Natural::from_string_base did not always fail when it should have (Issue 20). There was a small gap in the testing; from_string_base's behavior on valid strings was well-tested, but its behavior on invalid strings was not. Thanks to qingshi163 for catching this one as well.added/completed small prime generation, primorials, and binomial coefficients. As usual, the same algorithms are used as in GMP.
added/completed small prime generation, primorials, and binomial coefficients. As usual, the same algorithms are used as in GMP.
This release is mostly to fix https://github.com/mhogrefe/malachite/issues/6.
This release is mostly to fix https://github.com/mhogrefe/malachite/issues/6.
There has also been some work on small prime generation, primorials, and binomial coefficients, which I will complete in the next release.
Added the malachite meta-crate, for easier importing
malachite meta-crate, for easier importingCheckedFrom by TryFrom and removed fallible From implementationsAdded the factorial, double factorial, multifactorial, and subfactorial functions. All but the subfactorial have fast implementations based on GMP's i
Added the factorial, double factorial, multifactorial, and subfactorial functions. All but the subfactorial have fast implementations based on GMP's implementations. The subfactorial just uses the recurrence relation !n = n * !(n - 1) + (-1)^n until I can come up with something faster.
Added Legendre, Jacobi, and Kronecker symbols. The implementations for Naturals and Integers use a variation of Lehmer's GCD algorithm.
Added Legendre, Jacobi, and Kronecker symbols. The implementations for Naturals and Integers use a variation of Lehmer's GCD algorithm.
Also added exhaustive and random generators for Rationals with a specified denominator and in a specified range.
Modular inversion for primitive integers and Naturals is now implemented. It's a straightforward application of extended GCD, but can be made a little
Modular inversion for primitive integers and Naturals is now implemented. It's a straightforward application of extended GCD, but can be made a little faster since only one cofactor is needed. There's also a new trait for inversion modulo a power of 2, ModPowerOf2Inverse. The Natural implementation uses Newton's method.
I also added iterators that generate compositions, which will be useful for exhaustively generating ordered Vecs.
Added extended GCD, using a variation of Lehmer's GCD algorithm for Naturals and Integers.
Added extended GCD, using a variation of Lehmer's GCD algorithm for Naturals and Integers.
Clean up documentation and cross-references.
Clean up documentation and cross-references.
Fix KaTeX in malachite-base rustdocs. Normally this would be too minor for a separate release, but I want to get this change to the public rustdocs.
Fix KaTeX in malachite-base rustdocs. Normally this would be too minor for a separate release, but I want to get this change to the public rustdocs.
The initial public release of Malachite. Naturals, Integers, and Rationals are ready to use.
Full Changelog: https://github.com/mhogrefe/malachite/commits/v0.2.0
The initial public release of Malachite. Naturals, Integers, and Rationals are ready to use.
One column per quarter.