num_traits/ops/
euclid.rs

Help
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        #[cfg(has_div_euclid)]
75        impl Euclid for $t {
76            #[inline]
77            fn div_euclid(&self, v: &$t) -> Self {
78                <$t>::div_euclid(*self, *v)
79            }
80
81            #[inline]
82            fn rem_euclid(&self, v: &$t) -> Self {
83                <$t>::rem_euclid(*self, *v)
84            }
85        }
86    )*}
87}
88
89macro_rules! euclid_int_impl {
90    ($($t:ty)*) => {$(
91        euclid_forward_impl!($t);
92
93        #[cfg(not(has_div_euclid))]
94        impl Euclid for $t {
95            #[inline]
96            fn div_euclid(&self, v: &$t) -> Self {
97                let q = self / v;
98                if self % v < 0 {
99                    return if *v > 0 { q - 1 } else { q + 1 }
100                }
101                q
102            }
103
104            #[inline]
105            fn rem_euclid(&self, v: &$t) -> Self {
106                let r = self % v;
107                if r < 0 {
108                    if *v < 0 {
109                        r - v
110                    } else {
111                        r + v
112                    }
113                } else {
114                    r
115                }
116            }
117        }
118    )*}
119}
120
121macro_rules! euclid_uint_impl {
122    ($($t:ty)*) => {$(
123        euclid_forward_impl!($t);
124
125        #[cfg(not(has_div_euclid))]
126        impl Euclid for $t {
127            #[inline]
128            fn div_euclid(&self, v: &$t) -> Self {
129                self / v
130            }
131
132            #[inline]
133            fn rem_euclid(&self, v: &$t) -> Self {
134                self % v
135            }
136        }
137    )*}
138}
139
140euclid_int_impl!(isize i8 i16 i32 i64 i128);
141euclid_uint_impl!(usize u8 u16 u32 u64 u128);
142
143#[cfg(all(has_div_euclid, feature = "std"))]
144euclid_forward_impl!(f32 f64);
145
146#[cfg(not(all(has_div_euclid, feature = "std")))]
147impl Euclid for f32 {
148    #[inline]
149    fn div_euclid(&self, v: &f32) -> f32 {
150        let q = <f32 as crate::float::FloatCore>::trunc(self / v);
151        if self % v < 0.0 {
152            return if *v > 0.0 { q - 1.0 } else { q + 1.0 };
153        }
154        q
155    }
156
157    #[inline]
158    fn rem_euclid(&self, v: &f32) -> f32 {
159        let r = self % v;
160        if r < 0.0 {
161            r + <f32 as crate::float::FloatCore>::abs(*v)
162        } else {
163            r
164        }
165    }
166}
167
168#[cfg(not(all(has_div_euclid, feature = "std")))]
169impl Euclid for f64 {
170    #[inline]
171    fn div_euclid(&self, v: &f64) -> f64 {
172        let q = <f64 as crate::float::FloatCore>::trunc(self / v);
173        if self % v < 0.0 {
174            return if *v > 0.0 { q - 1.0 } else { q + 1.0 };
175        }
176        q
177    }
178
179    #[inline]
180    fn rem_euclid(&self, v: &f64) -> f64 {
181        let r = self % v;
182        if r < 0.0 {
183            r + <f64 as crate::float::FloatCore>::abs(*v)
184        } else {
185            r
186        }
187    }
188}
189
190pub trait CheckedEuclid: Euclid {
191    /// Performs euclid division that returns `None` instead of panicking on division by zero
192    /// and instead of wrapping around on underflow and overflow.
193    fn checked_div_euclid(&self, v: &Self) -> Option<Self>;
194
195    /// Finds the euclid remainder of dividing two numbers, checking for underflow, overflow and
196    /// division by zero. If any of that happens, `None` is returned.
197    fn checked_rem_euclid(&self, v: &Self) -> Option<Self>;
198
199    /// Returns both the quotient and remainder from checked Euclidean division.
200    ///
201    /// By default, it internally calls both `CheckedEuclid::checked_div_euclid` and `CheckedEuclid::checked_rem_euclid`,
202    /// but it can be overridden in order to implement some optimization.
203    /// # Examples
204    ///
205    /// ```
206    /// # use num_traits::CheckedEuclid;
207    /// let x = 5u8;
208    /// let y = 3u8;
209    ///
210    /// let div = CheckedEuclid::checked_div_euclid(&x, &y);
211    /// let rem = CheckedEuclid::checked_rem_euclid(&x, &y);
212    ///
213    /// assert_eq!(Some((div.unwrap(), rem.unwrap())), CheckedEuclid::checked_div_rem_euclid(&x, &y));
214    /// ```
215    fn checked_div_rem_euclid(&self, v: &Self) -> Option<(Self, Self)> {
216        Some((self.checked_div_euclid(v)?, self.checked_rem_euclid(v)?))
217    }
218}
219
220macro_rules! checked_euclid_forward_impl {
221    ($($t:ty)*) => {$(
222        #[cfg(has_div_euclid)]
223        impl CheckedEuclid for $t {
224            #[inline]
225            fn checked_div_euclid(&self, v: &$t) -> Option<Self> {
226                <$t>::checked_div_euclid(*self, *v)
227            }
228
229            #[inline]
230            fn checked_rem_euclid(&self, v: &$t) -> Option<Self> {
231                <$t>::checked_rem_euclid(*self, *v)
232            }
233        }
234    )*}
235}
236
237macro_rules! checked_euclid_int_impl {
238    ($($t:ty)*) => {$(
239        checked_euclid_forward_impl!($t);
240
241        #[cfg(not(has_div_euclid))]
242        impl CheckedEuclid for $t {
243            #[inline]
244            fn checked_div_euclid(&self, v: &$t) -> Option<$t> {
245                if *v == 0 || (*self == Self::min_value() && *v == -1) {
246                    None
247                } else {
248                    Some(Euclid::div_euclid(self, v))
249                }
250            }
251
252            #[inline]
253            fn checked_rem_euclid(&self, v: &$t) -> Option<$t> {
254                if *v == 0 || (*self == Self::min_value() && *v == -1) {
255                    None
256                } else {
257                    Some(Euclid::rem_euclid(self, v))
258                }
259            }
260        }
261    )*}
262}
263
264macro_rules! checked_euclid_uint_impl {
265    ($($t:ty)*) => {$(
266        checked_euclid_forward_impl!($t);
267
268        #[cfg(not(has_div_euclid))]
269        impl CheckedEuclid for $t {
270            #[inline]
271            fn checked_div_euclid(&self, v: &$t) -> Option<$t> {
272                if *v == 0 {
273                    None
274                } else {
275                    Some(Euclid::div_euclid(self, v))
276                }
277            }
278
279            #[inline]
280            fn checked_rem_euclid(&self, v: &$t) -> Option<$t> {
281                if *v == 0 {
282                    None
283                } else {
284                    Some(Euclid::rem_euclid(self, v))
285                }
286            }
287        }
288    )*}
289}
290
291checked_euclid_int_impl!(isize i8 i16 i32 i64 i128);
292checked_euclid_uint_impl!(usize u8 u16 u32 u64 u128);
293
294#[cfg(test)]
295mod tests {
296    use super::*;
297
298    #[test]
299    fn euclid_unsigned() {
300        macro_rules! test_euclid {
301            ($($t:ident)+) => {
302                $(
303                    {
304                        let x: $t = 10;
305                        let y: $t = 3;
306                        let div = Euclid::div_euclid(&x, &y);
307                        let rem = Euclid::rem_euclid(&x, &y);
308                        assert_eq!(div, 3);
309                        assert_eq!(rem, 1);
310                        assert_eq!((div, rem), Euclid::div_rem_euclid(&x, &y));
311                    }
312                )+
313            };
314        }
315
316        test_euclid!(usize u8 u16 u32 u64);
317    }
318
319    #[test]
320    fn euclid_signed() {
321        macro_rules! test_euclid {
322            ($($t:ident)+) => {
323                $(
324                    {
325                        let x: $t = 10;
326                        let y: $t = -3;
327                        assert_eq!(Euclid::div_euclid(&x, &y), -3);
328                        assert_eq!(Euclid::div_euclid(&-x, &y), 4);
329                        assert_eq!(Euclid::rem_euclid(&x, &y), 1);
330                        assert_eq!(Euclid::rem_euclid(&-x, &y), 2);
331                        assert_eq!((Euclid::div_euclid(&x, &y), Euclid::rem_euclid(&x, &y)), Euclid::div_rem_euclid(&x, &y));
332                        let x: $t = $t::min_value() + 1;
333                        let y: $t = -1;
334                        assert_eq!(Euclid::div_euclid(&x, &y), $t::max_value());
335                    }
336                )+
337            };
338        }
339
340        test_euclid!(isize i8 i16 i32 i64 i128);
341    }
342
343    #[test]
344    fn euclid_float() {
345        macro_rules! test_euclid {
346            ($($t:ident)+) => {
347                $(
348                    {
349                        let x: $t = 12.1;
350                        let y: $t = 3.2;
351                        assert!(Euclid::div_euclid(&x, &y) * y + Euclid::rem_euclid(&x, &y) - x
352                        <= 46.4 * <$t as crate::float::FloatCore>::epsilon());
353                        assert!(Euclid::div_euclid(&x, &-y) * -y + Euclid::rem_euclid(&x, &-y) - x
354                        <= 46.4 * <$t as crate::float::FloatCore>::epsilon());
355                        assert!(Euclid::div_euclid(&-x, &y) * y + Euclid::rem_euclid(&-x, &y) + x
356                        <= 46.4 * <$t as crate::float::FloatCore>::epsilon());
357                        assert!(Euclid::div_euclid(&-x, &-y) * -y + Euclid::rem_euclid(&-x, &-y) + x
358                        <= 46.4 * <$t as crate::float::FloatCore>::epsilon());
359                        assert_eq!((Euclid::div_euclid(&x, &y), Euclid::rem_euclid(&x, &y)), Euclid::div_rem_euclid(&x, &y));
360                    }
361                )+
362            };
363        }
364
365        test_euclid!(f32 f64);
366    }
367
368    #[test]
369    fn euclid_checked() {
370        macro_rules! test_euclid_checked {
371            ($($t:ident)+) => {
372                $(
373                    {
374                        assert_eq!(CheckedEuclid::checked_div_euclid(&$t::min_value(), &-1), None);
375                        assert_eq!(CheckedEuclid::checked_rem_euclid(&$t::min_value(), &-1), None);
376                        assert_eq!(CheckedEuclid::checked_div_euclid(&1, &0), None);
377                        assert_eq!(CheckedEuclid::checked_rem_euclid(&1, &0), None);
378                    }
379                )+
380            };
381        }
382
383        test_euclid_checked!(isize i8 i16 i32 i64 i128);
384    }
385}
num_traits/ops/euclid.rs

num_traits/ops/
euclid.rs
