dashu_base/ring/
mod.rs

1//! Trait definitions for operations related to rings (integer/polynomial/etc.)
2
3/// Compute quotient and remainder at the same time.
4///
5/// # Examples
6/// ```
7/// use dashu_base::DivRem;
8/// assert_eq!(23.div_rem(10), (2, 3));
9/// ```
10pub trait DivRem<Rhs = Self> {
11    /// The type of the quotient.
12    type OutputDiv;
13    /// The type of the remainder.
14    type OutputRem;
15
16    /// Compute the quotient and remainder at the same time.
17    fn div_rem(self, rhs: Rhs) -> (Self::OutputDiv, Self::OutputRem);
18}
19
20/// Compute quotient inplace and return remainder at the same time.
21///
22/// # Examples
23/// ```
24/// use dashu_base::DivRemAssign;
25/// let mut n = 23;
26/// let r = n.div_rem_assign(10);
27/// assert!(n == 2 && r == 3);
28/// ```
29pub trait DivRemAssign<Rhs = Self> {
30    /// The type of the remainder.
31    type OutputRem;
32
33    /// Divide `self` by `rhs` in place, storing the quotient in `self` and returning the remainder.
34    fn div_rem_assign(&mut self, rhs: Rhs) -> Self::OutputRem;
35}
36
37/// Compute Euclidean quotient.
38///
39/// # Examples
40/// ```
41/// use dashu_base::DivEuclid;
42/// assert_eq!((-23).div_euclid(10), -3);
43/// ```
44pub trait DivEuclid<Rhs = Self> {
45    /// The type of the quotient.
46    type Output;
47
48    /// Compute the Euclidean quotient of `self / rhs`.
49    fn div_euclid(self, rhs: Rhs) -> Self::Output;
50}
51
52/// Compute Euclidean remainder.
53///
54/// # Examples
55/// ```
56/// use dashu_base::RemEuclid;
57/// assert_eq!((-23).rem_euclid(10), 7);
58/// ```
59pub trait RemEuclid<Rhs = Self> {
60    /// The type of the remainder.
61    type Output;
62
63    /// Compute the non-negative Euclidean remainder of `self % rhs`.
64    fn rem_euclid(self, rhs: Rhs) -> Self::Output;
65}
66
67/// Compute Euclidean quotient and remainder at the same time.
68///
69/// # Examples
70/// ```
71/// use dashu_base::DivRemEuclid;
72/// assert_eq!((-23).div_rem_euclid(10), (-3, 7));
73/// ```
74pub trait DivRemEuclid<Rhs = Self> {
75    /// The type of the quotient.
76    type OutputDiv;
77    /// The type of the remainder.
78    type OutputRem;
79
80    /// Compute the Euclidean quotient and remainder at the same time.
81    fn div_rem_euclid(self, rhs: Rhs) -> (Self::OutputDiv, Self::OutputRem);
82}
83
84/// Compute the greatest common divisor.
85///
86/// For negative integers, the common divisor is still kept positive.
87///
88/// # Examples
89/// ```
90/// use dashu_base::Gcd;
91/// assert_eq!(12u8.gcd(10u8), 2);
92/// ```
93///
94/// # Panics
95///
96/// Panics if both operands are zeros
97pub trait Gcd<Rhs = Self> {
98    /// The type of the greatest common divisor.
99    type Output;
100
101    /// Compute the greatest common divisor between the two operands.
102    ///
103    /// Panics if both operands are zeros
104    fn gcd(self, rhs: Rhs) -> Self::Output;
105}
106
107/// Compute the greatest common divisor between self and the other operand, and return
108/// both the common divisor `g` and the Bézout coefficients respectively.
109///
110/// For negative integers, the common divisor is still kept positive.
111///
112/// # Examples
113/// ```
114/// use dashu_base::{Gcd, ExtendedGcd};
115/// let (g, cx, cy) = 12u8.gcd_ext(10u8);
116/// assert_eq!(g, 12u8.gcd(10u8));
117/// assert_eq!(g as i8, 12 * cx + 10 * cy);
118/// ```
119///
120/// # Panics
121///
122/// Panics if both operands are zeros
123pub trait ExtendedGcd<Rhs = Self> {
124    /// The type of the greatest common divisor.
125    type OutputGcd;
126    /// The type of the Bézout coefficients.
127    type OutputCoeff;
128
129    /// Calculate the greatest common divisor between the two operands, returns
130    /// the common divisor `g` and the Bézout coefficients respectively.
131    ///
132    /// Panics if both operands are zeros
133    fn gcd_ext(self, rhs: Rhs) -> (Self::OutputGcd, Self::OutputCoeff, Self::OutputCoeff);
134}
135
136/// Computer the floored square root of the number and return the remainder at the same time.
137pub trait SquareRootRem {
138    /// The type of the (floored) root and the remainder.
139    type Output;
140
141    /// Compute the floored square root together with the remainder, so that
142    /// `root*root + rem == *self` and `0 <= rem <= 2*root`.
143    fn sqrt_rem(&self) -> (Self::Output, Self);
144}
145
146/// Computer the floored cubic root of the number and return the remainder at the same time.
147pub trait CubicRootRem {
148    /// The type of the (floored) root and the remainder.
149    type Output;
150
151    /// Compute the floored cubic root together with the remainder, so that
152    /// `root*root*root + rem == *self` and `0 <= rem < 3*root*root + 3*root`.
153    fn cbrt_rem(&self) -> (Self::Output, Self);
154}
155
156mod div_rem;
157mod gcd;
158mod root;
159pub(crate) use root::NormalizedRootRem;
dashu_base/ring/mod.rs

dashu_base/ring/
mod.rs
