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/// Exact division, re-exported from [`num-modular`](https://docs.rs/num-modular).
85///
86/// `DivExact<Rhs, Precompute>::div_exact(self, rhs, pre)` returns `Some(self / rhs)` when `rhs`
87/// divides `self` exactly and `None` otherwise. `dashu`'s implementations use the empty
88/// precomputation `Precompute = ()` (pass `&()` at the call site). For arbitrary-precision types an
89/// exact division avoids the general division's normalization and remainder computation when the
90/// divisor is small (e.g. `dashu-int` uses Hensel 2-adic division).
91pub use num_modular::{DivExact, DivExactAssign};
92
93/// Compute the greatest common divisor.
94///
95/// For negative integers, the common divisor is still kept positive.
96///
97/// # Examples
98/// ```
99/// use dashu_base::Gcd;
100/// assert_eq!(12u8.gcd(10u8), 2);
101/// ```
102///
103/// # Panics
104///
105/// Panics if both operands are zeros
106pub trait Gcd<Rhs = Self> {
107    /// The type of the greatest common divisor.
108    type Output;
109
110    /// Compute the greatest common divisor between the two operands.
111    ///
112    /// Panics if both operands are zeros
113    fn gcd(self, rhs: Rhs) -> Self::Output;
114}
115
116/// Compute the greatest common divisor between self and the other operand, and return
117/// both the common divisor `g` and the Bézout coefficients respectively.
118///
119/// For negative integers, the common divisor is still kept positive.
120///
121/// # Examples
122/// ```
123/// use dashu_base::{Gcd, ExtendedGcd};
124/// let (g, cx, cy) = 12u8.gcd_ext(10u8);
125/// assert_eq!(g, 12u8.gcd(10u8));
126/// assert_eq!(g as i8, 12 * cx + 10 * cy);
127/// ```
128///
129/// # Panics
130///
131/// Panics if both operands are zeros
132pub trait ExtendedGcd<Rhs = Self> {
133    /// The type of the greatest common divisor.
134    type OutputGcd;
135    /// The type of the Bézout coefficients.
136    type OutputCoeff;
137
138    /// Calculate the greatest common divisor between the two operands, returns
139    /// the common divisor `g` and the Bézout coefficients respectively.
140    ///
141    /// Panics if both operands are zeros
142    fn gcd_ext(self, rhs: Rhs) -> (Self::OutputGcd, Self::OutputCoeff, Self::OutputCoeff);
143}
144
145/// Computer the floored square root of the number and return the remainder at the same time.
146pub trait SquareRootRem {
147    /// The type of the (floored) root and the remainder.
148    type Output;
149
150    /// Compute the floored square root together with the remainder, so that
151    /// `root*root + rem == *self` and `0 <= rem <= 2*root`.
152    fn sqrt_rem(&self) -> (Self::Output, Self);
153}
154
155/// Computer the floored cubic root of the number and return the remainder at the same time.
156pub trait CubicRootRem {
157    /// The type of the (floored) root and the remainder.
158    type Output;
159
160    /// Compute the floored cubic root together with the remainder, so that
161    /// `root*root*root + rem == *self` and `0 <= rem < 3*root*root + 3*root`.
162    fn cbrt_rem(&self) -> (Self::Output, Self);
163}
164
165mod div_rem;
166mod gcd;
167mod root;
168pub(crate) use root::NormalizedRootRem;
dashu_base/ring/mod.rs

dashu_base/ring/
mod.rs
