1use core::ops::{Div, Rem};
2
3pub trait Euclid: Sized + Div<Self, Output = Self> + Rem<Self, Output = Self> {
4 /// Calculates Euclidean division, the matching method for `rem_euclid`.
5 ///
6 /// This computes the integer `n` such that
7 /// `self = n * v + self.rem_euclid(v)`.
8 /// In other words, the result is `self / v` rounded to the integer `n`
9 /// such that `self >= n * v`.
10 ///
11 /// # Examples
12 ///
13 /// ```
14 /// use num_traits::Euclid;
15 ///
16 /// let a: i32 = 7;
17 /// let b: i32 = 4;
18 /// assert_eq!(Euclid::div_euclid(&a, &b), 1); // 7 > 4 * 1
19 /// assert_eq!(Euclid::div_euclid(&-a, &b), -2); // -7 >= 4 * -2
20 /// assert_eq!(Euclid::div_euclid(&a, &-b), -1); // 7 >= -4 * -1
21 /// assert_eq!(Euclid::div_euclid(&-a, &-b), 2); // -7 >= -4 * 2
22 /// ```
23 fn div_euclid(&self, v: &Self) -> Self;
24
25 /// Calculates the least nonnegative remainder of `self (mod v)`.
26 ///
27 /// In particular, the return value `r` satisfies `0.0 <= r < v.abs()` in
28 /// most cases. However, due to a floating point round-off error it can
29 /// result in `r == v.abs()`, violating the mathematical definition, if
30 /// `self` is much smaller than `v.abs()` in magnitude and `self < 0.0`.
31 /// This result is not an element of the function's codomain, but it is the
32 /// closest floating point number in the real numbers and thus fulfills the
33 /// property `self == self.div_euclid(v) * v + self.rem_euclid(v)`
34 /// approximatively.
35 ///
36 /// # Examples
37 ///
38 /// ```
39 /// use num_traits::Euclid;
40 ///
41 /// let a: i32 = 7;
42 /// let b: i32 = 4;
43 /// assert_eq!(Euclid::rem_euclid(&a, &b), 3);
44 /// assert_eq!(Euclid::rem_euclid(&-a, &b), 1);
45 /// assert_eq!(Euclid::rem_euclid(&a, &-b), 3);
46 /// assert_eq!(Euclid::rem_euclid(&-a, &-b), 1);
47 /// ```
48 fn rem_euclid(&self, v: &Self) -> Self;
49
50 /// Returns both the quotient and remainder from Euclidean division.
51 ///
52 /// By default, it internally calls both `Euclid::div_euclid` and `Euclid::rem_euclid`,
53 /// but it can be overridden in order to implement some optimization.
54 ///
55 /// # Examples
56 ///
57 /// ```
58 /// # use num_traits::Euclid;
59 /// let x = 5u8;
60 /// let y = 3u8;
61 ///
62 /// let div = Euclid::div_euclid(&x, &y);
63 /// let rem = Euclid::rem_euclid(&x, &y);
64 ///
65 /// assert_eq!((div, rem), Euclid::div_rem_euclid(&x, &y));
66 /// ```
67 fn div_rem_euclid(&self, v: &Self) -> (Self, Self) {
68 (self.div_euclid(v), self.rem_euclid(v))
69 }
70}
71
72macro_rules! euclid_forward_impl {
73 ($($t:ty)*) => {$(
74 impl Euclid for $t {
75 #[inline]
76 fn div_euclid(&self, v: &$t) -> Self {
77 <$t>::div_euclid(*self, *v)
78 }
79
80 #[inline]
81 fn rem_euclid(&self, v: &$t) -> Self {
82 <$t>::rem_euclid(*self, *v)
83 }
84 }
85 )*}
86}
87
88euclid_forward_impl!(isize i8 i16 i32 i64 i128);
89euclid_forward_impl!(usize u8 u16 u32 u64 u128);
90
91#[cfg(feature = "std")]
92euclid_forward_impl!(f32 f64);
93
94#[cfg(not(feature = "std"))]
95impl Euclid for f32 {
96 #[inline]
97 fn div_euclid(&self, v: &f32) -> f32 {
98 let q = <f32 as crate::float::FloatCore>::trunc(self / v);
99 if self % v < 0.0 {
100 return if *v > 0.0 { q - 1.0 } else { q + 1.0 };
101 }
102 q
103 }
104
105 #[inline]
106 fn rem_euclid(&self, v: &f32) -> f32 {
107 let r = self % v;
108 if r < 0.0 {
109 r + <f32 as crate::float::FloatCore>::abs(*v)
110 } else {
111 r
112 }
113 }
114}
115
116#[cfg(not(feature = "std"))]
117impl Euclid for f64 {
118 #[inline]
119 fn div_euclid(&self, v: &f64) -> f64 {
120 let q = <f64 as crate::float::FloatCore>::trunc(self / v);
121 if self % v < 0.0 {
122 return if *v > 0.0 { q - 1.0 } else { q + 1.0 };
123 }
124 q
125 }
126
127 #[inline]
128 fn rem_euclid(&self, v: &f64) -> f64 {
129 let r = self % v;
130 if r < 0.0 {
131 r + <f64 as crate::float::FloatCore>::abs(*v)
132 } else {
133 r
134 }
135 }
136}
137
138pub trait CheckedEuclid: Euclid {
139 /// Performs euclid division that returns `None` instead of panicking on division by zero
140 /// and instead of wrapping around on underflow and overflow.
141 fn checked_div_euclid(&self, v: &Self) -> Option<Self>;
142
143 /// Finds the euclid remainder of dividing two numbers, checking for underflow, overflow and
144 /// division by zero. If any of that happens, `None` is returned.
145 fn checked_rem_euclid(&self, v: &Self) -> Option<Self>;
146
147 /// Returns both the quotient and remainder from checked Euclidean division.
148 ///
149 /// By default, it internally calls both `CheckedEuclid::checked_div_euclid` and `CheckedEuclid::checked_rem_euclid`,
150 /// but it can be overridden in order to implement some optimization.
151 /// # Examples
152 ///
153 /// ```
154 /// # use num_traits::CheckedEuclid;
155 /// let x = 5u8;
156 /// let y = 3u8;
157 ///
158 /// let div = CheckedEuclid::checked_div_euclid(&x, &y);
159 /// let rem = CheckedEuclid::checked_rem_euclid(&x, &y);
160 ///
161 /// assert_eq!(Some((div.unwrap(), rem.unwrap())), CheckedEuclid::checked_div_rem_euclid(&x, &y));
162 /// ```
163 fn checked_div_rem_euclid(&self, v: &Self) -> Option<(Self, Self)> {
164 Some((self.checked_div_euclid(v)?, self.checked_rem_euclid(v)?))
165 }
166}
167
168macro_rules! checked_euclid_forward_impl {
169 ($($t:ty)*) => {$(
170 impl CheckedEuclid for $t {
171 #[inline]
172 fn checked_div_euclid(&self, v: &$t) -> Option<Self> {
173 <$t>::checked_div_euclid(*self, *v)
174 }
175
176 #[inline]
177 fn checked_rem_euclid(&self, v: &$t) -> Option<Self> {
178 <$t>::checked_rem_euclid(*self, *v)
179 }
180 }
181 )*}
182}
183
184checked_euclid_forward_impl!(isize i8 i16 i32 i64 i128);
185checked_euclid_forward_impl!(usize u8 u16 u32 u64 u128);
186
187#[cfg(test)]
188mod tests {
189 use super::*;
190
191 #[test]
192 fn euclid_unsigned() {
193 macro_rules! test_euclid {
194 ($($t:ident)+) => {
195 $(
196 {
197 let x: $t = 10;
198 let y: $t = 3;
199 let div = Euclid::div_euclid(&x, &y);
200 let rem = Euclid::rem_euclid(&x, &y);
201 assert_eq!(div, 3);
202 assert_eq!(rem, 1);
203 assert_eq!((div, rem), Euclid::div_rem_euclid(&x, &y));
204 }
205 )+
206 };
207 }
208
209 test_euclid!(usize u8 u16 u32 u64);
210 }
211
212 #[test]
213 fn euclid_signed() {
214 macro_rules! test_euclid {
215 ($($t:ident)+) => {
216 $(
217 {
218 let x: $t = 10;
219 let y: $t = -3;
220 assert_eq!(Euclid::div_euclid(&x, &y), -3);
221 assert_eq!(Euclid::div_euclid(&-x, &y), 4);
222 assert_eq!(Euclid::rem_euclid(&x, &y), 1);
223 assert_eq!(Euclid::rem_euclid(&-x, &y), 2);
224 assert_eq!((Euclid::div_euclid(&x, &y), Euclid::rem_euclid(&x, &y)), Euclid::div_rem_euclid(&x, &y));
225 let x: $t = $t::min_value() + 1;
226 let y: $t = -1;
227 assert_eq!(Euclid::div_euclid(&x, &y), $t::max_value());
228 }
229 )+
230 };
231 }
232
233 test_euclid!(isize i8 i16 i32 i64 i128);
234 }
235
236 #[test]
237 fn euclid_float() {
238 macro_rules! test_euclid {
239 ($($t:ident)+) => {
240 $(
241 {
242 let x: $t = 12.1;
243 let y: $t = 3.2;
244 assert!(Euclid::div_euclid(&x, &y) * y + Euclid::rem_euclid(&x, &y) - x
245 <= 46.4 * <$t as crate::float::FloatCore>::epsilon());
246 assert!(Euclid::div_euclid(&x, &-y) * -y + Euclid::rem_euclid(&x, &-y) - x
247 <= 46.4 * <$t as crate::float::FloatCore>::epsilon());
248 assert!(Euclid::div_euclid(&-x, &y) * y + Euclid::rem_euclid(&-x, &y) + x
249 <= 46.4 * <$t as crate::float::FloatCore>::epsilon());
250 assert!(Euclid::div_euclid(&-x, &-y) * -y + Euclid::rem_euclid(&-x, &-y) + x
251 <= 46.4 * <$t as crate::float::FloatCore>::epsilon());
252 assert_eq!((Euclid::div_euclid(&x, &y), Euclid::rem_euclid(&x, &y)), Euclid::div_rem_euclid(&x, &y));
253 }
254 )+
255 };
256 }
257
258 test_euclid!(f32 f64);
259 }
260
261 #[test]
262 fn euclid_checked() {
263 macro_rules! test_euclid_checked {
264 ($($t:ident)+) => {
265 $(
266 {
267 assert_eq!(CheckedEuclid::checked_div_euclid(&$t::min_value(), &-1), None);
268 assert_eq!(CheckedEuclid::checked_rem_euclid(&$t::min_value(), &-1), None);
269 assert_eq!(CheckedEuclid::checked_div_euclid(&1, &0), None);
270 assert_eq!(CheckedEuclid::checked_rem_euclid(&1, &0), None);
271 }
272 )+
273 };
274 }
275
276 test_euclid_checked!(isize i8 i16 i32 i64 i128);
277 }
278}
279