malachite_base/num/arithmetic/

traits.rs

// Copyright © 2026 Mikhail Hogrefe
//
// This file is part of Malachite.
//
// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.

use crate::num::basic::traits::Two;
use crate::rounding_modes::RoundingMode;
use core::cmp::Ordering;

/// Takes the absolute value of a number. Assumes that the number has a representable absolute
/// value.
pub trait Abs {
    type Output;

    fn abs(self) -> Self::Output;
}

/// Replaces a number with its absolute value. Assumes that the number has a representable absolute
/// value.
pub trait AbsAssign {
    fn abs_assign(&mut self);
}

/// Computes the squared absolute value of a number.
///
/// For a real number this is just its square, but for a complex number it is the sum of the squares
/// of its real and imaginary parts. In both cases it equals $|x|^2$; for Gaussian integers and
/// Gaussian rationals this quantity is also called the norm.
pub trait AbsSquared {
    type Output;

    fn abs_squared(self) -> Self::Output;
}

/// Replaces a number with its squared absolute value.
///
/// For a real number this is just squaring in place. For a complex number the result is the purely
/// real value $|x|^2$, embedded in the same type.
pub trait AbsSquaredAssign {
    fn abs_squared_assign(&mut self);
}

/// Computes the complex conjugate of a number.
///
/// For a complex number the sign of the imaginary part is flipped. For a real number, which is its
/// own conjugate, this is the identity; the trivial implementations let generic code use
/// conjugation uniformly, for example when forming Hermitian products.
pub trait Conjugate {
    type Output;

    fn conjugate(self) -> Self::Output;
}

/// Replaces a number with its complex conjugate.
///
/// For a complex number the sign of the imaginary part is flipped. For a real number this does
/// nothing.
pub trait ConjugateAssign {
    fn conjugate_assign(&mut self);
}

/// Multiplies a number by $i$, the imaginary unit.
///
/// For a complex number $a + bi$ this is $-b + ai$, a counterclockwise quarter turn. No type in
/// this crate implements this trait; it exists for complex types downstream, like Gaussian
/// integers.
pub trait MulI {
    type Output;

    fn mul_i(self) -> Self::Output;
}

/// Replaces a number with its product with $i$, the imaginary unit.
///
/// For a complex number $a + bi$ the result is $-b + ai$, a counterclockwise quarter turn. No type
/// in this crate implements this trait; it exists for complex types downstream, like Gaussian
/// integers.
pub trait MulIAssign {
    fn mul_i_assign(&mut self);
}

/// Divides a number by $i$, the imaginary unit.
///
/// For a complex number $a + bi$ this is $b - ai$, a clockwise quarter turn. No type in this crate
/// implements this trait; it exists for complex types downstream, like Gaussian integers.
pub trait DivI {
    type Output;

    fn div_i(self) -> Self::Output;
}

/// Replaces a number with its quotient by $i$, the imaginary unit.
///
/// For a complex number $a + bi$ the result is $b - ai$, a clockwise quarter turn. No type in this
/// crate implements this trait; it exists for complex types downstream, like Gaussian integers.
pub trait DivIAssign {
    fn div_i_assign(&mut self);
}

/// Multiplies a number by $i^k$, a power of the imaginary unit.
///
/// Only $k$ modulo 4 matters: $i^0 = 1$, $i^1 = i$, $i^2 = -1$, and $i^3 = -i$, so the result is
/// the number itself, a counterclockwise quarter turn, a half turn, or a clockwise quarter turn.
/// Since $i^{-k} = i^{3k}$, a negative power is a matter of tripling the exponent. No type in this
/// crate implements this trait; it exists for complex types downstream, like Gaussian integers.
pub trait MulIPow {
    type Output;

    fn mul_i_pow(self, k: u64) -> Self::Output;
}

/// Replaces a number with its product with $i^k$, a power of the imaginary unit.
///
/// Only $k$ modulo 4 matters: $i^0 = 1$, $i^1 = i$, $i^2 = -1$, and $i^3 = -i$, so the result is
/// the number itself, a counterclockwise quarter turn, a half turn, or a clockwise quarter turn.
/// Since $i^{-k} = i^{3k}$, a negative power is a matter of tripling the exponent. No type in this
/// crate implements this trait; it exists for complex types downstream, like Gaussian integers.
pub trait MulIPowAssign {
    fn mul_i_pow_assign(&mut self, k: u64);
}

/// Determines whether a number is a unit of its ring, meaning that it has a multiplicative inverse
/// in the same ring.
///
/// Which elements these are depends on the ring: the only unit of $\mathbb{N}$ is 1, the units of
/// $\mathbb{Z}$ are $\pm 1$, the Gaussian integers have four, $\pm 1$ and $\pm i$, and in a field
/// every nonzero element is a unit.
///
/// The implementations for the primitive integers follow suit, and the ones for the primitive
/// floats count every finite nonzero value.
pub trait IsUnit {
    fn is_unit(&self) -> bool;
}

/// Finds the power of $i$ that brings a number into canonical Gaussian-unit form.
///
/// The Gaussian units are $1$, $i$, $-1$, and $-i$: the units of the Gaussian integers. Multiplying
/// a nonzero complex number by them gives its four Gaussian associates, $x$, $ix$, $-x$, and $-ix$,
/// and the canonical one is the one whose argument lies in $(-\pi/4, \pi/4]$, meaning that its real
/// part $a$ is positive and its imaginary part $b$ satisfies $-a < b \leq a$. This function returns
/// the $k \in \\{0, 1, 2, 3\\}$ such that $x i^k$ is canonical, and 0 for zero;
/// [`CanonicalizeGaussianUnit`] does the multiplication.
///
/// A real number has only the two Gaussian associates $\pm x$ to choose between, so the answer
/// there is 0 for a nonnegative number and 2 for a negative one, $i^2$ being $-1$. That is what the
/// primitive implementations return.
///
/// This is the canonical form of [`CanonicalizeUnit`] only when the ring's units are Gaussian
/// units: for the integers, whose units are $\pm 1$, and the Gaussian integers, whose units are
/// $\pm 1$ and $\pm i$. In a field every nonzero element is a unit, so the canonical associate of a
/// nonzero rational or Gaussian rational is 1, which no power of $i$ reaches.
pub trait CanonicalUnitIPow {
    fn canonical_unit_i_pow(&self) -> u64;
}

/// Brings a number into canonical unit form: replaces it with its canonical associate.
///
/// The associates of a number are the numbers it becomes when multiplied by a unit of its ring, and
/// the canonical associate is the one chosen to represent them all. Each implementation documents
/// its choice. An unsigned number is already canonical, so the unsigned implementations are the
/// identity; the units of the integers are $\pm 1$, so the signed implementations return the
/// absolute value; the units of the Gaussian integers are the powers of $i$, and the canonical
/// associate is the one whose argument lies in $(-\pi/4, \pi/4]$ (see [`CanonicalUnitIPow`]). In a
/// field every nonzero element is a unit, so the canonical associate of a nonzero rational number,
/// a nonzero Gaussian rational, or a finite nonzero floating-point number is 1; zero, the
/// infinities, and NaN are not units, and keep their absolute value. For a polynomial over the
/// integers it is the associate with a positive leading coefficient, and over the rationals it is
/// the monic one.
///
/// For the canonical form under the Gaussian units $\pm 1$ and $\pm i$ alone, which rotates a
/// number by a power of $i$ rather than collapsing a field's units to 1, see
/// [`CanonicalizeGaussianUnit`].
pub trait CanonicalizeUnit {
    type Output;

    fn canonicalize_unit(self) -> Self::Output;
}

/// Replaces a number with its canonical unit form: its canonical associate.
///
/// This is the in-place form of [`CanonicalizeUnit`], and the same per-type behaviour applies.
pub trait CanonicalizeUnitAssign {
    fn canonicalize_unit_assign(&mut self);
}

/// Brings a number into canonical Gaussian-unit form: multiplies it by the power of $i$ that
/// [`CanonicalUnitIPow`] finds.
///
/// The result is the Gaussian associate whose argument lies in $(-\pi/4, \pi/4]$. For a real number
/// that is its absolute value, and zero is its own canonical form. This differs from
/// [`CanonicalizeUnit`] exactly in a field, where every nonzero element is a unit and canonicalizes
/// to 1; here a nonzero number keeps its magnitude and is only rotated by a quarter turn or
/// negated.
pub trait CanonicalizeGaussianUnit {
    type Output;

    fn canonicalize_gaussian_unit(self) -> Self::Output;
}

/// Replaces a number with its canonical Gaussian-unit form.
///
/// This is the in-place form of [`CanonicalizeGaussianUnit`].
pub trait CanonicalizeGaussianUnitAssign {
    fn canonicalize_gaussian_unit_assign(&mut self);
}

/// Brings a value into canonical sign form: negates it if it is negative, so that the result is
/// non-negative.
///
/// A value and its negation are the same up to multiplication by $\pm 1$, and this picks one of the
/// two to represent both. What "negative" means is up to the type: a vector is negative when its
/// pivot, its first nonzero element, is, so a vector of zeros is already canonical.
pub trait CanonicalizeSign {
    type Output;

    fn canonicalize_sign(self) -> Self::Output;
}

/// Replaces a value with its canonical sign form.
///
/// This is the in-place form of [`CanonicalizeSign`].
pub trait CanonicalizeSignAssign {
    fn canonicalize_sign_assign(&mut self);
}

/// Takes the absolute value of a number and converts to the unsigned equivalent.
pub trait UnsignedAbs {
    type Output;

    fn unsigned_abs(self) -> Self::Output;
}

/// Replaces every entry of a value, such as every element of a vector, by its absolute value.
///
/// This is distinct from [`Abs`], which for a vector would be its Euclidean length.
pub trait EntrywiseAbs {
    type Output;

    fn entrywise_abs(self) -> Self::Output;
}

/// Replaces every entry of a value, such as every element of a vector, by its absolute value, in
/// place.
pub trait EntrywiseAbsAssign {
    fn entrywise_abs_assign(&mut self);
}

/// Replaces every entry of a value, such as every element of a vector, by its absolute value,
/// converting to the unsigned equivalent, as [`UnsignedAbs`] does for a single number.
pub trait EntrywiseUnsignedAbs {
    type Output;

    fn entrywise_unsigned_abs(self) -> Self::Output;
}

/// Takes the entrywise maximum of two values, such as two vectors of the same dimension: the value
/// whose every entry is the larger of the corresponding entries.
pub trait EntrywiseMax<RHS = Self> {
    type Output;

    fn entrywise_max(self, other: RHS) -> Self::Output;
}

/// Replaces a value, such as a vector, by its entrywise maximum with another: every entry becomes
/// the larger of itself and the corresponding entry of the other value.
pub trait EntrywiseMaxAssign<RHS = Self> {
    fn entrywise_max_assign(&mut self, other: RHS);
}

/// Takes the entrywise minimum of two values, such as two vectors of the same dimension: the value
/// whose every entry is the smaller of the corresponding entries.
pub trait EntrywiseMin<RHS = Self> {
    type Output;

    fn entrywise_min(self, other: RHS) -> Self::Output;
}

/// Replaces a value, such as a vector, by its entrywise minimum with another: every entry becomes
/// the smaller of itself and the corresponding entry of the other value.
pub trait EntrywiseMinAssign<RHS = Self> {
    fn entrywise_min_assign(&mut self, other: RHS);
}

/// Divides every entry of a value, such as a vector, by a scalar, rounding each quotient according
/// to a specified rounding mode.
///
/// Unlike [`DivRound`], no [`Ordering`] is returned, since different entries may be rounded in
/// different directions.
pub trait EntrywiseDivRound<RHS> {
    type Output;

    fn entrywise_div_round(self, other: RHS, rm: RoundingMode) -> Self::Output;
}

/// Divides every entry of a value, such as a vector, by a scalar in place, rounding each quotient
/// according to a specified rounding mode.
///
/// Unlike [`DivRoundAssign`], no [`Ordering`] is returned, since different entries may be rounded
/// in different directions.
pub trait EntrywiseDivRoundAssign<RHS> {
    fn entrywise_div_round_assign(&mut self, other: RHS, rm: RoundingMode);
}

/// Left-shifts every entry of a value, such as a vector (multiplying it by a power of 2), rounding
/// each entry according to a specified rounding mode.
///
/// Unlike [`ShlRound`], no [`Ordering`] is returned, since different entries may be rounded in
/// different directions. Rounding might only be necessary if `other` is negative.
pub trait EntrywiseShlRound<RHS> {
    type Output;

    fn entrywise_shl_round(self, other: RHS, rm: RoundingMode) -> Self::Output;
}

/// Left-shifts every entry of a value, such as a vector (multiplying it by a power of 2), in place,
/// rounding each entry according to a specified rounding mode.
///
/// Unlike [`ShlRoundAssign`], no [`Ordering`] is returned, since different entries may be rounded
/// in different directions. Rounding might only be necessary if `other` is negative.
pub trait EntrywiseShlRoundAssign<RHS> {
    fn entrywise_shl_round_assign(&mut self, other: RHS, rm: RoundingMode);
}

/// Right-shifts every entry of a value, such as a vector (dividing it by a power of 2), rounding
/// each entry according to a specified rounding mode.
///
/// Unlike [`ShrRound`], no [`Ordering`] is returned, since different entries may be rounded in
/// different directions. Rounding might only be necessary if `other` is positive.
pub trait EntrywiseShrRound<RHS> {
    type Output;

    fn entrywise_shr_round(self, other: RHS, rm: RoundingMode) -> Self::Output;
}

/// Right-shifts every entry of a value, such as a vector (dividing it by a power of 2), in place,
/// rounding each entry according to a specified rounding mode.
///
/// Unlike [`ShrRoundAssign`], no [`Ordering`] is returned, since different entries may be rounded
/// in different directions. Rounding might only be necessary if `other` is positive.
pub trait EntrywiseShrRoundAssign<RHS> {
    fn entrywise_shr_round_assign(&mut self, other: RHS, rm: RoundingMode);
}

/// Subtracts two numbers and takes the absolute value of the difference.
pub trait AbsDiff<RHS = Self> {
    type Output;

    fn abs_diff(self, other: RHS) -> Self::Output;
}

/// Replaces a number with the absolute value of its difference with another number.
pub trait AbsDiffAssign<RHS = Self> {
    fn abs_diff_assign(&mut self, other: RHS);
}

/// Adds a number and the product of two other numbers.
///
/// Depending on the implementing type, the fused operation may compute the same value as the
/// unfused `self + y * z` more efficiently; or, for types with rounding, it may compute a *more
/// accurate* value -- the product enters the addition exactly, with a single rounding at the end --
/// but *less* efficiently, since the exact product must be computed in full. See each
/// implementation's documentation for which contract it provides.
pub trait AddMul<Y = Self, Z = Self> {
    type Output;

    fn add_mul(self, y: Y, z: Z) -> Self::Output;
}

/// Adds a number and the product of two other numbers, in place.
///
/// Depending on the implementing type, the fused operation may compute the same value as the
/// unfused `*self + y * z` more efficiently; or, for types with rounding, it may compute a *more
/// accurate* value -- the product enters the addition exactly, with a single rounding at the end --
/// but *less* efficiently, since the exact product must be computed in full. See each
/// implementation's documentation for which contract it provides.
pub trait AddMulAssign<Y = Self, Z = Self> {
    fn add_mul_assign(&mut self, y: Y, z: Z);
}

/// Adds a number and the product of two other numbers, shifted left by a number of bits: $x +
/// yz2^k$.
pub trait AddMulShl<Y = Self, Z = Self> {
    type Output;

    fn add_mul_shl(self, y: Y, z: Z, bits: u64) -> Self::Output;
}

/// Adds the product of two numbers, shifted left by a number of bits, to a number in place: $x
/// \gets x + yz2^k$.
pub trait AddMulShlAssign<Y = Self, Z = Self> {
    fn add_mul_shl_assign(&mut self, y: Y, z: Z, bits: u64);
}

/// Adds the products of two pairs of numbers.
pub trait MulAddMul<Y = Self, Z = Self, W = Self> {
    type Output;

    fn mul_add_mul(self, y: Y, z: Z, w: W) -> Self::Output;
}

/// Adds the products of two pairs of numbers, in place.
pub trait MulAddMulAssign<Y = Self, Z = Self, W = Self> {
    fn mul_add_mul_assign(&mut self, y: Y, z: Z, w: W);
}

/// Multiplies two numbers and right-shifts the product (divides it by a power of 2), rounding the
/// result according to a specified rounding mode. An [`Ordering`] is also returned, indicating
/// whether the returned value is less than, equal to, or greater than the exact value.
///
/// The product is computed exactly, as if at unlimited width; only the final shifted result must be
/// representable.
pub trait MulShrRound<RHS = Self, B = u64> {
    type Output;

    fn mul_shr_round(self, other: RHS, bits: B, rm: RoundingMode) -> (Self::Output, Ordering);
}

/// Multiplies two numbers and right-shifts the product (divides it by a power of 2) in place,
/// rounding the result according to a specified rounding mode. An [`Ordering`] is returned,
/// indicating whether the assigned value is less than, equal to, or greater than the exact value.
///
/// The product is computed exactly, as if at unlimited width; only the final shifted result must be
/// representable.
pub trait MulShrRoundAssign<RHS = Self, B = u64> {
    fn mul_shr_round_assign(&mut self, other: RHS, bits: B, rm: RoundingMode) -> Ordering;
}

/// Subtracts the product of one pair of numbers from the product of another.
pub trait MulSubMul<Y = Self, Z = Self, W = Self> {
    type Output;

    fn mul_sub_mul(self, y: Y, z: Z, w: W) -> Self::Output;
}

/// Subtracts the product of one pair of numbers from the product of another, in place.
pub trait MulSubMulAssign<Y = Self, Z = Self, W = Self> {
    fn mul_sub_mul_assign(&mut self, y: Y, z: Z, w: W);
}

/// Calculates the AGM (arithmetic-geometric mean) of two numbers.
pub trait Agm<RHS = Self> {
    type Output;

    fn agm(self, other: RHS) -> Self::Output;
}

/// Replaces a number with the AGM (arithmetic-geometric mean) of it and another number.
pub trait AgmAssign<RHS = Self> {
    fn agm_assign(&mut self, other: RHS);
}

/// Calculates the hypotenuse of two numbers, $\sqrt{x^2+y^2}$.
pub trait Hypot<RHS = Self> {
    type Output;

    fn hypot(self, other: RHS) -> Self::Output;
}

/// Replaces a number with the hypotenuse of it and another number.
pub trait HypotAssign<RHS = Self> {
    fn hypot_assign(&mut self, other: RHS);
}

/// Calculates the compound function $(1+x)^n$ of a number $x$.
pub trait Compound<N> {
    type Output;

    fn compound(self, n: N) -> Self::Output;
}

/// Replaces a number $x$ with the compound function $(1+x)^n$.
pub trait CompoundAssign<N> {
    fn compound_assign(&mut self, n: N);
}

/// Left-shifts a number (multiplies it by a power of 2), returning `None` if the result is not
/// representable.
pub trait ArithmeticCheckedShl<RHS> {
    type Output;

    fn arithmetic_checked_shl(self, other: RHS) -> Option<Self::Output>;
}

/// Right-shifts a number (divides it by a power of 2), returning `None` if the result is not
/// representable.
pub trait ArithmeticCheckedShr<RHS> {
    type Output;

    fn arithmetic_checked_shr(self, other: RHS) -> Option<Self::Output>;
}

/// Computes the average (arithmetic mean) of two numbers, rounding to the nearest integer. Two-way
/// ties are broken by rounding to the even integer.
///
/// The average is computed without overflow: the result is always exact or within a half of the
/// exact value, so it always fits in the same type as the inputs.
pub trait Average<RHS = Self> {
    type Output;

    fn average(self, other: RHS) -> Self::Output;
}

/// Computes the average (arithmetic mean) of two numbers, rounding to the nearest integer and
/// replacing the first number with it. Two-way ties are broken by rounding to the even integer.
///
/// The average is computed without overflow: the result is always exact or within a half of the
/// exact value, so it always fits in the same type as the inputs.
pub trait AverageAssign<RHS = Self> {
    fn average_assign(&mut self, other: RHS);
}

/// Computes the average (arithmetic mean) of two numbers and rounds according to a specified
/// rounding mode. An [`Ordering`] is also returned, indicating whether the returned value is less
/// than, equal to, or greater than the exact value.
///
/// The average is computed without overflow: the result is always exact or within a half of the
/// exact value, so it always fits in the same type as the inputs.
pub trait AverageRound<RHS = Self> {
    type Output;

    fn average_round(self, other: RHS, rm: RoundingMode) -> (Self::Output, Ordering);
}

/// Computes the average (arithmetic mean) of two numbers, rounding according to a specified
/// rounding mode and replacing the first number with it. An [`Ordering`] is returned, indicating
/// whether the assigned value is less than, equal to, or greater than the exact value.
///
/// The average is computed without overflow: the result is always exact or within a half of the
/// exact value, so it always fits in the same type as the inputs.
pub trait AverageRoundAssign<RHS = Self> {
    fn average_round_assign(&mut self, other: RHS, rm: RoundingMode) -> Ordering;
}

pub trait BinomialCoefficient<T = Self> {
    fn binomial_coefficient(n: T, k: T) -> Self;
}

pub trait CheckedBinomialCoefficient<T = Self>: Sized {
    fn checked_binomial_coefficient(n: T, k: T) -> Option<Self>;
}

/// Takes the ceiling of a number.
pub trait Ceiling {
    type Output;

    fn ceiling(self) -> Self::Output;
}

/// Replaces a number with its ceiling.
pub trait CeilingAssign {
    fn ceiling_assign(&mut self);
}

/// Takes the absolute valie of a number, returning `None` if the result is not representable.
pub trait CheckedAbs {
    type Output;

    fn checked_abs(self) -> Option<Self::Output>;
}

/// Adds two numbers, returning `None` if the result is not representable.
pub trait CheckedAdd<RHS = Self> {
    type Output;

    fn checked_add(self, other: RHS) -> Option<Self::Output>;
}

/// Adds a number and the product of two other numbers, returning `None` if the result is not
/// representable.
pub trait CheckedAddMul<Y = Self, Z = Self> {
    type Output;

    fn checked_add_mul(self, y: Y, z: Z) -> Option<Self::Output>;
}

/// Adds the products of two pairs of numbers, returning `None` if the result is not representable.
pub trait CheckedMulAddMul<Y = Self, Z = Self, W = Self> {
    type Output;

    fn checked_mul_add_mul(self, y: Y, z: Z, w: W) -> Option<Self::Output>;
}

/// Subtracts the product of one pair of numbers from the product of another, returning `None` if
/// the result is not representable.
pub trait CheckedMulSubMul<Y = Self, Z = Self, W = Self> {
    type Output;

    fn checked_mul_sub_mul(self, y: Y, z: Z, w: W) -> Option<Self::Output>;
}

/// Divides two numbers, returning `None` if the result is not representable.
pub trait CheckedDiv<RHS = Self> {
    type Output;

    fn checked_div(self, other: RHS) -> Option<Self::Output>;
}

/// Multiplies two numbers, returning `None` if the result is not representable.
pub trait CheckedMul<RHS = Self> {
    type Output;

    fn checked_mul(self, other: RHS) -> Option<Self::Output>;
}

/// Negates a number, returning `None` if the result is not representable.
pub trait CheckedNeg {
    type Output;

    fn checked_neg(self) -> Option<Self::Output>;
}

/// Finds the smallest integer power of 2 greater than or equal to a number, returning `None` if the
/// result is not representable.
pub trait CheckedNextPowerOf2 {
    type Output;

    fn checked_next_power_of_2(self) -> Option<Self::Output>;
}

/// Raises a number to a power, returning `None` if the result is not representable.
pub trait CheckedPow<RHS> {
    type Output;

    fn checked_pow(self, exp: RHS) -> Option<Self::Output>;
}

/// Squares a number, returning `None` if the result is not representable.
pub trait CheckedSquare {
    type Output;

    fn checked_square(self) -> Option<Self::Output>;
}

/// Subtracts two numbers, returning `None` if the result is not representable.
pub trait CheckedSub<RHS = Self> {
    type Output;

    fn checked_sub(self, other: RHS) -> Option<Self::Output>;
}

/// Subtracts a number by the product of two other numbers, returning `None` if the result is not
/// representable.
pub trait CheckedSubMul<Y = Self, Z = Self> {
    type Output;

    fn checked_sub_mul(self, y: Y, z: Z) -> Option<Self::Output>;
}

/// Determines whether two numbers are coprime.
pub trait CoprimeWith<RHS = Self> {
    fn coprime_with(self, other: RHS) -> bool;
}

/// Combines two congruences by the Chinese remainder theorem, returning `None` if the moduli are
/// not coprime. The residues must be already reduced modulo their moduli.
pub trait Crt<M1 = Self, R2 = Self, M2 = Self> {
    type Output;

    fn crt(self, m1: M1, r2: R2, m2: M2) -> Option<Self::Output>;
}

/// Combines two congruences by the Chinese remainder theorem, returning the representative of
/// smallest absolute value, or `None` if the moduli are not coprime. The first residue may be
/// negative.
pub trait BalancedCrt<M1 = Self, R2 = Self, M2 = Self> {
    type Output;

    fn balanced_crt(self, m1: M1, r2: R2, m2: M2) -> Option<Self::Output>;
}

/// Divides two numbers, assuming the first exactly divides the second.
///
/// If it doesn't, the `div_exact` function may panic or return a meaningless result.
pub trait DivExact<RHS = Self> {
    type Output;

    fn div_exact(self, other: RHS) -> Self::Output;
}

/// Divides a number by another number in place, assuming the first exactly divides the second.
///
/// If it doesn't, this function may panic or assign a meaningless number to the first number.
pub trait DivExactAssign<RHS = Self> {
    fn div_exact_assign(&mut self, other: RHS);
}

/// Divides two numbers, returning the quotient and remainder. The quotient is rounded towards
/// negative infinity, and the remainder has the same sign as the divisor (second input).
///
/// The quotient and remainder satisfy $x = qy + r$ and $0 \leq |r| < |y|$.
pub trait DivMod<RHS = Self> {
    type DivOutput;
    type ModOutput;

    fn div_mod(self, other: RHS) -> (Self::DivOutput, Self::ModOutput);
}

/// Divides two numbers, returning the quotient and remainder. The quotient is rounded towards
/// negative infinity, and the remainder has the same sign as the divisor (second input).
///
/// The quotient and remainder satisfy $x = qy + r$ and $0 \leq |r| < |y|$.
///
/// If multiple divisions by the same divisor are necessary, it can be quicker to precompute some
/// piece of data based on the divisor and reuse it in the division calls. This trait provides a
/// function for precomputing the data and a function for using it during division.
pub trait DivModPrecomputed<RHS = Self> {
    type DivOutput;
    type ModOutput;
    type Data;

    /// Precomputes some data to use for division.
    fn precompute_div_mod_data(other: &RHS) -> Self::Data;

    fn div_mod_precomputed(
        self,
        other: RHS,
        data: &Self::Data,
    ) -> (Self::DivOutput, Self::ModOutput);
}

/// Divides a number by another number in place, returning the remainder. The quotient is rounded
/// towards negative infinity, and the remainder has the same sign as the divisor (second input).
///
/// The quotient and remainder satisfy $x = qy + r$ and $0 \leq |r| < |y|$.
///
/// If multiple divisions by the same divisor are necessary, it can be quicker to precompute some
/// piece of data based on the divisor and reuse it in the division calls. This trait provides a
/// function for using precomputed data during division. For precomputing the data, use the
/// [`precompute_div_mod_data`](DivModPrecomputed::precompute_div_mod_data) function in
/// [`DivModPrecomputed`].
pub trait DivAssignModPrecomputed<RHS = Self>: DivModPrecomputed<RHS> {
    fn div_assign_mod_precomputed(&mut self, other: RHS, data: &Self::Data) -> Self::ModOutput;
}

/// Divides two numbers, returning just the quotient. The quotient is rounded towards the quotient
/// that makes the remainder nonnegative.
///
/// If the remainder were computed, the quotient and remainder would satisfy $x = qy + r$ and $0
/// \leq r < |y|$.
pub trait DivEuclidean<RHS = Self> {
    type Output;

    fn div_euclidean(self, other: RHS) -> Self::Output;
}

/// Divides a number by another number in place, keeping just the quotient. The quotient is rounded
/// towards the quotient that makes the remainder nonnegative.
///
/// If the remainder were computed, the quotient and remainder would satisfy $x = qy + r$ and $0
/// \leq r < |y|$.
pub trait DivEuclideanAssign<RHS = Self> {
    fn div_euclidean_assign(&mut self, other: RHS);
}

/// Divides two numbers, returning the quotient and remainder. The quotient is rounded towards the
/// quotient that makes the remainder nonnegative, and the remainder is always nonnegative.
///
/// The quotient and remainder satisfy $x = qy + r$ and $0 \leq r < |y|$.
pub trait DivModEuclidean<RHS = Self> {
    type DivOutput;
    type ModOutput;

    fn div_mod_euclidean(self, other: RHS) -> (Self::DivOutput, Self::ModOutput);
}

/// Divides a number by another number in place, returning the remainder. The quotient is rounded
/// towards negative infinity, and the remainder has the same sign as the divisor (second input).
///
/// The quotient and remainder satisfy $x = qy + r$ and $0 \leq |r| < |y|$.
pub trait DivAssignMod<RHS = Self> {
    type ModOutput;

    fn div_assign_mod(&mut self, other: RHS) -> Self::ModOutput;
}

/// Divides a number by another number in place, returning the remainder. The quotient is rounded
/// towards the quotient that makes the remainder nonnegative, and the remainder is always
/// nonnegative.
///
/// The quotient and remainder satisfy $x = qy + r$ and $0 \leq r < |y|$.
pub trait DivAssignModEuclidean<RHS = Self> {
    type ModOutput;

    fn div_assign_mod_euclidean(&mut self, other: RHS) -> Self::ModOutput;
}

/// Divides two numbers, returning the quotient and remainder. The quotient is rounded towards zero,
/// and the remainder has the same sign as the dividend (first input).
///
/// The quotient and remainder satisfy $x = qy + r$ and $0 \leq |r| < |y|$.
pub trait DivRem<RHS = Self> {
    type DivOutput;
    type RemOutput;

    fn div_rem(self, other: RHS) -> (Self::DivOutput, Self::RemOutput);
}

/// Divides a number by another number in place, returning the remainder. The quotient is rounded
/// towards zero, and the remainder has the same sign as the dividend (first input).
///
/// The quotient and remainder satisfy $x = qy + r$ and $0 \leq |r| < |y|$.
pub trait DivAssignRem<RHS = Self> {
    type RemOutput;

    fn div_assign_rem(&mut self, other: RHS) -> Self::RemOutput;
}

/// Divides a number by another number, returning the ceiling of the quotient and the remainder of
/// the negative of the first number divided by the second.
///
/// The quotient and remainder satisfy $x = qy - r$ and $0 \leq r < y$.
pub trait CeilingDivNegMod<RHS = Self> {
    type DivOutput;
    type ModOutput;

    fn ceiling_div_neg_mod(self, other: RHS) -> (Self::DivOutput, Self::ModOutput);
}

/// Divides a number by another number in place, taking the ceiling of the quotient and returning
/// the remainder of the negative of the first number divided by the second.
///
/// The quotient and remainder satisfy $x = qy - r$ and $0 \leq r < y$.
pub trait CeilingDivAssignNegMod<RHS = Self> {
    type ModOutput;

    fn ceiling_div_assign_neg_mod(&mut self, other: RHS) -> Self::ModOutput;
}

/// Divides a number by another number, returning the quotient and remainder. The quotient is
/// rounded towards positive infinity and the remainder has the opposite sign as the divisor (second
/// input).
///
/// The quotient and remainder satisfy $x = qy + r$ and $0 \leq |r| < |y|$.
pub trait CeilingDivMod<RHS = Self> {
    type DivOutput;
    type ModOutput;

    fn ceiling_div_mod(self, other: RHS) -> (Self::DivOutput, Self::ModOutput);
}

/// Divides a number by another number in place, taking the quotient and returning the remainder.
/// The quotient is rounded towards positive infinity and the remainder has the opposite sign of the
/// divisor (second input).
///
/// The quotient and remainder satisfy $x = qy + r$ and $0 \leq |r| < |y|$.
pub trait CeilingDivAssignMod<RHS = Self> {
    type ModOutput;

    fn ceiling_div_assign_mod(&mut self, other: RHS) -> Self::ModOutput;
}

/// Divides a number by another number and rounds according to a specified rounding mode. An
/// [`Ordering`] is also returned, indicating whether the returned value is less than, equal to, or
/// greater than the exact value.
pub trait DivRound<RHS = Self> {
    type Output;

    fn div_round(self, other: RHS, rm: RoundingMode) -> (Self::Output, Ordering);
}

/// Divides a number by another number in place and rounds according to a specified rounding mode.
/// An [`Ordering`] is returned, indicating whether the assigned value is less than, equal to, or
/// greater than the exact value.
pub trait DivRoundAssign<RHS = Self> {
    fn div_round_assign(&mut self, other: RHS, rm: RoundingMode) -> Ordering;
}

/// Determines whether a number is divisible by $2^k$.
pub trait DivisibleByPowerOf2 {
    fn divisible_by_power_of_2(self, pow: u64) -> bool;
}

/// Determines whether a number is divisible by another number.
pub trait DivisibleBy<RHS = Self> {
    fn divisible_by(self, other: RHS) -> bool;
}

/// Determines whether a number is equivalent to another number modulo $2^k$.
pub trait EqModPowerOf2<RHS = Self> {
    fn eq_mod_power_of_2(self, other: RHS, pow: u64) -> bool;
}

/// Determines whether a number is equivalent to another number modulo $m$.
pub trait EqMod<RHS = Self, M = Self> {
    fn eq_mod(self, other: RHS, m: M) -> bool;
}

/// Computes the GCD (greatest common divisor) of two numbers $a$ and $b$, and also the coefficients
/// $x$ and $y$ in Bézout's identity $ax+by=\gcd(a,b)$.
///
/// The are infinitely many $x$, $y$ that satisfy the identity, so the full specification is more
/// detailed:
///
/// - $f(0, 0) = (0, 0, 0)$.
/// - $f(a, ak) = (a, 1, 0)$ if $a > 0$ and $k \neq 1$.
/// - $f(a, ak) = (-a, -1, 0)$ if $a < 0$ and $k \neq 1$.
/// - $f(bk, b) = (b, 0, 1)$ if $b > 0$.
/// - $f(bk, b) = (-b, 0, -1)$ if $b < 0$.
/// - $f(a, b) = (g, x, y)$ if $a \neq 0$ and $b \neq 0$ and $\gcd(a, b) \neq \min(|a|, |b|)$, where
///   $g = \gcd(a, b) \geq 0$, $ax + by = g$, $x \leq \lfloor b/g \rfloor$, and $y \leq \lfloor a/g
///   \rfloor$.
pub trait ExtendedGcd<RHS = Self> {
    type Gcd;
    type Cofactor;

    fn extended_gcd(self, other: RHS) -> (Self::Gcd, Self::Cofactor, Self::Cofactor);
}

/// Computes the $n$th Bell number: the number of ways to partition a set of $n$ elements.
pub trait BellNumber {
    fn bell_number(n: u64) -> Self;
}

/// Computes the $n$th Bell number, returning `None` if the result is too large to be represented.
pub trait CheckedBellNumber: Sized {
    fn checked_bell_number(n: u64) -> Option<Self>;
}

/// Computes the factorial of a `u64`.
pub trait Factorial {
    fn factorial(n: u64) -> Self;
}

/// Computes the factorial of a `u64`, returning `None` if the result is too large to be
/// represented.
pub trait CheckedFactorial: Sized {
    fn checked_factorial(n: u64) -> Option<Self>;
}

/// Computes the double factorial of a `u64`. The double factorial of a non-negative integer is the
/// product of all the positive integers that are less than or equal to it and have the same parity
/// as it.
pub trait DoubleFactorial {
    fn double_factorial(n: u64) -> Self;
}

/// Computes the double factorial of a `u64`, returning `None` if the result is too large to be
/// represented. The double factorial of a non-negative integer is the product of all the positive
/// integers that are less than or equal to it and have the same parity as it.
pub trait CheckedDoubleFactorial: Sized {
    fn checked_double_factorial(n: u64) -> Option<Self>;
}

/// Computes the $m$-multifactorial of a `u64`. The $m$-multifactorial of a non-negative integer $n$
/// is the product of all integers $k$ such that $0<k\leq n$ and $k\equiv n \pmod m$.
pub trait Multifactorial {
    fn multifactorial(n: u64, m: u64) -> Self;
}

/// Computes the $m$-multifactorial of a `u64`, returning `None` if the result is too large to be
/// represented. The $m$-multifactorial of a non-negative integer $n$ is the product of all integers
/// $k$ such that $0<k\leq n$ and $k\equiv n \pmod m$.
pub trait CheckedMultifactorial: Sized {
    fn checked_multifactorial(n: u64, m: u64) -> Option<Self>;
}

/// Computes the subfactorial of a `u64`. The subfactorial of a non-negative integer $n$ counts the
/// number of derangements of $n$ elements, which are the permutations in which no element is fixed.
pub trait Subfactorial {
    fn subfactorial(n: u64) -> Self;
}

/// Computes the subfactorial of a `u64`, returning `None` if the result is too large to be
/// represented. The subfactorial of a non-negative integer $n$ counts the number of derangements of
/// $n$ elements, which are the permutations in which no element is fixed.
pub trait CheckedSubfactorial: Sized {
    fn checked_subfactorial(n: u64) -> Option<Self>;
}

/// Computes the rising factorial of a number: the product of the `n` consecutive numbers starting
/// at `self`, or 1 when `n` is 0.
pub trait RisingFactorial {
    type Output;

    fn rising_factorial(self, n: u64) -> Self::Output;
}

/// Computes the rising factorial of a number, returning `None` if the result cannot be represented.
pub trait CheckedRisingFactorial: Sized {
    fn checked_rising_factorial(self, n: u64) -> Option<Self>;
}

/// Computes the falling factorial of a number: the product of the `n` consecutive numbers counting
/// down from `self`, or 1 when `n` is 0.
pub trait FallingFactorial {
    type Output;

    fn falling_factorial(self, n: u64) -> Self::Output;
}

/// Computes the falling factorial of a number, returning `None` if the result cannot be
/// represented.
pub trait CheckedFallingFactorial: Sized {
    fn checked_falling_factorial(self, n: u64) -> Option<Self>;
}

/// Computes the $n$th Fibonacci number, either alone or paired with its predecessor:
/// `fibonacci_pair(n)` returns $(F(n), F(n-1))$.
pub trait Fibonacci: Sized {
    fn fibonacci(n: u64) -> Self;

    fn fibonacci_pair(n: u64) -> (Self, Self);
}

/// Computes the $n$th Fibonacci number, either alone or paired with its predecessor, returning
/// `None` if the result is too large to be represented.
pub trait CheckedFibonacci: Sized {
    fn checked_fibonacci(n: u64) -> Option<Self>;

    fn checked_fibonacci_pair(n: u64) -> Option<(Self, Self)>;
}

/// Takes the floor of a number.
pub trait Floor {
    type Output;

    fn floor(self) -> Self::Output;
}

/// Replaces a number with its floor.
pub trait FloorAssign {
    fn floor_assign(&mut self);
}

/// Calculates the GCD (greatest common divisor) of two numbers.
pub trait Gcd<RHS = Self> {
    type Output;

    fn gcd(self, other: RHS) -> Self::Output;
}

/// Replaces a number with the GCD (greatest common divisor) of it and another number.
pub trait GcdAssign<RHS = Self> {
    fn gcd_assign(&mut self, other: RHS);
}

/// Calculates the height of a value: the largest of the magnitudes of the parts it is built from.
///
/// For a rational number $p/q$ in lowest terms this is $\max(|p|, q)$, the measure in which
/// Diophantine approximation bounds are usually stated. For something built out of several such
/// values — a polynomial, or a complex number — it is the largest of their heights.
pub trait Height {
    type Output;

    fn to_height(&self) -> Self::Output;

    fn into_height(self) -> Self::Output;

    fn height_significant_bits(&self) -> u64;
}

/// Lends the height of a value, for the types that already hold it.
///
/// Most heights are one of the magnitudes the value is built from, so they can be lent rather than
/// built: a rational number's height is its numerator or its denominator, and a polynomial's is one
/// of its coefficients. This is separate from [`Height`] because not every height is stored — the
/// coefficients of a polynomial over the rationals share one denominator, so a coefficient's height
/// has to be worked out before it can be compared with the others, and there is nothing to lend.
///
/// It is also not worth implementing where the height is a primitive integer, since there is no
/// clone to avoid.
pub trait HeightRef: Height {
    fn height_ref(&self) -> &Self::Output;
}

/// Calculates 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.
pub trait L1Norm {
    type Output;

    fn to_l1_norm(&self) -> Self::Output;

    fn into_l1_norm(self) -> Self::Output;

    fn l1_norm_significant_bits(&self) -> u64;
}

/// Calculates the sum of the elements of a vector modulo $2^k$.
///
/// The elements must already be reduced modulo $2^k$. Unlike [`ModPowerOf2Sum`], which adds vectors
/// to each other, this adds up the elements of one vector, producing a single element.
pub trait ModPowerOf2ElementSum {
    type Output;

    fn to_mod_power_of_2_element_sum(&self, pow: u64) -> Self::Output;

    fn into_mod_power_of_2_element_sum(self, pow: u64) -> Self::Output;
}

/// Calculates the sum of the elements of a vector modulo another number $m$.
///
/// The elements must already be reduced modulo $m$. Unlike [`ModSum`], which adds vectors to each
/// other, this adds up the elements of one vector, producing a single element.
pub trait ModElementSum<M> {
    type Output;

    fn to_mod_element_sum(&self, m: M) -> Self::Output;

    fn into_mod_element_sum(self, m: M) -> Self::Output;
}

/// Calculates the product of the elements of a vector as a value of a wider type, so that the
/// product cannot overflow.
///
/// Unlike [`ElementProduct`], whose output has the type of the elements, this produces a `T` that
/// can hold any product of them: for example, the product of the elements of an
/// [`UnsignedVector<u64>`](crate::unsigned_vector::UnsignedVector) as a `Natural`.
pub trait WideningElementProduct<T> {
    fn to_widening_element_product(&self) -> T;

    fn into_widening_element_product(self) -> T;
}

/// Calculates the product of the elements of a vector modulo $2^k$.
///
/// The elements must already be reduced modulo $2^k$. Unlike [`ModPowerOf2Product`], which
/// multiplies values from an iterator, this multiplies the elements of one vector, producing a
/// single element.
pub trait ModPowerOf2ElementProduct {
    type Output;

    fn to_mod_power_of_2_element_product(&self, pow: u64) -> Self::Output;

    fn into_mod_power_of_2_element_product(self, pow: u64) -> Self::Output;
}

/// Calculates the product of the elements of a vector modulo another number $m$.
///
/// The elements must already be reduced modulo $m$. Unlike [`ModProduct`], which multiplies values
/// from an iterator, this multiplies the elements of one vector, producing a single element.
pub trait ModElementProduct<M> {
    type Output;

    fn to_mod_element_product(&self, m: M) -> Self::Output;

    fn into_mod_element_product(self, m: M) -> Self::Output;
}

/// Computes the dot product of two vectors: the sum of the products of their corresponding
/// elements.
///
/// The vectors must have the same dimension. The dot product of two 0-dimensional vectors is 0.
pub trait Dot<RHS = Self> {
    type Output;

    fn dot(self, other: RHS) -> Self::Output;
}

/// Determines the sign of the dot product of two vectors, as the ordering of the dot product
/// against 0, without computing the dot product when it can be avoided.
///
/// The vectors must have the same dimension.
pub trait DotSign<RHS = Self> {
    fn dot_sign(self, other: RHS) -> Ordering;
}

/// Computes the dot product of two vectors modulo $2^k$. The elements must already be reduced
/// modulo $2^k$.
pub trait ModPowerOf2Dot<RHS = Self> {
    type Output;

    fn mod_power_of_2_dot(self, other: RHS, pow: u64) -> Self::Output;
}

/// Computes the dot product of two vectors modulo another number $m$. The elements must already be
/// reduced modulo $m$.
pub trait ModDot<RHS = Self, M = Self> {
    type Output;

    fn mod_dot(self, other: RHS, m: M) -> Self::Output;
}

/// Calculates the LCM of the elements of a vector.
///
/// The LCM of the elements of the 0-dimensional vector is 1, and the LCM is 0 if any element is 0.
pub trait ElementLcm {
    type Output;

    fn to_element_lcm(&self) -> Self::Output;

    fn into_element_lcm(self) -> Self::Output;
}

/// Calculates the product of the elements of a vector.
///
/// Unlike [`Product`](core::iter::Product), which would multiply vectors together, this multiplies
/// the elements of one vector, producing a single element.
pub trait ElementProduct {
    type Output;

    fn to_element_product(&self) -> Self::Output;

    fn into_element_product(self) -> Self::Output;
}

/// Calculates the sum of the elements of a vector.
///
/// Unlike [`Sum`](core::iter::Sum), which adds vectors to each other, this adds up the elements of
/// one vector, producing a single element.
pub trait ElementSum {
    type Output;

    fn to_element_sum(&self) -> Self::Output;

    fn into_element_sum(self) -> Self::Output;
}

/// Determines whether a number is an integer power of 2.
pub trait IsPowerOf2 {
    fn is_power_of_2(&self) -> bool;
}

/// Calculates the LCM (least common multiple) of two numbers.
pub trait Lcm<RHS = Self> {
    type Output;

    fn lcm(self, other: RHS) -> Self::Output;
}

/// Replaces a number with the LCM (least common multiple) of it and another number.
pub trait LcmAssign<RHS = Self> {
    fn lcm_assign(&mut self, other: RHS);
}

/// Computes the content of a value: the unique non-negative rational $c$ such that the value is $c$
/// times an element of the underlying integer lattice with coprime coordinates.
///
/// This applies to an element of a vector space over the rationals with a distinguished integer
/// lattice, like a polynomial, a Gaussian rational, or a vector. For an element of the lattice
/// itself, such as a polynomial or vector with integer entries, the content is the GCD of the
/// coordinates, a non-negative integer. Zero has content 0.
///
/// The content does not depend on any choice of sign or unit: [`PrimitivePart`] and
/// [`CanonicalPrimitivePart`] both divide by the same content.
pub trait Content {
    type Output;

    fn content(self) -> Self::Output;
}

/// Computes the GCD of a given value and the content of another: for a vector, the GCD of the value
/// and the vector's elements.
///
/// This makes it possible to accumulate the common content of several values one at a time,
/// starting from 0. As with [`Content`], the computation can stop as soon as the GCD reaches 1.
pub trait ContentChained<T> {
    type Output;

    fn content_chained(self, x: T) -> Self::Output;
}

/// Computes the primitive part of a value: the element of the underlying integer lattice, with
/// coprime coordinates, that the value is the [`Content`] times.
///
/// $$
/// x = \operatorname{cont}(x) \operatorname{pp}(x).
/// $$
///
/// No sign or unit is chosen, so the primitive part of $-x$ is the negative of the primitive part
/// of $x$. The primitive part of zero is zero. For the representative that is canonical under
/// multiplication by units, see [`CanonicalPrimitivePart`].
pub trait PrimitivePart {
    type Output;

    fn primitive_part(self) -> Self::Output;
}

/// Replaces a value with its primitive part.
///
/// See [`PrimitivePart`].
pub trait PrimitivePartAssign {
    fn primitive_part_assign(&mut self);
}

/// Computes the content and the primitive part of a value together.
///
/// The primitive part is found by dividing by the content, so computing both at once finds the
/// content only once. See [`Content`] and [`PrimitivePart`].
pub trait ContentAndPrimitivePart {
    type Content;
    type PrimitivePart;

    fn content_and_primitive_part(self) -> (Self::Content, Self::PrimitivePart);
}

/// Computes the canonical primitive part of a value: its [`PrimitivePart`], replaced by the
/// canonical associate under multiplication by units, as [`CanonicalizeUnit`] chooses it.
///
/// $$
/// x = u \operatorname{cont}(x) \operatorname{cpp}(x),
/// $$
///
/// where $u$ is a unit. Each implementation documents its choice of associate: for a polynomial
/// with integer or rational coefficients it is the one with a non-negative leading coefficient, for
/// a vector it is the one whose first nonzero element is positive, and for a Gaussian rational it
/// is the one whose argument lies in $(-\pi/4, \pi/4]$. Values with no negative coordinates have
/// only one associate to choose from, so for them this is the same as [`PrimitivePart`]. The
/// canonical primitive part of zero is zero.
pub trait CanonicalPrimitivePart {
    type Output;

    fn canonical_primitive_part(self) -> Self::Output;
}

/// Replaces a value with its canonical primitive part.
///
/// See [`CanonicalPrimitivePart`].
pub trait CanonicalPrimitivePartAssign {
    fn canonical_primitive_part_assign(&mut self);
}

/// Computes the content and the canonical primitive part of a value together.
///
/// The canonical primitive part is found by dividing by the content, so computing both at once
/// finds the content only once. See [`Content`] and [`CanonicalPrimitivePart`].
pub trait ContentAndCanonicalPrimitivePart {
    type Content;
    type CanonicalPrimitivePart;

    fn content_and_canonical_primitive_part(self) -> (Self::Content, Self::CanonicalPrimitivePart);
}

/// Computes $e^x$, the exponential of a number.
pub trait Exp {
    type Output;

    fn exp(self) -> Self::Output;
}

/// Replaces a number with its exponential, $e^x$.
pub trait ExpAssign {
    fn exp_assign(&mut self);
}

/// Computes $\cos(x)$, the cosine of a number.
pub trait Cos {
    type Output;

    fn cos(self) -> Self::Output;
}

/// Replaces a number with its cosine, $\cos(x)$.
pub trait CosAssign {
    fn cos_assign(&mut self);
}

/// Computes $\sin(x)$, the sine of a number.
pub trait Sin {
    type Output;

    fn sin(self) -> Self::Output;
}

/// Replaces a number with its sine, $\sin(x)$.
pub trait SinAssign {
    fn sin_assign(&mut self);
}

/// Computes $\sin(x)$ and $\cos(x)$, the sine and cosine of a number, together.
pub trait SinCos {
    type Output;

    fn sin_cos(self) -> (Self::Output, Self::Output);
}

/// Computes $\tan(x)$, the tangent of a number.
pub trait Tan {
    type Output;

    fn tan(self) -> Self::Output;
}

/// Replaces a number with its tangent, $\tan(x)$.
pub trait TanAssign {
    fn tan_assign(&mut self);
}

/// Computes $\sec(x)$, the secant of a number.
pub trait Sec {
    type Output;

    fn sec(self) -> Self::Output;
}

/// Replaces a number with its secant, $\sec(x)$.
pub trait SecAssign {
    fn sec_assign(&mut self);
}

/// Computes $\csc(x)$, the cosecant of a number.
pub trait Csc {
    type Output;

    fn csc(self) -> Self::Output;
}

/// Replaces a number with its cosecant, $\csc(x)$.
pub trait CscAssign {
    fn csc_assign(&mut self);
}

/// Computes $\cot(x)$, the cotangent of a number.
pub trait Cot {
    type Output;

    fn cot(self) -> Self::Output;
}

/// Replaces a number with its cotangent, $\cot(x)$.
pub trait CotAssign {
    fn cot_assign(&mut self);
}

/// Computes $\arctan(x)$, the arctangent of a number.
pub trait Atan {
    type Output;

    fn atan(self) -> Self::Output;
}

/// Replaces a number with its arctangent, $\arctan(x)$.
pub trait AtanAssign {
    fn atan_assign(&mut self);
}

/// Computes $\operatorname{atan2}(y,x)$, the angle of the point $(x,y)$ measured from the positive
/// $x$-axis.
pub trait Atan2<RHS = Self> {
    type Output;

    fn atan2(self, other: RHS) -> Self::Output;
}

/// Replaces a number $y$ with $\operatorname{atan2}(y,x)$, the angle of the point $(x,y)$ measured
/// from the positive $x$-axis.
pub trait Atan2Assign<RHS = Self> {
    fn atan2_assign(&mut self, other: RHS);
}

/// Computes $\arcsin(x)$, the arcsine of a number.
pub trait Asin {
    type Output;

    fn asin(self) -> Self::Output;
}

/// Replaces a number with its arcsine, $\arcsin(x)$.
pub trait AsinAssign {
    fn asin_assign(&mut self);
}

/// Computes $\arccos(x)$, the arccosine of a number.
pub trait Acos {
    type Output;

    fn acos(self) -> Self::Output;
}

/// Replaces a number with its arccosine, $\arccos(x)$.
pub trait AcosAssign {
    fn acos_assign(&mut self);
}

/// Computes $\operatorname{asec}(x)$, the arcsecant of a number.
pub trait Asec {
    type Output;

    fn asec(self) -> Self::Output;
}

/// Replaces a number with its arcsecant, $\operatorname{asec}(x)$.
pub trait AsecAssign {
    fn asec_assign(&mut self);
}

/// Computes $\operatorname{acsc}(x)$, the arccosecant of a number.
pub trait Acsc {
    type Output;

    fn acsc(self) -> Self::Output;
}

/// Replaces a number with its arccosecant, $\operatorname{acsc}(x)$.
pub trait AcscAssign {
    fn acsc_assign(&mut self);
}

/// Computes $\operatorname{acot}(x)$, the arccotangent of a number.
pub trait Acot {
    type Output;

    fn acot(self) -> Self::Output;
}

/// Replaces a number with its arccotangent, $\operatorname{acot}(x)$.
pub trait AcotAssign {
    fn acot_assign(&mut self);
}

/// Computes $\cosh(x)$, the hyperbolic cosine of a number.
pub trait Cosh {
    type Output;

    fn cosh(self) -> Self::Output;
}

/// Replaces a number with its hyperbolic cosine, $\cosh(x)$.
pub trait CoshAssign {
    fn cosh_assign(&mut self);
}

/// Computes $\sinh(x)$, the hyperbolic sine of a number.
pub trait Sinh {
    type Output;

    fn sinh(self) -> Self::Output;
}

/// Replaces a number with its hyperbolic sine, $\sinh(x)$.
pub trait SinhAssign {
    fn sinh_assign(&mut self);
}

/// Computes $\sinh(x)$ and $\cosh(x)$, the hyperbolic sine and cosine of a number, together.
pub trait SinhCosh {
    type Output;

    fn sinh_cosh(self) -> (Self::Output, Self::Output);
}

/// Replaces a number with its hyperbolic sine, $\sinh(x)$, and writes its hyperbolic cosine,
/// $\cosh(x)$, to a second number.
pub trait SinhCoshAssign {
    fn sinh_cosh_assign(&mut self, cosh: &mut Self);
}

/// Computes $\tanh(x)$, the hyperbolic tangent of a number.
pub trait Tanh {
    type Output;

    fn tanh(self) -> Self::Output;
}

/// Replaces a number with its hyperbolic tangent, $\tanh(x)$.
pub trait TanhAssign {
    fn tanh_assign(&mut self);
}

/// Computes $\operatorname{sech}(x)$, the hyperbolic secant of a number.
pub trait Sech {
    type Output;

    fn sech(self) -> Self::Output;
}

/// Replaces a number with its hyperbolic secant, $\operatorname{sech}(x)$.
pub trait SechAssign {
    fn sech_assign(&mut self);
}

/// Computes $\operatorname{csch}(x)$, the hyperbolic cosecant of a number.
pub trait Csch {
    type Output;

    fn csch(self) -> Self::Output;
}

/// Replaces a number with its hyperbolic cosecant, $\operatorname{csch}(x)$.
pub trait CschAssign {
    fn csch_assign(&mut self);
}

/// Computes $\coth(x)$, the hyperbolic cotangent of a number.
pub trait Coth {
    type Output;

    fn coth(self) -> Self::Output;
}

/// Replaces a number with its hyperbolic cotangent, $\coth(x)$.
pub trait CothAssign {
    fn coth_assign(&mut self);
}

/// Computes $\operatorname{asinh}(x)$, the inverse hyperbolic sine of a number.
pub trait Asinh {
    type Output;

    fn asinh(self) -> Self::Output;
}

/// Replaces a number with its inverse hyperbolic sine, $\operatorname{asinh}(x)$.
pub trait AsinhAssign {
    fn asinh_assign(&mut self);
}

/// Computes $\operatorname{acosh}(x)$, the inverse hyperbolic cosine of a number.
pub trait Acosh {
    type Output;

    fn acosh(self) -> Self::Output;
}

/// Replaces a number with its inverse hyperbolic cosine, $\operatorname{acosh}(x)$.
pub trait AcoshAssign {
    fn acosh_assign(&mut self);
}

/// Computes $\operatorname{atanh}(x)$, the inverse hyperbolic tangent of a number.
pub trait Atanh {
    type Output;

    fn atanh(self) -> Self::Output;
}

/// Replaces a number with its inverse hyperbolic tangent, $\operatorname{atanh}(x)$.
pub trait AtanhAssign {
    fn atanh_assign(&mut self);
}

/// Computes $\operatorname{asech}(x)$, the inverse hyperbolic secant of a number.
pub trait Asech {
    type Output;

    fn asech(self) -> Self::Output;
}

/// Replaces a number with its inverse hyperbolic secant, $\operatorname{asech}(x)$.
pub trait AsechAssign {
    fn asech_assign(&mut self);
}

/// Computes $\operatorname{acsch}(x)$, the inverse hyperbolic cosecant of a number.
pub trait Acsch {
    type Output;

    fn acsch(self) -> Self::Output;
}

/// Replaces a number with its inverse hyperbolic cosecant, $\operatorname{acsch}(x)$.
pub trait AcschAssign {
    fn acsch_assign(&mut self);
}

/// Computes $\operatorname{acoth}(x)$, the inverse hyperbolic cotangent of a number.
pub trait Acoth {
    type Output;

    fn acoth(self) -> Self::Output;
}

/// Replaces a number with its inverse hyperbolic cotangent, $\operatorname{acoth}(x)$.
pub trait AcothAssign {
    fn acoth_assign(&mut self);
}

/// Replaces a number with its sine, $\sin(x)$, and writes its cosine, $\cos(x)$, to a second
/// number.
pub trait SinCosAssign {
    fn sin_cos_assign(&mut self, cos: &mut Self);
}

/// Computes $e^x-1$, the exponential of a number, minus one.
pub trait ExpXMinus1 {
    type Output;

    fn exp_x_minus_1(self) -> Self::Output;
}

/// Replaces a number $x$ with $e^x-1$.
pub trait ExpXMinus1Assign {
    fn exp_x_minus_1_assign(&mut self);
}

/// Computes $2^x-1$, two raised to the power of a number, minus one.
pub trait PowerOf2XMinus1 {
    type Output;

    fn power_of_2_x_minus_1(self) -> Self::Output;
}

/// Replaces a number $x$ with $2^x-1$.
pub trait PowerOf2XMinus1Assign {
    fn power_of_2_x_minus_1_assign(&mut self);
}

/// Computes $10^x-1$, ten raised to the power of a number, minus one.
pub trait PowerOf10XMinus1 {
    type Output;

    fn power_of_10_x_minus_1(self) -> Self::Output;
}

/// Replaces a number $x$ with $10^x-1$.
pub trait PowerOf10XMinus1Assign {
    fn power_of_10_x_minus_1_assign(&mut self);
}

/// Takes the natural logarithm of a number.
pub trait Ln {
    type Output;

    fn ln(self) -> Self::Output;
}

/// Replaces a number with its natural logarithm.
pub trait LnAssign {
    fn ln_assign(&mut self);
}

/// Computes $\ln(1+x)$.
pub trait Ln1PlusX {
    type Output;

    fn ln_1_plus_x(self) -> Self::Output;
}

/// Replaces a number $x$ by $\ln(1+x)$.
pub trait Ln1PlusXAssign {
    fn ln_1_plus_x_assign(&mut self);
}

/// Calculates the LCM (least common multiple) of two numbers, returning `None` if the result is not
/// representable.
pub trait CheckedLcm<RHS = Self> {
    type Output;

    fn checked_lcm(self, other: RHS) -> Option<Self::Output>;
}

/// Calculates the Legendre symbol of two numbers. Typically the implementations will be identical
/// to those of [`JacobiSymbol`].
pub trait LegendreSymbol<RHS = Self> {
    fn legendre_symbol(self, other: RHS) -> i8;
}

/// Calculates the Jacobi symbol of two numbers.
pub trait JacobiSymbol<RHS = Self> {
    fn jacobi_symbol(self, other: RHS) -> i8;
}

/// Calculates the Kronecker symbol of two numbers.
pub trait KroneckerSymbol<RHS = Self> {
    fn kronecker_symbol(self, other: RHS) -> i8;
}

/// Calculates the base-$b$ logarithm of a number, or returns `None` if the number is not a perfect
/// power of $b$.
pub trait CheckedLogBase<B = Self> {
    type Output;

    fn checked_log_base(self, base: B) -> Option<Self::Output>;
}

/// Calculates the floor of the base-$b$ logarithm of a number.
pub trait FloorLogBase<B = Self> {
    type Output;

    fn floor_log_base(self, base: B) -> Self::Output;
}

/// Calculates the ceiling of the base-$b$ logarithm of a number.
pub trait CeilingLogBase<B = Self> {
    type Output;

    fn ceiling_log_base(self, base: B) -> Self::Output;
}

/// Calculates the base-2 logarithm of a number, or returns `None` if the number is not a perfect
/// power of 2.
pub trait CheckedLogBase2 {
    type Output;

    fn checked_log_base_2(self) -> Option<Self::Output>;
}

/// Calculates the base-2 logarithm of a number.
pub trait LogBase2 {
    type Output;

    fn log_base_2(self) -> Self::Output;
}

/// Replaces a number with its base-2 logarithm.
pub trait LogBase2Assign {
    fn log_base_2_assign(&mut self);
}

/// Calculates the base-10 logarithm of a number, rounding the (generally irrational) result.
pub trait LogBase10 {
    type Output;

    fn log_base_10(self) -> Self::Output;
}

/// Replaces a number with its base-10 logarithm, rounding the (generally irrational) result.
pub trait LogBase10Assign {
    fn log_base_10_assign(&mut self);
}

/// Computes $\log_2(1+x)$.
pub trait LogBase2Of1PlusX {
    type Output;

    fn log_base_2_1_plus_x(self) -> Self::Output;
}

/// Replaces a number $x$ by $\log_2(1+x)$.
pub trait LogBase2Of1PlusXAssign {
    fn log_base_2_1_plus_x_assign(&mut self);
}

/// Computes $\log_{2^k}(1+x)$.
pub trait LogBasePowerOf2Of1PlusX<POW> {
    type Output;

    fn log_base_power_of_2_1_plus_x(self, pow: POW) -> Self::Output;
}

/// Replaces a number $x$ by $\log_{2^k}(1+x)$.
pub trait LogBasePowerOf2Of1PlusXAssign<POW> {
    fn log_base_power_of_2_1_plus_x_assign(&mut self, pow: POW);
}

/// Computes $\log_b(1+x)$ for an integer base $b$.
pub trait LogBaseOf1PlusX<B = Self> {
    type Output;

    fn log_base_1_plus_x(self, base: B) -> Self::Output;
}

/// Replaces a number $x$ by $\log_b(1+x)$ for an integer base $b$.
pub trait LogBaseOf1PlusXAssign<B = Self> {
    fn log_base_1_plus_x_assign(&mut self, base: B);
}

/// Computes $\log_{10}(1+x)$.
pub trait LogBase10Of1PlusX {
    type Output;

    fn log_base_10_1_plus_x(self) -> Self::Output;
}

/// Replaces a number $x$ by $\log_{10}(1+x)$.
pub trait LogBase10Of1PlusXAssign {
    fn log_base_10_1_plus_x_assign(&mut self);
}

/// Calculates the floor of the base-2 logarithm of a number.
pub trait FloorLogBase2 {
    type Output;

    fn floor_log_base_2(self) -> Self::Output;
}

/// Calculates the ceiling of the base-2 logarithm of a number.
pub trait CeilingLogBase2 {
    type Output;

    fn ceiling_log_base_2(self) -> Self::Output;
}

/// Calculates the base-$2^k$ logarithm of a number, or returns `None` if the number is not a
/// perfect power of $2^k$.
pub trait CheckedLogBasePowerOf2<POW> {
    type Output;

    fn checked_log_base_power_of_2(self, pow: POW) -> Option<Self::Output>;
}

/// Calculates the floor of the base-$2^k$ logarithm of a number.
pub trait FloorLogBasePowerOf2<POW> {
    type Output;

    fn floor_log_base_power_of_2(self, pow: POW) -> Self::Output;
}

/// Calculates the ceiling of the base-$2^k$ logarithm of a number.
pub trait CeilingLogBasePowerOf2<POW> {
    type Output;

    fn ceiling_log_base_power_of_2(self, pow: POW) -> Self::Output;
}

/// Calculates the base-$2^k$ logarithm of a number.
pub trait LogBasePowerOf2<POW> {
    type Output;

    fn log_base_power_of_2(self, pow: POW) -> Self::Output;
}

/// Replaces a number with its base-$2^k$ logarithm.
pub trait LogBasePowerOf2Assign<POW> {
    fn log_base_power_of_2_assign(&mut self, pow: POW);
}

/// Calculates the base-$b$ logarithm of a number, rounding the (generally irrational) result.
pub trait LogBase<B = Self> {
    type Output;

    fn log_base(self, base: B) -> Self::Output;
}

/// Replaces a number with its base-$b$ logarithm, rounding the (generally irrational) result.
pub trait LogBaseAssign<B = Self> {
    fn log_base_assign(&mut self, base: B);
}

/// Computes the $n$th Lucas number, either alone or paired with its predecessor:
/// `lucas_number_pair(n)` returns $(L(n), L(n-1))$.
pub trait LucasNumber: Sized {
    fn lucas_number(n: u64) -> Self;

    fn lucas_number_pair(n: u64) -> (Self, Self);
}

/// Computes the $n$th Lucas number, either alone or paired with its predecessor, returning `None`
/// if the result is too large to be represented.
pub trait CheckedLucasNumber: Sized {
    fn checked_lucas_number(n: u64) -> Option<Self>;

    fn checked_lucas_number_pair(n: u64) -> Option<(Self, Self)>;
}

/// Adds two numbers modulo a third number $m$. The inputs must be already reduced modulo $m$.
pub trait ModAdd<RHS = Self, M = Self> {
    type Output;

    fn mod_add(self, other: RHS, m: M) -> Self::Output;
}

/// Adds two numbers modulo a third number $m$, in place. The inputs must be already reduced modulo
/// $m$.
pub trait ModAddAssign<RHS = Self, M = Self> {
    fn mod_add_assign(&mut self, other: RHS, m: M);
}

/// Divides a number by another number modulo a third number $m$, returning `None` if no quotient
/// exists. The inputs must be already reduced modulo $m$.
///
/// If the divisor is not invertible modulo $m$, a quotient may exist without being unique; in that
/// case one of the quotients is returned.
pub trait ModDiv<RHS = Self, M = Self> {
    type Output;

    fn mod_div(self, other: RHS, m: M) -> Option<Self::Output>;
}

/// Finds all quotients of a number and another number modulo a third number $m$, returning `None`
/// if no quotient exists. The inputs must be already reduced modulo $m$.
///
/// The quotients form an arithmetic progression: `Some((start, stride, length))` means that the
/// quotients are exactly the numbers $\text{start} + \text{stride} \cdot i$ for $0 \leq i <
/// \text{length}$, where `start` is the smallest quotient.
pub trait ModDivList<RHS = Self, M = Self> {
    type Output;

    #[allow(clippy::type_complexity)]
    fn mod_div_list(self, other: RHS, m: M) -> Option<(Self::Output, Self::Output, Self::Output)>;
}

/// Finds the multiplicative inverse of a number modulo another number $m$. The input must be
/// already reduced modulo $m$.
pub trait ModInverse<M = Self> {
    type Output;

    fn mod_inverse(self, m: M) -> Option<Self::Output>;
}

/// Checks whether a number is reduced modulo another number $m$.
pub trait ModIsReduced<M = Self> {
    fn mod_is_reduced(&self, m: &M) -> bool;
}

/// Multiplies two numbers modulo a third number $m$. The inputs must be already reduced modulo $m$.
pub trait ModMul<RHS = Self, M = Self> {
    type Output;

    fn mod_mul(self, other: RHS, m: M) -> Self::Output;
}

/// Multiplies two numbers modulo a third number $m$, in place. The inputs must be already reduced
/// modulo $m$.
pub trait ModMulAssign<RHS = Self, M = Self> {
    fn mod_mul_assign(&mut self, other: RHS, m: M);
}

/// Multiplies two numbers modulo a third number $m$. The inputs must be already reduced modulo $m$.
///
/// If multiple modular multiplications with the same modulus are necessary, it can be quicker to
/// precompute some piece of data and reuse it in the multiplication calls. This trait provides a
/// function for precomputing the data and a function for using it during multiplication.
pub trait ModMulPrecomputed<RHS = Self, M = Self> {
    type Output;
    type Data;

    /// Precomputes some data to use for modular multiplication.
    fn precompute_mod_mul_data(m: &M) -> Self::Data;

    fn mod_mul_precomputed(self, other: RHS, m: M, data: &Self::Data) -> Self::Output;
}

/// Multiplies two numbers modulo a third number $m$, in place.The inputs must be already reduced
/// modulo $m$.
///
/// If multiple modular multiplications with the same modulus are necessary, it can be quicker to
/// precompute some piece of data and reuse it in the multiplication calls. This trait provides a
/// function for using precomputed data during multiplication. For precomputing the data, use the
/// [`precompute_mod_mul_data`](ModMulPrecomputed::precompute_mod_mul_data) function in
/// [`ModMulPrecomputed`].
pub trait ModMulPrecomputedAssign<RHS = Self, M = Self>: ModMulPrecomputed<RHS, M> {
    fn mod_mul_precomputed_assign(&mut self, other: RHS, m: M, data: &Self::Data);
}

/// Adds a number and the product of two other numbers, modulo a fourth number $m$. All three inputs
/// must be already reduced modulo $m$.
pub trait ModAddMul<Y = Self, Z = Self, M = Self> {
    type Output;

    fn mod_add_mul(self, y: Y, z: Z, m: M) -> Self::Output;
}

/// Adds the product of two numbers to a number modulo a fourth number $m$, in place. All three
/// inputs must be already reduced modulo $m$.
pub trait ModAddMulAssign<Y = Self, Z = Self, M = Self> {
    fn mod_add_mul_assign(&mut self, y: Y, z: Z, m: M);
}

/// Subtracts the product of two numbers from a number, modulo a fourth number $m$. All three inputs
/// must be already reduced modulo $m$.
pub trait ModSubMul<Y = Self, Z = Self, M = Self> {
    type Output;

    fn mod_sub_mul(self, y: Y, z: Z, m: M) -> Self::Output;
}

/// Subtracts the product of two numbers from a number modulo a fourth number $m$, in place. All
/// three inputs must be already reduced modulo $m$.
pub trait ModSubMulAssign<Y = Self, Z = Self, M = Self> {
    fn mod_sub_mul_assign(&mut self, y: Y, z: Z, m: M);
}

/// Adds a number and the product of two other numbers, shifted left by a number of bits, modulo a
/// fourth number $m$: $x + yz2^b \bmod m$. All three inputs must be already reduced modulo $m$.
pub trait ModAddMulShl<Y = Self, Z = Self, M = Self> {
    type Output;

    fn mod_add_mul_shl(self, y: Y, z: Z, bits: u64, m: M) -> Self::Output;
}

/// Adds the product of two numbers, shifted left by a number of bits, to a number modulo a fourth
/// number $m$, in place. All three inputs must be already reduced modulo $m$.
pub trait ModAddMulShlAssign<Y = Self, Z = Self, M = Self> {
    fn mod_add_mul_shl_assign(&mut self, y: Y, z: Z, bits: u64, m: M);
}

/// Subtracts the product of two numbers, shifted left by a number of bits, from a number, modulo a
/// fourth number $m$: $x - yz2^b \bmod m$. All three inputs must be already reduced modulo $m$.
pub trait ModSubMulShl<Y = Self, Z = Self, M = Self> {
    type Output;

    fn mod_sub_mul_shl(self, y: Y, z: Z, bits: u64, m: M) -> Self::Output;
}

/// Subtracts the product of two numbers, shifted left by a number of bits, from a number modulo a
/// fourth number $m$, in place. All three inputs must be already reduced modulo $m$.
pub trait ModSubMulShlAssign<Y = Self, Z = Self, M = Self> {
    fn mod_sub_mul_shl_assign(&mut self, y: Y, z: Z, bits: u64, m: M);
}

/// Adds up the numbers in an iterator, modulo another number $m$. Every number must be already
/// reduced modulo $m$.
///
/// Like [`Sum`](core::iter::Sum), this is implemented both for iterators of values and for
/// iterators of references.
pub trait ModSum<A = Self, M = Self>: Sized {
    fn mod_sum<I: Iterator<Item = A>>(xs: I, m: M) -> Self;
}

/// Multiplies together the numbers in an iterator, modulo another number $m$. Every number must be
/// already reduced modulo $m$.
///
/// Like [`Product`](core::iter::Product), this is implemented both for iterators of values and for
/// iterators of references. The product of no numbers is 1 reduced modulo $m$, which is 0 when $m =
/// 1$.
pub trait ModProduct<A = Self, M = Self>: Sized {
    fn mod_product<I: Iterator<Item = A>>(xs: I, m: M) -> Self;
}

/// Negates a number modulo another number $m$. The input must be already reduced modulo $m$.
pub trait ModNeg<M = Self> {
    type Output;

    fn mod_neg(self, m: M) -> Self::Output;
}

/// Negates a number modulo another number $m$, in place. The input must be already reduced modulo
/// $m$.
pub trait ModNegAssign<M = Self> {
    fn mod_neg_assign(&mut self, m: M);
}

/// Divides a number by another number, returning just the remainder. The remainder has the same
/// sign as the divisor (second number).
///
/// If the quotient were computed, the quotient and remainder would satisfy $x = qy + r$ and $0 \leq
/// |r| < |y|$.
pub trait Mod<RHS = Self> {
    type Output;

    fn mod_op(self, other: RHS) -> Self::Output;
}

/// Divides a number by another number, replacing the first number by the remainder. The remainder
/// has the same sign as the divisor (second number).
///
/// If the quotient were computed, the quotient and remainder would satisfy $x = qy + r$ and $0 \leq
/// |r| < |y|$.
pub trait ModAssign<RHS = Self> {
    fn mod_assign(&mut self, other: RHS);
}

/// Divides a number by another number, returning the balanced remainder: the representative of the
/// first number modulo the second that is closest to zero.
///
/// The remainder $r$ satisfies $-|y|/2 < r \leq |y|/2$, so a remainder of exactly $|y|/2$ is
/// positive. It is congruent to $x$ modulo $y$, and those two properties determine it uniquely.
pub trait BalancedMod<RHS = Self> {
    type Output;

    fn balanced_mod(self, other: RHS) -> Self::Output;
}

/// Divides a number by another number, replacing the first number by the balanced remainder: the
/// representative of the first number modulo the second that is closest to zero.
///
/// The remainder $r$ satisfies $-|y|/2 < r \leq |y|/2$, so a remainder of exactly $|y|/2$ is
/// positive.
pub trait BalancedModAssign<RHS = Self> {
    fn balanced_mod_assign(&mut self, other: RHS);
}

/// Divides a number by another number, returning just the remainder. The remainder is always
/// nonnegative.
///
/// If the quotient were computed, the quotient and remainder would satisfy $x = qy + r$ and $0 \leq
/// r < |y|$.
pub trait ModEuclidean<RHS = Self> {
    type Output;

    fn mod_euclidean(self, other: RHS) -> Self::Output;
}

/// Divides a number by another number, replacing the first number by the remainder. The remainder
/// is always nonnegative.
///
/// If the quotient were computed, the quotient and remainder would satisfy $x = qy + r$ and $0 \leq
/// r < |y|$.
pub trait ModEuclideanAssign<RHS = Self> {
    fn mod_euclidean_assign(&mut self, other: RHS);
}

/// Divides the negative of a number by another number, returning the remainder.
///
/// If the quotient were computed, the quotient and remainder would satisfy $x = qy - r$ and $0 \leq
/// r < y$.
pub trait NegMod<RHS = Self> {
    type Output;

    fn neg_mod(self, other: RHS) -> Self::Output;
}

/// Divides the negative of a number by another number, replacing the first number by the remainder.
///
/// If the quotient were computed, the quotient and remainder would satisfy $x = qy - r$ and $0 \leq
/// r < y$.
pub trait NegModAssign<RHS = Self> {
    fn neg_mod_assign(&mut self, other: RHS);
}

/// Divides a number by another number, returning just the remainder. The remainder has the opposite
/// sign as the divisor (second number).
///
/// If the quotient were computed, the quotient and remainder would satisfy $x = qy + r$ and $0 \leq
/// |r| < |y|$.
pub trait CeilingMod<RHS = Self> {
    type Output;

    fn ceiling_mod(self, other: RHS) -> Self::Output;
}

/// Divides a number by another number, replacing the first number by the remainder. The remainder
/// has the same sign as the divisor (second number).
///
/// If the quotient were computed, the quotient and remainder would satisfy $x = qy + r$ and $0 \leq
/// |r| < |y|$.
pub trait CeilingModAssign<RHS = Self> {
    fn ceiling_mod_assign(&mut self, other: RHS);
}

/// Raises a number to a power modulo another number $m$. The base must be already reduced modulo
/// $m$.
pub trait ModPow<RHS = Self, M = Self> {
    type Output;

    fn mod_pow(self, exp: RHS, m: M) -> Self::Output;
}

/// Raises a number to a power modulo another number $m$, in place. The base must be already reduced
/// modulo $m$.
pub trait ModPowAssign<RHS = Self, M = Self> {
    fn mod_pow_assign(&mut self, exp: RHS, m: M);
}

/// Raises a number to a power modulo another number $m$. The base must be already reduced modulo
/// $m$.
///
/// If multiple modular exponentiations with the same modulus are necessary, it can be quicker to
/// precompute some piece of data and reuse it in the exponentiation calls. This trait provides a
/// function for precomputing the data and a function for using it during exponentiation.
pub trait ModPowPrecomputed<RHS = Self, M = Self>
where
    Self: Sized,
{
    type Output;
    type Data;

    /// Precomputes some data to use for modular exponentiation.
    fn precompute_mod_pow_data(m: &M) -> Self::Data;

    fn mod_pow_precomputed(self, exp: RHS, m: M, data: &Self::Data) -> Self::Output;
}

/// Raises a number to a power modulo another number $m$, in place. The base must be already reduced
/// modulo $m$.
///
/// If multiple modular exponentiations with the same modulus are necessary, it can be quicker to
/// precompute some piece of data and reuse it in the exponentiation calls. This trait provides a
/// function for using precomputed data during exponentiation. For precomputing the data, use the
/// [`precompute_mod_pow_data`](ModPowPrecomputed::precompute_mod_pow_data) function in
/// [`ModPowPrecomputed`].
pub trait ModPowPrecomputedAssign<RHS: Two = Self, M = Self>: ModPowPrecomputed<RHS, M> {
    fn mod_pow_precomputed_assign(&mut self, exp: RHS, m: M, data: &Self::Data);
}

/// Adds two numbers modulo $2^k$. The inputs must be already reduced modulo $2^k$.
pub trait ModPowerOf2Add<RHS = Self> {
    type Output;

    fn mod_power_of_2_add(self, other: RHS, pow: u64) -> Self::Output;
}

/// Adds two numbers modulo $2^k$, in place. The inputs must be already reduced modulo $2^k$.
pub trait ModPowerOf2AddAssign<RHS = Self> {
    fn mod_power_of_2_add_assign(&mut self, other: RHS, pow: u64);
}

/// Finds the multiplicative inverse of a number modulo $2^k$. The input must be already reduced
/// modulo $2^k$.
pub trait ModPowerOf2Inverse {
    type Output;

    fn mod_power_of_2_inverse(self, pow: u64) -> Option<Self::Output>;
}

/// Finds the least square root of a number modulo $2^k$, returning `None` if the number is not a
/// square modulo $2^k$. The input must be already reduced modulo $2^k$.
pub trait ModPowerOf2Sqrt {
    type Output;

    fn mod_power_of_2_sqrt(self, pow: u64) -> Option<Self::Output>;
}

/// Checks whether a number is reduced modulo $2^k$.
pub trait ModPowerOf2IsReduced {
    fn mod_power_of_2_is_reduced(&self, pow: u64) -> bool;
}

/// Multiplies two numbers modulo $2^k$. The inputs must be already reduced modulo $2^k$.
pub trait ModPowerOf2Mul<RHS = Self> {
    type Output;

    fn mod_power_of_2_mul(self, other: RHS, pow: u64) -> Self::Output;
}

/// Multiplies two numbers modulo $2^k$, in place. The inputs must be already reduced modulo $2^k$.
pub trait ModPowerOf2MulAssign<RHS = Self> {
    fn mod_power_of_2_mul_assign(&mut self, other: RHS, pow: u64);
}

/// Adds a number and the product of two other numbers, modulo $2^k$. All three inputs must be
/// already reduced modulo $2^k$.
pub trait ModPowerOf2AddMul<Y = Self, Z = Self> {
    type Output;

    fn mod_power_of_2_add_mul(self, y: Y, z: Z, pow: u64) -> Self::Output;
}

/// Adds the product of two numbers to a number modulo $2^k$, in place. All three inputs must be
/// already reduced modulo $2^k$.
pub trait ModPowerOf2AddMulAssign<Y = Self, Z = Self> {
    fn mod_power_of_2_add_mul_assign(&mut self, y: Y, z: Z, pow: u64);
}

/// Adds a number and the product of two other numbers, shifted left by a number of bits, modulo
/// $2^k$: $x + yz2^b \bmod 2^k$. All three inputs must be already reduced modulo $2^k$.
pub trait ModPowerOf2AddMulShl<Y = Self, Z = Self> {
    type Output;

    fn mod_power_of_2_add_mul_shl(self, y: Y, z: Z, bits: u64, pow: u64) -> Self::Output;
}

/// Adds the product of two numbers, shifted left by a number of bits, to a number modulo $2^k$, in
/// place. All three inputs must be already reduced modulo $2^k$.
pub trait ModPowerOf2AddMulShlAssign<Y = Self, Z = Self> {
    fn mod_power_of_2_add_mul_shl_assign(&mut self, y: Y, z: Z, bits: u64, pow: u64);
}

/// Subtracts the product of two numbers from a number, modulo $2^k$. All three inputs must be
/// already reduced modulo $2^k$.
pub trait ModPowerOf2SubMul<Y = Self, Z = Self> {
    type Output;

    fn mod_power_of_2_sub_mul(self, y: Y, z: Z, pow: u64) -> Self::Output;
}

/// Subtracts the product of two numbers from a number modulo $2^k$, in place. All three inputs must
/// be already reduced modulo $2^k$.
pub trait ModPowerOf2SubMulAssign<Y = Self, Z = Self> {
    fn mod_power_of_2_sub_mul_assign(&mut self, y: Y, z: Z, pow: u64);
}

/// Subtracts the product of two numbers, shifted left by a number of bits, from a number, modulo
/// $2^k$: $x - yz2^b \bmod 2^k$. All three inputs must be already reduced modulo $2^k$.
pub trait ModPowerOf2SubMulShl<Y = Self, Z = Self> {
    type Output;

    fn mod_power_of_2_sub_mul_shl(self, y: Y, z: Z, bits: u64, pow: u64) -> Self::Output;
}

/// Subtracts the product of two numbers, shifted left by a number of bits, from a number modulo
/// $2^k$, in place. All three inputs must be already reduced modulo $2^k$.
pub trait ModPowerOf2SubMulShlAssign<Y = Self, Z = Self> {
    fn mod_power_of_2_sub_mul_shl_assign(&mut self, y: Y, z: Z, bits: u64, pow: u64);
}

/// Adds up the numbers in an iterator, modulo $2^k$. Every number must be already reduced modulo
/// $2^k$.
///
/// Like [`Sum`](core::iter::Sum), this is implemented both for iterators of values and for
/// iterators of references.
pub trait ModPowerOf2Sum<A = Self>: Sized {
    fn mod_power_of_2_sum<I: Iterator<Item = A>>(xs: I, pow: u64) -> Self;
}

/// Multiplies together the numbers in an iterator, modulo $2^k$. Every number must be already
/// reduced modulo $2^k$.
///
/// Like [`Product`](core::iter::Product), this is implemented both for iterators of values and for
/// iterators of references. The product of no numbers is 1 reduced modulo $2^k$, which is 0 when $k
/// = 0$.
pub trait ModPowerOf2Product<A = Self>: Sized {
    fn mod_power_of_2_product<I: Iterator<Item = A>>(xs: I, pow: u64) -> Self;
}

/// Negates a number modulo $2^k$. The input must be already reduced modulo $2^k$.
pub trait ModPowerOf2Neg {
    type Output;

    fn mod_power_of_2_neg(self, pow: u64) -> Self::Output;
}

/// Negates a number modulo $2^k$ in place. The input must be already reduced modulo $2^k$.
pub trait ModPowerOf2NegAssign {
    fn mod_power_of_2_neg_assign(&mut self, pow: u64);
}

/// Raises a number to a power modulo $2^k$. The base must be already reduced modulo $2^k$.
pub trait ModPowerOf2Pow<RHS = Self> {
    type Output;

    fn mod_power_of_2_pow(self, exp: RHS, pow: u64) -> Self::Output;
}

/// Raises a number to a power modulo $2^k$, in place. The base must be already reduced modulo
/// $2^k$.
pub trait ModPowerOf2PowAssign<RHS = Self> {
    fn mod_power_of_2_pow_assign(&mut self, exp: RHS, pow: u64);
}

/// Left-shifts a number (multiplies it by a power of 2) modulo $2^k$. The number must be already
/// reduced modulo $2^k$.
pub trait ModPowerOf2Shl<RHS> {
    type Output;

    fn mod_power_of_2_shl(self, other: RHS, pow: u64) -> Self::Output;
}

/// Left-shifts a number (multiplies it by a power of 2) modulo $2^k$, in place. The number must be
/// already reduced modulo $2^k$.
pub trait ModPowerOf2ShlAssign<RHS> {
    fn mod_power_of_2_shl_assign(&mut self, other: RHS, pow: u64);
}

/// Right-shifts a number (divides it by a power of 2) modulo $2^k$. The number must be already
/// reduced modulo $2^k$.
pub trait ModPowerOf2Shr<RHS> {
    type Output;

    fn mod_power_of_2_shr(self, other: RHS, pow: u64) -> Self::Output;
}

/// Right-shifts a number (divides it by a power of 2) modulo $2^k$, in place. The number must be
/// already reduced modulo $2^k$.
pub trait ModPowerOf2ShrAssign<RHS> {
    fn mod_power_of_2_shr_assign(&mut self, other: RHS, pow: u64);
}

/// Squares a number modulo $2^k$. The input must be already reduced modulo $2^k$.
pub trait ModPowerOf2Square {
    type Output;

    fn mod_power_of_2_square(self, pow: u64) -> Self::Output;
}

/// Squares a number modulo $2^k$ in place. The input must be already reduced modulo $2^k$.
pub trait ModPowerOf2SquareAssign {
    fn mod_power_of_2_square_assign(&mut self, pow: u64);
}

/// Computes the squared absolute value of a number modulo $2^k$. The input must be already reduced
/// modulo $2^k$.
///
/// For a real number this is its square modulo $2^k$; the trait exists for the types where it is
/// not, such as complex numbers and vectors, for which it is the reduced sum of squares.
pub trait ModPowerOf2AbsSquared {
    type Output;

    fn mod_power_of_2_abs_squared(self, pow: u64) -> Self::Output;
}

/// Replaces a number with its squared absolute value modulo $2^k$. The input must be already
/// reduced modulo $2^k$.
pub trait ModPowerOf2AbsSquaredAssign {
    fn mod_power_of_2_abs_squared_assign(&mut self, pow: u64);
}

/// Subtracts two numbers modulo $2^k$. The inputs must be already reduced modulo $2^k$.
pub trait ModPowerOf2Sub<RHS = Self> {
    type Output;

    fn mod_power_of_2_sub(self, other: RHS, pow: u64) -> Self::Output;
}

/// Subtracts two numbers modulo $2^k$, in place. The inputs must be already reduced modulo $2^k$.
pub trait ModPowerOf2SubAssign<RHS = Self> {
    fn mod_power_of_2_sub_assign(&mut self, other: RHS, pow: u64);
}

/// Divides a number by $2^k$, returning the balanced remainder: the representative of the number
/// modulo $2^k$ that is closest to zero.
///
/// The remainder $r$ satisfies $-2^{k-1} < r \leq 2^{k-1}$, so a remainder of exactly $2^{k-1}$ is
/// positive, as with [`BalancedMod`]; for $k = 0$ it is 0. It is congruent to $x$ modulo $2^k$, and
/// those two properties determine it uniquely.
pub trait BalancedModPowerOf2 {
    type Output;

    fn balanced_mod_power_of_2(self, pow: u64) -> Self::Output;
}

/// Divides a number by $2^k$, replacing the number by the balanced remainder: the representative of
/// the number modulo $2^k$ that is closest to zero.
///
/// The remainder $r$ satisfies $-2^{k-1} < r \leq 2^{k-1}$, so a remainder of exactly $2^{k-1}$ is
/// positive; for $k = 0$ it is 0.
pub trait BalancedModPowerOf2Assign {
    fn balanced_mod_power_of_2_assign(&mut self, pow: u64);
}

/// Divides a number by $2^k$, returning just the remainder. The remainder is non-negative.
///
/// If the quotient were computed, the quotient and remainder would satisfy $x = q2^k + r$ and $0
/// \leq r < 2^k$.
pub trait ModPowerOf2 {
    type Output;

    fn mod_power_of_2(self, other: u64) -> Self::Output;
}

/// Divides a number by $2^k$, replacing the number by the remainder. The remainder is non-negative.
///
/// If the quotient were computed, the quotient and remainder would satisfy $x = q2^k + r$ and $0
/// \leq r < 2^k$.
pub trait ModPowerOf2Assign {
    fn mod_power_of_2_assign(&mut self, other: u64);
}

/// Divides a number by $2^k$, returning just the remainder. The remainder has the same sign as the
/// number.
///
/// If the quotient were computed, the quotient and remainder would satisfy $x = q2^k + r$ and $0
/// \leq |r| < 2^k$.
pub trait RemPowerOf2 {
    type Output;

    fn rem_power_of_2(self, other: u64) -> Self::Output;
}

/// Divides a number by $2^k$, replacing the number by the remainder. The remainder has the same
/// sign as the number.
///
/// If the quotient were computed, the quotient and remainder would satisfy $x = q2^k + r$ and $0
/// \leq |r| < 2^k$.
pub trait RemPowerOf2Assign {
    fn rem_power_of_2_assign(&mut self, other: u64);
}

/// Divides the negative of a number by $2^k$, returning the remainder.
///
/// If the quotient were computed, the quotient and remainder would satisfy $x = q2^k - r$ and $0
/// \leq r < 2^k$.
pub trait NegModPowerOf2 {
    type Output;

    fn neg_mod_power_of_2(self, other: u64) -> Self::Output;
}

/// Divides the negative of a number by $2^k$, replacing the number by the remainder.
///
/// If the quotient were computed, the quotient and remainder would satisfy $x = q2^k - r$ and $0
/// \leq r < 2^k$.
pub trait NegModPowerOf2Assign {
    fn neg_mod_power_of_2_assign(&mut self, other: u64);
}

/// Divides a number by $2^k$, returning just the remainder. The remainder is non-positive.
///
/// If the quotient were computed, the quotient and remainder would satisfy $x = q2^k + r$ and $0
/// \leq -r < 2^k$.
pub trait CeilingModPowerOf2 {
    type Output;

    fn ceiling_mod_power_of_2(self, other: u64) -> Self::Output;
}

/// Divides a number by $2^k$, replacing the number by the remainder. The remainder is non-positive.
///
/// If the quotient were computed, the quotient and remainder would satisfy $x = q2^k + r$ and $0
/// \leq -r < 2^k$.
pub trait CeilingModPowerOf2Assign {
    fn ceiling_mod_power_of_2_assign(&mut self, other: u64);
}

/// Left-shifts a number (multiplies it by a power of 2) modulo another number $m$. The number must
/// be already reduced modulo $m$.
pub trait ModShl<RHS, M = Self> {
    type Output;

    fn mod_shl(self, other: RHS, m: M) -> Self::Output;
}

/// Left-shifts a number (multiplies it by a power of 2) modulo another number $m$, in place. The
/// number must be already reduced modulo $m$.
pub trait ModShlAssign<RHS, M = Self> {
    fn mod_shl_assign(&mut self, other: RHS, m: M);
}

/// Right-shifts a number (divides it by a power of 2) modulo another number $m$. The number must be
/// already reduced modulo $m$.
pub trait ModShr<RHS, M = Self> {
    type Output;

    fn mod_shr(self, other: RHS, m: M) -> Self::Output;
}

/// Right-shifts a number (divides it by a power of 2) modulo another number $m$, in place. The
/// number must be already reduced modulo $m$.
pub trait ModShrAssign<RHS, M = Self> {
    fn mod_shr_assign(&mut self, other: RHS, m: M);
}

/// Computes a square root of a number modulo another number $m$, returning `None` if no root is
/// found. The input must be already reduced modulo $m$.
///
/// The modulus should be an odd prime: for such moduli a root is found whenever one exists. The
/// behavior for other moduli is deterministic and never hangs, but a root may be missed, and a
/// returned value may fail to be a root.
pub trait ModSqrt<M = Self> {
    type Output;

    fn mod_sqrt(self, m: M) -> Option<Self::Output>;
}

/// Squares a number modulo another number $m$. The input must be already reduced modulo $m$.
pub trait ModSquare<M = Self> {
    type Output;

    fn mod_square(self, m: M) -> Self::Output;
}

/// Squares a number modulo another number $m$, in place. The input must be already reduced modulo
/// $m$.
pub trait ModSquareAssign<M = Self> {
    fn mod_square_assign(&mut self, m: M);
}

/// Computes the squared absolute value of a number modulo another number $m$. The input must be
/// already reduced modulo $m$.
///
/// For a real number this is its square modulo $m$; the trait exists for the types where it is not,
/// such as complex numbers and vectors, for which it is the reduced sum of squares.
pub trait ModAbsSquared<M = Self> {
    type Output;

    fn mod_abs_squared(self, m: M) -> Self::Output;
}

/// Replaces a number with its squared absolute value modulo another number $m$. The input must be
/// already reduced modulo $m$.
pub trait ModAbsSquaredAssign<M = Self> {
    fn mod_abs_squared_assign(&mut self, m: M);
}

/// Squares a number modulo another number $m$. The input must be already reduced modulo $m$.
///
/// If multiple modular squarings with the same modulus are necessary, it can be quicker to
/// precompute some piece of data using
/// [`precompute_mod_pow_data`](ModPowPrecomputed::precompute_mod_pow_data) function in
/// [`ModMulPrecomputed`] and reuse it in the squaring calls.
pub trait ModSquarePrecomputed<RHS = Self, M = Self>: ModPowPrecomputed<RHS, M>
where
    Self: Sized,
{
    fn mod_square_precomputed(self, m: M, data: &Self::Data) -> Self::Output;
}

/// Squares a number modulo another number $m$, in place. The input must be already reduced modulo
/// $m$.
///
/// If multiple modular squarings with the same modulus are necessary, it can be quicker to
/// precompute some piece of data using
/// [`precompute_mod_pow_data`](ModPowPrecomputed::precompute_mod_pow_data) function in
/// [`ModMulPrecomputed`] and reuse it in the squaring calls.
pub trait ModSquarePrecomputedAssign<RHS = Self, M = Self>: ModPowPrecomputed<RHS, M> {
    fn mod_square_precomputed_assign(&mut self, m: M, data: &Self::Data);
}

/// Adds two numbers modulo a third number $m$. The inputs must be already reduced modulo $m$.
pub trait ModSub<RHS = Self, M = Self> {
    type Output;

    fn mod_sub(self, other: RHS, m: M) -> Self::Output;
}

/// Adds two numbers modulo a third number $m$, in place. The inputs must be already reduced modulo
/// $m$.
pub trait ModSubAssign<RHS = Self, M = Self> {
    fn mod_sub_assign(&mut self, other: RHS, m: M);
}

/// Replaces a number with its negative. Assumes the result is representable.
pub trait NegAssign {
    fn neg_assign(&mut self);
}

/// Returns the smallest power of 2 greater than or equal to a number. Assumes the result is
/// representable.
pub trait NextPowerOf2 {
    type Output;

    fn next_power_of_2(self) -> Self::Output;
}

/// Replaces a number with the smallest power of 2 greater than or equal it. Assumes the result is
/// representable.
pub trait NextPowerOf2Assign {
    fn next_power_of_2_assign(&mut self);
}

/// Takes the absolute value of a number.
///
/// Returns a tuple of the result along with a boolean indicating whether an arithmetic overflow
/// occurred. If an overflow occurred, then the wrapped number is returned.
pub trait OverflowingAbs {
    type Output;

    fn overflowing_abs(self) -> (Self::Output, bool);
}

/// Replaces a number with its absolute value.
///
/// Returns a boolean indicating whether an arithmetic overflow occurred. If an overflow occurred,
/// then the wrapped number is assigned.
pub trait OverflowingAbsAssign {
    fn overflowing_abs_assign(&mut self) -> bool;
}

/// Adds two numbers.
///
/// Returns a tuple of the sum along with a boolean indicating whether an arithmetic overflow
/// occurred. If an overflow occurred, then the wrapped number is returned.
pub trait OverflowingAdd<RHS = Self> {
    type Output;

    fn overflowing_add(self, other: RHS) -> (Self::Output, bool);
}

/// Adds a number to another number in place.
///
/// Returns a boolean indicating whether an arithmetic overflow occurred. If an overflow occurred,
/// then the wrapped number is assigned.
pub trait OverflowingAddAssign<RHS = Self> {
    fn overflowing_add_assign(&mut self, other: RHS) -> bool;
}

/// Adds a number and the product of two other numbers.
///
/// Returns a tuple of the result along with a boolean indicating whether an arithmetic overflow
/// occurred. If an overflow occurred, then the wrapped number is returned.
pub trait OverflowingAddMul<Y = Self, Z = Self> {
    type Output;

    fn overflowing_add_mul(self, y: Y, z: Z) -> (Self::Output, bool);
}

/// Adds a number and the product of two other numbers, in place.
///
/// Returns a tuple of the result along with a boolean indicating whether an arithmetic overflow
/// occurred. If an overflow occurred, then the wrapped number is returned.
pub trait OverflowingAddMulAssign<Y = Self, Z = Self> {
    fn overflowing_add_mul_assign(&mut self, y: Y, z: Z) -> bool;
}

/// Adds the products of two pairs of numbers.
///
/// Returns a tuple of the result along with a boolean indicating whether an arithmetic overflow
/// occurred. If an overflow occurred, then the wrapped result is returned.
pub trait OverflowingMulAddMul<Y = Self, Z = Self, W = Self> {
    type Output;

    fn overflowing_mul_add_mul(self, y: Y, z: Z, w: W) -> (Self::Output, bool);
}

/// Adds the products of two pairs of numbers, in place.
///
/// Returns a boolean indicating whether an arithmetic overflow occurred. If an overflow occurred,
/// then the wrapped result is assigned.
pub trait OverflowingMulAddMulAssign<Y = Self, Z = Self, W = Self> {
    fn overflowing_mul_add_mul_assign(&mut self, y: Y, z: Z, w: W) -> bool;
}

/// Subtracts the product of one pair of numbers from the product of another.
///
/// Returns a tuple of the result along with a boolean indicating whether an arithmetic overflow
/// occurred. If an overflow occurred, then the wrapped result is returned.
pub trait OverflowingMulSubMul<Y = Self, Z = Self, W = Self> {
    type Output;

    fn overflowing_mul_sub_mul(self, y: Y, z: Z, w: W) -> (Self::Output, bool);
}

/// Subtracts the product of one pair of numbers from the product of another, in place.
///
/// Returns a boolean indicating whether an arithmetic overflow occurred. If an overflow occurred,
/// then the wrapped result is assigned.
pub trait OverflowingMulSubMulAssign<Y = Self, Z = Self, W = Self> {
    fn overflowing_mul_sub_mul_assign(&mut self, y: Y, z: Z, w: W) -> bool;
}

/// Divides two numbers.
///
/// Returns a tuple of the sum along with a boolean indicating whether an arithmetic overflow
/// occurred. If an overflow occurred, then the wrapped number is returned.
pub trait OverflowingDiv<RHS = Self> {
    type Output;

    fn overflowing_div(self, other: RHS) -> (Self::Output, bool);
}

/// Divides a number by another number in place.
///
/// Returns a boolean indicating whether an arithmetic overflow occurred. If an overflow occurred,
/// then the wrapped number is assigned.
pub trait OverflowingDivAssign<RHS = Self> {
    fn overflowing_div_assign(&mut self, other: RHS) -> bool;
}

/// Multiplies two numbers.
///
/// Returns a tuple of the sum along with a boolean indicating whether an arithmetic overflow
/// occurred. If an overflow occurred, then the wrapped number is returned.
pub trait OverflowingMul<RHS = Self> {
    type Output;

    fn overflowing_mul(self, other: RHS) -> (Self::Output, bool);
}

/// Multiplies a number by another number in place.
///
/// Returns a boolean indicating whether an arithmetic overflow occurred. If an overflow occurred,
/// then the wrapped number is assigned.
pub trait OverflowingMulAssign<RHS = Self> {
    fn overflowing_mul_assign(&mut self, other: RHS) -> bool;
}

/// Negates a number.
///
/// Returns a tuple of the sum along with a boolean indicating whether an arithmetic overflow
/// occurred. If an overflow occurred, then the wrapped number is returned.
pub trait OverflowingNeg {
    type Output;

    fn overflowing_neg(self) -> (Self::Output, bool);
}

/// Negates a number in place.
///
/// Returns a boolean indicating whether an arithmetic overflow occurred. If an overflow occurred,
/// then the wrapped number is assigned.
pub trait OverflowingNegAssign {
    fn overflowing_neg_assign(&mut self) -> bool;
}

/// Raises a number to a power.
///
/// Returns a tuple of the sum along with a boolean indicating whether an arithmetic overflow
/// occurred. If an overflow occurred, then the wrapped number is returned.
pub trait OverflowingPow<RHS> {
    type Output;

    fn overflowing_pow(self, exp: RHS) -> (Self::Output, bool);
}

/// Raises a number to a power in place.
///
/// Returns a boolean indicating whether an arithmetic overflow occurred. If an overflow occurred,
/// then the wrapped number is assigned.
pub trait OverflowingPowAssign<RHS = Self> {
    fn overflowing_pow_assign(&mut self, exp: RHS) -> bool;
}

/// Squares a number.
///
/// Returns a tuple of the sum along with a boolean indicating whether an arithmetic overflow
/// occurred. If an overflow occurred, then the wrapped number is returned.
pub trait OverflowingSquare {
    type Output;

    fn overflowing_square(self) -> (Self::Output, bool);
}

/// Squares a number in place.
///
/// Returns a boolean indicating whether an arithmetic overflow occurred. If an overflow occurred,
/// then the wrapped number is assigned.
pub trait OverflowingSquareAssign {
    fn overflowing_square_assign(&mut self) -> bool;
}

/// Subtracts two numbers.
///
/// Returns a tuple of the sum along with a boolean indicating whether an arithmetic overflow
/// occurred. If an overflow occurred, then the wrapped number is returned.
pub trait OverflowingSub<RHS = Self> {
    type Output;

    fn overflowing_sub(self, other: RHS) -> (Self::Output, bool);
}

/// Subtracts a number by another number in place.
///
/// Returns a boolean indicating whether an arithmetic overflow occurred. If an overflow occurred,
/// then the wrapped number is assigned.
pub trait OverflowingSubAssign<RHS = Self> {
    fn overflowing_sub_assign(&mut self, other: RHS) -> bool;
}

/// Subtracts a number by the product of two other numbers.
///
/// Returns a tuple of the result along with a boolean indicating whether an arithmetic overflow
/// occurred. If an overflow occurred, then the wrapped number is returned.
pub trait OverflowingSubMul<Y = Self, Z = Self> {
    type Output;

    fn overflowing_sub_mul(self, y: Y, z: Z) -> (Self::Output, bool);
}

/// Subtracts a number by the product of two other numbers, in place.
///
/// Returns a tuple of the result along with a boolean indicating whether an arithmetic overflow
/// occurred. If an overflow occurred, then the wrapped number is returned.
pub trait OverflowingSubMulAssign<Y = Self, Z = Self> {
    fn overflowing_sub_mul_assign(&mut self, y: Y, z: Z) -> bool;
}

/// Determines whether a number is even or odd.
pub trait Parity {
    /// Determines whether a number is even.
    fn even(self) -> bool;

    /// Determines whether a number is odd.
    fn odd(self) -> bool;
}

/// Raises a number to a power. Assumes the result is representable.
pub trait Pow<RHS> {
    type Output;

    fn pow(self, exp: RHS) -> Self::Output;
}

/// Raises a number to a power in place. Assumes the result is representable.
pub trait PowAssign<RHS = Self> {
    fn pow_assign(&mut self, exp: RHS);
}

/// Raises 2 to a power.
pub trait PowerOf2<POW> {
    fn power_of_2(pow: POW) -> Self;
}

/// Replaces a number with 2 raised to the power of that number.
pub trait PowerOf2Assign {
    fn power_of_2_assign(&mut self);
}

/// Raises 10 to a power.
pub trait PowerOf10<POW> {
    fn power_of_10(pow: POW) -> Self;
}

/// Replaces a number with 10 raised to the power of that number.
pub trait PowerOf10Assign {
    fn power_of_10_assign(&mut self);
}

pub trait Primorial {
    fn primorial(n: u64) -> Self;

    fn product_of_first_n_primes(n: u64) -> Self;
}

pub trait CheckedPrimorial: Sized {
    fn checked_primorial(n: u64) -> Option<Self>;

    fn checked_product_of_first_n_primes(n: u64) -> Option<Self>;
}

/// Finds the reciprocal (multiplicative inverse) of a number.
pub trait Reciprocal {
    type Output;

    fn reciprocal(self) -> Self::Output;
}

/// Replaces a number with its reciprocal (multiplicative inverse).
pub trait ReciprocalAssign {
    fn reciprocal_assign(&mut self);
}

/// Takes the reciprocal of the square root of a number.
pub trait ReciprocalSqrt {
    type Output;

    fn reciprocal_sqrt(self) -> Self::Output;
}

/// Replaces a number with the reciprocal of its square root.
pub trait ReciprocalSqrtAssign {
    fn reciprocal_sqrt_assign(&mut self);
}

/// Finds the floor of the $n$th root of a number.
pub trait FloorRoot<POW> {
    type Output;

    fn floor_root(self, pow: POW) -> Self::Output;
}

/// Replaces a number with the floor of its $n$th root.
pub trait FloorRootAssign<POW> {
    fn floor_root_assign(&mut self, pow: POW);
}

/// Finds the ceiling of the $n$th root of a number.
pub trait CeilingRoot<POW> {
    type Output;

    fn ceiling_root(self, pow: POW) -> Self::Output;
}

/// Replaces a number with the ceiling of its $n$th root.
pub trait CeilingRootAssign<POW> {
    fn ceiling_root_assign(&mut self, pow: POW);
}

/// Finds the $n$th root of a number, returning `None` if it is not a perfect $n$th power.
pub trait CheckedRoot<POW> {
    type Output;

    fn checked_root(self, pow: POW) -> Option<Self::Output>;
}

/// Finds the floor of the $n$th root of a number, returning both the root and the remainder.
pub trait RootRem<POW> {
    type RootOutput;
    type RemOutput;

    fn root_rem(self, exp: POW) -> (Self::RootOutput, Self::RemOutput);
}

/// Replaces a number with the floor of its $n$th root, returning the remainder.
pub trait RootAssignRem<POW> {
    type RemOutput;

    fn root_assign_rem(&mut self, exp: POW) -> Self::RemOutput;
}

/// Takes the $n$th root of a number.
pub trait Root<POW> {
    type Output;

    fn root(self, pow: POW) -> Self::Output;
}

/// Replaces a number with its $n$th root.
pub trait RootAssign<POW> {
    fn root_assign(&mut self, pow: POW);
}

/// Takes the cube root of a number.
pub trait Cbrt {
    type Output;

    fn cbrt(self) -> Self::Output;
}

/// Replaces a number with its cube root.
pub trait CbrtAssign {
    fn cbrt_assign(&mut self);
}

/// Rotates a number left, inserting the leftmost bits into the right end.
pub trait RotateLeft {
    type Output;

    fn rotate_left(self, n: u64) -> Self::Output;
}

/// Rotates a number left, inserting the leftmost bits into the right end, in place.
pub trait RotateLeftAssign {
    fn rotate_left_assign(&mut self, n: u64);
}

/// Rotates a number right, inserting the leftmost bits into the left end.
pub trait RotateRight {
    type Output;

    fn rotate_right(self, n: u64) -> Self::Output;
}

/// Rotates a number right, inserting the leftmost bits into the left end, in place.
pub trait RotateRightAssign {
    fn rotate_right_assign(&mut self, n: u64);
}

/// Rounds a number to a multiple of another number, according to a specified rounding mode. An
/// [`Ordering`] is also returned, indicating whether the returned value is less than, equal to, or
/// greater than the original value.
pub trait RoundToMultiple<RHS = Self> {
    type Output;

    fn round_to_multiple(self, other: RHS, rm: RoundingMode) -> (Self::Output, Ordering);
}

/// Rounds a number to a multiple of another number in place, according to a specified rounding
/// mode. [`Ordering`] is returned, indicating whether the returned value is less than, equal to, or
/// greater than the original value.
pub trait RoundToMultipleAssign<RHS = Self> {
    fn round_to_multiple_assign(&mut self, other: RHS, rm: RoundingMode) -> Ordering;
}

/// Rounds a number to a multiple of $2^k$, according to a specified rounding mode. An [`Ordering`]
/// is also returned, indicating whether the returned value is less than, equal to, or greater than
/// the original value.
pub trait RoundToMultipleOfPowerOf2<RHS> {
    type Output;

    fn round_to_multiple_of_power_of_2(
        self,
        pow: RHS,
        rm: RoundingMode,
    ) -> (Self::Output, Ordering);
}

/// Rounds a number to a multiple of $2^k$ in place, according to a specified rounding mode. An
/// [`Ordering`] is returned, indicating whether the returned value is less than, equal to, or
/// greater than the original value.
pub trait RoundToMultipleOfPowerOf2Assign<RHS> {
    fn round_to_multiple_of_power_of_2_assign(&mut self, pow: RHS, rm: RoundingMode) -> Ordering;
}

/// Takes the absolute value of a number, saturating at the numeric bounds instead of overflowing.
pub trait SaturatingAbs {
    type Output;

    fn saturating_abs(self) -> Self::Output;
}

/// Replaces a number with its absolute value, saturating at the numeric bounds instead of
/// overflowing.
pub trait SaturatingAbsAssign {
    fn saturating_abs_assign(&mut self);
}

/// Adds two numbers, saturating at the numeric bounds instead of overflowing.
pub trait SaturatingAdd<RHS = Self> {
    type Output;

    fn saturating_add(self, other: RHS) -> Self::Output;
}

/// Add a number to another number in place, saturating at the numeric bounds instead of
/// overflowing.
pub trait SaturatingAddAssign<RHS = Self> {
    fn saturating_add_assign(&mut self, other: RHS);
}

/// Adds a number and the product of two other numbers, saturating at the numeric bounds instead of
/// overflowing.
pub trait SaturatingAddMul<Y = Self, Z = Self> {
    type Output;

    fn saturating_add_mul(self, y: Y, z: Z) -> Self::Output;
}

/// Adds a number and the product of two other numbers in place, saturating at the numeric bounds
/// instead of overflowing.
pub trait SaturatingAddMulAssign<Y = Self, Z = Self> {
    fn saturating_add_mul_assign(&mut self, y: Y, z: Z);
}

/// Adds the products of two pairs of numbers, saturating at the numeric bounds instead of
/// overflowing.
pub trait SaturatingMulAddMul<Y = Self, Z = Self, W = Self> {
    type Output;

    fn saturating_mul_add_mul(self, y: Y, z: Z, w: W) -> Self::Output;
}

/// Adds the products of two pairs of numbers, in place, saturating at the numeric bounds instead of
/// overflowing.
pub trait SaturatingMulAddMulAssign<Y = Self, Z = Self, W = Self> {
    fn saturating_mul_add_mul_assign(&mut self, y: Y, z: Z, w: W);
}

/// Subtracts the product of one pair of numbers from the product of another, saturating at the
/// numeric bounds instead of overflowing.
pub trait SaturatingMulSubMul<Y = Self, Z = Self, W = Self> {
    type Output;

    fn saturating_mul_sub_mul(self, y: Y, z: Z, w: W) -> Self::Output;
}

/// Subtracts the product of one pair of numbers from the product of another, in place, saturating
/// at the numeric bounds instead of overflowing.
pub trait SaturatingMulSubMulAssign<Y = Self, Z = Self, W = Self> {
    fn saturating_mul_sub_mul_assign(&mut self, y: Y, z: Z, w: W);
}

/// Multiplies two numbers, saturating at the numeric bounds instead of overflowing.
pub trait SaturatingMul<RHS = Self> {
    type Output;

    fn saturating_mul(self, other: RHS) -> Self::Output;
}

/// Multiplies a number by another number in place, saturating at the numeric bounds instead of
/// overflowing.
pub trait SaturatingMulAssign<RHS = Self> {
    fn saturating_mul_assign(&mut self, other: RHS);
}

/// Negates a number, saturating at the numeric bounds instead of overflowing.
pub trait SaturatingNeg {
    type Output;

    fn saturating_neg(self) -> Self::Output;
}

/// Negates a number in place, saturating at the numeric bounds instead of overflowing.
pub trait SaturatingNegAssign {
    fn saturating_neg_assign(&mut self);
}

/// Raises a number to a power, saturating at the numeric bounds instead of overflowing.
pub trait SaturatingPow<RHS> {
    type Output;

    fn saturating_pow(self, exp: RHS) -> Self::Output;
}

/// Raises a number to a power in place, saturating at the numeric bounds instead of overflowing.
pub trait SaturatingPowAssign<RHS = Self> {
    fn saturating_pow_assign(&mut self, exp: RHS);
}

/// Squares a number, saturating at the numeric bounds instead of overflowing.
pub trait SaturatingSquare {
    type Output;

    fn saturating_square(self) -> Self::Output;
}

/// Squares a number in place, saturating at the numeric bounds instead of overflowing.
pub trait SaturatingSquareAssign {
    fn saturating_square_assign(&mut self);
}

/// Subtracts two numbers, saturating at the numeric bounds instead of overflowing.
pub trait SaturatingSub<RHS = Self> {
    type Output;

    fn saturating_sub(self, other: RHS) -> Self::Output;
}

/// Subtracts a number by another number in place, saturating at the numeric bounds instead of
/// overflowing.
pub trait SaturatingSubAssign<RHS = Self> {
    fn saturating_sub_assign(&mut self, other: RHS);
}

/// Subtracts a number by the product of two other numbers, saturating at the numeric bounds instead
/// of overflowing.
pub trait SaturatingSubMul<Y = Self, Z = Self> {
    type Output;

    fn saturating_sub_mul(self, y: Y, z: Z) -> Self::Output;
}

/// Subtracts a number by the product of two other numbers in place, saturating at the numeric
/// bounds instead of overflowing.
pub trait SaturatingSubMulAssign<Y = Self, Z = Self> {
    fn saturating_sub_mul_assign(&mut self, y: Y, z: Z);
}

/// Left-shifts a number (multiplies it by a power of 2), rounding the result according to a
/// specified rounding mode. An [`Ordering`] is also returned, indicating whether the returned value
/// is less than, equal to, or greater than the exact value.
///
/// Rounding might only be necessary if `other` is negative.
pub trait ShlRound<RHS> {
    type Output;

    fn shl_round(self, other: RHS, rm: RoundingMode) -> (Self::Output, Ordering);
}

/// Left-shifts a number (multiplies it by a power of 2) in place, rounding the result according to
/// a specified rounding mode. An [`Ordering`] is also returned, indicating whether the assigned
/// value is less than, equal to, or greater than the exact value.
///
/// Rounding might only be necessary if `other` is negative.
pub trait ShlRoundAssign<RHS> {
    fn shl_round_assign(&mut self, other: RHS, rm: RoundingMode) -> Ordering;
}

/// Right-shifts a number (divides it by a power of 2), rounding the result according to a specified
/// rounding mode. An [`Ordering`] is also returned, indicating whether the returned value is less
/// than, equal to, or greater than the exact value.
///
/// Rounding might only be necessary if `other` is positive.
pub trait ShrRound<RHS> {
    type Output;

    fn shr_round(self, other: RHS, rm: RoundingMode) -> (Self::Output, Ordering);
}

/// Right-shifts a number (divides it by a power of 2) in place, rounding the result according to a
/// specified rounding mode. An [`Ordering`] is also returned, indicating whether the assigned value
/// is less than, equal to, or greater than the exact value.
///
/// Rounding might only be necessary if `other` is positive.
pub trait ShrRoundAssign<RHS> {
    fn shr_round_assign(&mut self, other: RHS, rm: RoundingMode) -> Ordering;
}

/// Returns `Greater`, `Equal`, or `Less`, depending on whether a number is positive, zero, or
/// negative, respectively.
pub trait Sign {
    fn sign(&self) -> Ordering;
}

/// Takes the square root of a number.
pub trait Sqrt {
    type Output;

    fn sqrt(self) -> Self::Output;
}

/// Replaces a number with its square root.
pub trait SqrtAssign {
    fn sqrt_assign(&mut self);
}

/// Finds the floor of the square root of a number.
pub trait FloorSqrt {
    type Output;

    fn floor_sqrt(self) -> Self::Output;
}

/// Replaces a number with the floor of its square root.
pub trait FloorSqrtAssign {
    fn floor_sqrt_assign(&mut self);
}

/// Finds the ceiling of the square root of a number.
pub trait CeilingSqrt {
    type Output;

    fn ceiling_sqrt(self) -> Self::Output;
}

/// Replaces a number with the ceiling of its square root.
pub trait CeilingSqrtAssign {
    fn ceiling_sqrt_assign(&mut self);
}

/// Finds the square root of a number, returning `None` if it is not a perfect square.
pub trait CheckedSqrt {
    type Output;

    fn checked_sqrt(self) -> Option<Self::Output>;
}

/// Finds the floor of the square root of a number, returning both the root and the remainder.
pub trait SqrtRem {
    type SqrtOutput;
    type RemOutput;

    fn sqrt_rem(self) -> (Self::SqrtOutput, Self::RemOutput);
}

/// Replaces a number with the floor of its square root, returning the remainder.
pub trait SqrtAssignRem {
    type RemOutput;

    fn sqrt_assign_rem(&mut self) -> Self::RemOutput;
}

/// Squares a number.
pub trait Square {
    type Output;

    fn square(self) -> Self::Output;
}

/// Replaces a number with its square.
pub trait SquareAssign {
    fn square_assign(&mut self);
}

/// Subtracts a number by the product of two other numbers.
///
/// Depending on the implementing type, the fused operation may compute the same value as the
/// unfused `self - y * z` more efficiently; or, for types with rounding, it may compute a *more
/// accurate* value -- the product enters the subtraction exactly, with a single rounding at the end
/// -- but *less* efficiently, since the exact product must be computed in full. See each
/// implementation's documentation for which contract it provides.
pub trait SubMul<Y = Self, Z = Self> {
    type Output;

    fn sub_mul(self, y: Y, z: Z) -> Self::Output;
}

/// Subtracts a number by the product of two other numbers, in place.
///
/// Depending on the implementing type, the fused operation may compute the same value as the
/// unfused `*self - y * z` more efficiently; or, for types with rounding, it may compute a *more
/// accurate* value -- the product enters the subtraction exactly, with a single rounding at the end
/// -- but *less* efficiently, since the exact product must be computed in full. See each
/// implementation's documentation for which contract it provides.
pub trait SubMulAssign<Y = Self, Z = Self> {
    fn sub_mul_assign(&mut self, y: Y, z: Z);
}

/// Subtracts the product of two numbers, shifted left by a number of bits, from a number: $x -
/// yz2^k$.
pub trait SubMulShl<Y = Self, Z = Self> {
    type Output;

    fn sub_mul_shl(self, y: Y, z: Z, bits: u64) -> Self::Output;
}

/// Subtracts the product of two numbers, shifted left by a number of bits, from a number in place:
/// $x \gets x - yz2^k$.
pub trait SubMulShlAssign<Y = Self, Z = Self> {
    fn sub_mul_shl_assign(&mut self, y: Y, z: Z, bits: u64);
}

/// Takes the absolute value of a number, wrapping around at the boundary of the type.
pub trait WrappingAbs {
    type Output;

    fn wrapping_abs(self) -> Self::Output;
}

/// Replaces a number with its absolute value, wrapping around at the boundary of the type.
pub trait WrappingAbsAssign {
    fn wrapping_abs_assign(&mut self);
}

/// Adds two numbers, wrapping around at the boundary of the type.
pub trait WrappingAdd<RHS = Self> {
    type Output;

    fn wrapping_add(self, other: RHS) -> Self::Output;
}

/// Adds a number to another number in place, wrapping around at the boundary of the type.
pub trait WrappingAddAssign<RHS = Self> {
    fn wrapping_add_assign(&mut self, other: RHS);
}

/// Adds a number and the product of two other numbers, wrapping around at the boundary of the type.
pub trait WrappingAddMul<Y = Self, Z = Self> {
    type Output;

    fn wrapping_add_mul(self, y: Y, z: Z) -> Self::Output;
}

/// Adds a number and the product of two other numbers, in place, wrapping around at the boundary of
/// the type.
pub trait WrappingAddMulAssign<Y = Self, Z = Self> {
    fn wrapping_add_mul_assign(&mut self, y: Y, z: Z);
}

/// Adds the products of two pairs of numbers, wrapping around at the boundary of the type.
pub trait WrappingMulAddMul<Y = Self, Z = Self, W = Self> {
    type Output;

    fn wrapping_mul_add_mul(self, y: Y, z: Z, w: W) -> Self::Output;
}

/// Adds the products of two pairs of numbers, in place, wrapping around at the boundary of the
/// type.
pub trait WrappingMulAddMulAssign<Y = Self, Z = Self, W = Self> {
    fn wrapping_mul_add_mul_assign(&mut self, y: Y, z: Z, w: W);
}

/// Subtracts the product of one pair of numbers from the product of another, wrapping around at the
/// boundary of the type.
pub trait WrappingMulSubMul<Y = Self, Z = Self, W = Self> {
    type Output;

    fn wrapping_mul_sub_mul(self, y: Y, z: Z, w: W) -> Self::Output;
}

/// Subtracts the product of one pair of numbers from the product of another, in place, wrapping
/// around at the boundary of the type.
pub trait WrappingMulSubMulAssign<Y = Self, Z = Self, W = Self> {
    fn wrapping_mul_sub_mul_assign(&mut self, y: Y, z: Z, w: W);
}

/// Divides a number by another number, wrapping around at the boundary of the type.
pub trait WrappingDiv<RHS = Self> {
    type Output;

    fn wrapping_div(self, other: RHS) -> Self::Output;
}

/// Divides a number by another number in place, wrapping around at the boundary of the type.
pub trait WrappingDivAssign<RHS = Self> {
    fn wrapping_div_assign(&mut self, other: RHS);
}

/// Multiplies two numbers, wrapping around at the boundary of the type.
pub trait WrappingMul<RHS = Self> {
    type Output;

    fn wrapping_mul(self, other: RHS) -> Self::Output;
}

/// Multiplies a number by another number in place, wrapping around at the boundary of the type.
pub trait WrappingMulAssign<RHS = Self> {
    fn wrapping_mul_assign(&mut self, other: RHS);
}

/// Negates a number, wrapping around at the boundary of the type.
pub trait WrappingNeg {
    type Output;

    fn wrapping_neg(self) -> Self::Output;
}

/// Negates a number in place, wrapping around at the boundary of the type.
pub trait WrappingNegAssign {
    fn wrapping_neg_assign(&mut self);
}

/// Raises a number to a power, wrapping around at the boundary of the type.
pub trait WrappingPow<RHS> {
    type Output;

    fn wrapping_pow(self, exp: RHS) -> Self::Output;
}

/// Raises a number to a power in place, wrapping around at the boundary of the type.
pub trait WrappingPowAssign<RHS = Self> {
    fn wrapping_pow_assign(&mut self, exp: RHS);
}

/// Squares a number, wrapping around at the boundary of the type.
pub trait WrappingSquare {
    type Output;

    fn wrapping_square(self) -> Self::Output;
}

/// Squares a number in place, wrapping around at the boundary of the type.
pub trait WrappingSquareAssign {
    fn wrapping_square_assign(&mut self);
}

/// Subtracts two numbers, wrapping around at the boundary of the type.
pub trait WrappingSub<RHS = Self> {
    type Output;

    fn wrapping_sub(self, other: RHS) -> Self::Output;
}

/// Subtracts a number by another number in place, wrapping around at the boundary of the type.
pub trait WrappingSubAssign<RHS = Self> {
    fn wrapping_sub_assign(&mut self, other: RHS);
}

/// Subtracts a number by the product of two other numbers, wrapping around at the boundary of the
/// type.
pub trait WrappingSubMul<Y = Self, Z = Self> {
    type Output;

    fn wrapping_sub_mul(self, y: Y, z: Z) -> Self::Output;
}

/// Subtracts a number by the product of two other numbers, in place, wrapping around at the
/// boundary of the type.
pub trait WrappingSubMulAssign<Y = Self, Z = Self> {
    fn wrapping_sub_mul_assign(&mut self, y: Y, z: Z);
}

/// Multiplies two numbers, returning the product as a pair of `Self` values.
///
/// The more significant number always comes first.
pub trait XMulYToZZ: Sized {
    fn x_mul_y_to_zz(x: Self, y: Self) -> (Self, Self);
}

/// Adds two numbers, each composed of two `Self` values, returning the sum as a pair of `Self`
/// values.
///
/// The more significant number always comes first. Addition is wrapping, and overflow is not
/// indicated.
pub trait XXAddYYToZZ: Sized {
    fn xx_add_yy_to_zz(x_1: Self, x_0: Self, y_1: Self, y_0: Self) -> (Self, Self);
}

/// Computes the quotient and remainder of two numbers. The first is composed of two `Self` values,
/// and the second of a single one.
///
/// `x_1` must be less than `y`.
pub trait XXDivModYToQR: Sized {
    fn xx_div_mod_y_to_qr(x_1: Self, x_0: Self, y: Self) -> (Self, Self);
}

/// Subtracts two numbers, each composed of two `Self` values, returing the difference as a pair of
/// `Self` values.
///
/// The more significant number always comes first. Subtraction is wrapping, and overflow is not
/// indicated.
pub trait XXSubYYToZZ: Sized {
    fn xx_sub_yy_to_zz(x_1: Self, x_0: Self, y_1: Self, y_0: Self) -> (Self, Self);
}

/// Adds two numbers, each composed of three `Self` values, returning the sum as a triple of `Self`
/// values.
///
/// The more significant number always comes first. Addition is wrapping, and overflow is not
/// indicated.
pub trait XXXAddYYYToZZZ: Sized {
    fn xxx_add_yyy_to_zzz(
        x_2: Self,
        x_1: Self,
        x_0: Self,
        y_2: Self,
        y_1: Self,
        y_0: Self,
    ) -> (Self, Self, Self);
}

/// Subtracts two numbers, each composed of three `Self` values, returing the difference as a triple
/// of `Self` values.
///
/// The more significant number always comes first. Subtraction is wrapping, and overflow is not
/// indicated.
pub trait XXXSubYYYToZZZ: Sized {
    fn xxx_sub_yyy_to_zzz(
        x_2: Self,
        x_1: Self,
        x_0: Self,
        y_2: Self,
        y_1: Self,
        y_0: Self,
    ) -> (Self, Self, Self);
}

/// Adds two numbers, each composed of four `Self` values, returning the sum as a quadruple of
/// `Self` values.
///
/// The more significant number always comes first. Addition is wrapping, and overflow is not
/// indicated.
pub trait XXXXAddYYYYToZZZZ: Sized {
    #[allow(clippy::too_many_arguments)]
    fn xxxx_add_yyyy_to_zzzz(
        x_3: Self,
        x_2: Self,
        x_1: Self,
        x_0: Self,
        y_3: Self,
        y_2: Self,
        y_1: Self,
        y_0: Self,
    ) -> (Self, Self, Self, Self);
}