dashu_int/
div_ops.rs

1//! Division operators.
2
3use crate::{
4    helper_macros,
5    ibig::IBig,
6    ops::{DivEuclid, DivRem, DivRemAssign, DivRemEuclid, RemEuclid},
7    ubig::UBig,
8    Sign::*,
9};
10use core::ops::{Div, DivAssign, Rem, RemAssign};
11
12// Ops for UBig
13
14helper_macros::forward_ubig_binop_to_repr!(impl Div, div);
15helper_macros::forward_ubig_binop_to_repr!(impl Rem, rem);
16helper_macros::forward_ubig_binop_to_repr!(impl DivEuclid, div_euclid, div);
17helper_macros::forward_ubig_binop_to_repr!(impl RemEuclid, rem_euclid, rem);
18helper_macros::impl_binop_assign_by_taking!(impl DivAssign<UBig> for UBig, div_assign, div);
19helper_macros::impl_binop_assign_by_taking!(impl RemAssign<UBig> for UBig, rem_assign, rem);
20
21macro_rules! impl_ubig_divrem {
22    ($repr0:ident, $repr1:ident) => {{
23        let (q, r) = $repr0.div_rem($repr1);
24        (UBig(q), UBig(r))
25    }};
26}
27helper_macros::forward_ubig_binop_to_repr!(
28    impl DivRem, div_rem -> (UBig, UBig),
29    OutputDiv = UBig, OutputRem = UBig,
30    impl_ubig_divrem
31);
32helper_macros::forward_ubig_binop_to_repr!(
33    impl DivRemEuclid,
34    div_rem_euclid -> (UBig, UBig),
35    OutputDiv = UBig, OutputRem = UBig,
36    impl_ubig_divrem
37);
38helper_macros::impl_binop_assign_by_taking!(
39    impl DivRemAssign<UBig> for UBig, div_rem_assign,
40    OutputRem = UBig, div_rem
41);
42
43// Ops for IBig
44
45macro_rules! impl_ibig_div {
46    ($sign0:ident, $mag0:ident, $sign1:ident, $mag1:ident) => {
47        // truncate towards 0.
48        IBig(($mag0 / $mag1).with_sign($sign0 * $sign1))
49    };
50}
51macro_rules! impl_ibig_rem {
52    ($sign0:ident, $mag0:ident, $sign1:ident, $mag1:ident) => {{
53        let _unused = $sign1;
54
55        // remainder with truncating division has same sign as lhs.
56        IBig(($mag0 % $mag1).with_sign($sign0))
57    }};
58}
59helper_macros::forward_ibig_binop_to_repr!(impl Div, div, Output = IBig, impl_ibig_div);
60helper_macros::forward_ibig_binop_to_repr!(impl Rem, rem, Output = IBig, impl_ibig_rem);
61helper_macros::impl_binop_assign_by_taking!(impl DivAssign<IBig> for IBig, div_assign, div);
62helper_macros::impl_binop_assign_by_taking!(impl RemAssign<IBig> for IBig, rem_assign, rem);
63
64macro_rules! impl_ibig_divrem {
65    ($sign0:ident, $mag0:ident, $sign1:ident, $mag1:ident) => {{
66        // truncate towards 0.
67        let (q, r) = $mag0.div_rem($mag1);
68        (IBig(q.with_sign($sign0 * $sign1)), IBig(r.with_sign($sign0)))
69    }};
70}
71helper_macros::forward_ibig_binop_to_repr!(
72    impl DivRem, div_rem -> (IBig, IBig),
73    OutputDiv = IBig, OutputRem = IBig,
74    impl_ibig_divrem
75);
76
77macro_rules! impl_ibig_div_euclid {
78    ($sign0:ident, $mag0:ident, $sign1:ident, $mag1:ident) => {{
79        let (q, r) = $mag0.div_rem($mag1);
80        let q = match ($sign0, r.is_zero()) {
81            (Positive, _) | (Negative, true) => q,
82            (Negative, false) => q.into_typed().add_one(),
83        };
84        IBig(q.with_sign($sign0 * $sign1))
85    }};
86}
87macro_rules! impl_ibig_rem_euclid {
88    ($sign0:ident, $mag0:ident, $sign1:ident, $mag1:ident) => {{
89        let _unused = $sign1;
90        let repr = match $sign0 {
91            Positive => $mag0 % $mag1,
92            Negative => {
93                let r = $mag0 % $mag1.as_ref();
94                if r.is_zero() {
95                    r
96                } else {
97                    $mag1 - r.into_typed()
98                }
99            }
100        };
101        UBig(repr)
102    }};
103}
104helper_macros::forward_ibig_binop_to_repr!(
105    impl DivEuclid,
106    div_euclid,
107    Output = IBig,
108    impl_ibig_div_euclid
109);
110helper_macros::forward_ibig_binop_to_repr!(
111    impl RemEuclid,
112    rem_euclid,
113    Output = UBig,
114    impl_ibig_rem_euclid
115);
116
117macro_rules! impl_ibig_divrem_euclid {
118    ($sign0:ident, $mag0:ident, $sign1:ident, $mag1:ident) => {
119        match $sign0 {
120            Positive => {
121                let (q, r) = $mag0.div_rem($mag1);
122                (IBig(q.with_sign($sign1)), UBig(r))
123            }
124            Negative => {
125                let (mut q, mut r) = $mag0.div_rem($mag1.as_ref());
126                if !r.is_zero() {
127                    q = q.into_typed().add_one();
128                    r = $mag1 - r.into_typed();
129                }
130                (IBig(q.with_sign(-$sign1)), UBig(r))
131            }
132        }
133    };
134}
135helper_macros::forward_ibig_binop_to_repr!(
136    impl DivRemEuclid, div_rem_euclid -> (IBig, UBig),
137    OutputDiv = IBig, OutputRem = UBig,
138    impl_ibig_divrem_euclid
139);
140helper_macros::impl_binop_assign_by_taking!(
141    impl DivRemAssign<IBig> for IBig, div_rem_assign,
142    OutputRem = IBig, div_rem
143);
144
145// Ops between UBig & IBig
146
147macro_rules! impl_ubig_ibig_rem {
148    ($sign0:ident, $mag0:ident, $sign1:ident, $mag1:ident) => {{
149        debug_assert_eq!($sign0, Positive);
150        let _unused = $sign1;
151        UBig($mag0 % $mag1)
152    }};
153}
154macro_rules! impl_ubig_ibig_divrem {
155    ($sign0:ident, $mag0:ident, $sign1:ident, $mag1:ident) => {{
156        debug_assert_eq!($sign0, Positive);
157        let (q, r) = $mag0.div_rem($mag1);
158        (IBig(q.with_sign($sign1)), UBig(r))
159    }};
160}
161helper_macros::forward_ubig_ibig_binop_to_repr!(impl Div, div, Output = IBig, impl_ibig_div);
162helper_macros::forward_ubig_ibig_binop_to_repr!(impl Rem, rem, Output = UBig, impl_ubig_ibig_rem);
163helper_macros::forward_ubig_ibig_binop_to_repr!(impl DivRem, div_rem -> (IBig, UBig), OutputDiv = IBig, OutputRem = UBig, impl_ubig_ibig_divrem);
164helper_macros::impl_binop_assign_by_taking!(impl RemAssign<IBig> for UBig, rem_assign, rem);
165helper_macros::forward_ibig_ubig_binop_to_repr!(impl Div, div, Output = IBig, impl_ibig_div);
166helper_macros::forward_ibig_ubig_binop_to_repr!(impl Rem, rem, Output = IBig, impl_ibig_rem);
167helper_macros::forward_ibig_ubig_binop_to_repr!(impl DivRem, div_rem -> (IBig, IBig), OutputDiv = IBig, OutputRem = IBig, impl_ibig_divrem);
168helper_macros::impl_binop_assign_by_taking!(impl DivAssign<UBig> for IBig, div_assign, div);
169helper_macros::impl_binop_assign_by_taking!(impl RemAssign<UBig> for IBig, rem_assign, rem);
170
171// Ops with primitives
172
173macro_rules! impl_divrem_with_primitive {
174    (impl <$target:ty> for $t:ty) => {
175        impl DivRem<$target> for $t {
176            type OutputDiv = $t;
177            type OutputRem = $target;
178
179            #[inline]
180            fn div_rem(self, rhs: $target) -> ($t, $target) {
181                let (q, r) = self.div_rem(<$t>::from(rhs));
182                (q, r.try_into().unwrap())
183            }
184        }
185
186        impl<'l> DivRem<$target> for &'l $t {
187            type OutputDiv = $t;
188            type OutputRem = $target;
189
190            #[inline]
191            fn div_rem(self, rhs: $target) -> ($t, $target) {
192                let (q, r) = self.div_rem(<$t>::from(rhs));
193                (q, r.try_into().unwrap())
194            }
195        }
196
197        impl<'r> DivRem<&'r $target> for $t {
198            type OutputDiv = $t;
199            type OutputRem = $target;
200
201            #[inline]
202            fn div_rem(self, rhs: &$target) -> ($t, $target) {
203                let (q, r) = self.div_rem(<$t>::from(*rhs));
204                (q, r.try_into().unwrap())
205            }
206        }
207
208        impl<'l, 'r> DivRem<&'r $target> for &'l $t {
209            type OutputDiv = $t;
210            type OutputRem = $target;
211
212            #[inline]
213            fn div_rem(self, rhs: &$target) -> ($t, $target) {
214                let (q, r) = self.div_rem(<$t>::from(*rhs));
215                (q, r.try_into().unwrap())
216            }
217        }
218    };
219}
220
221macro_rules! impl_div_by_primitive {
222    (impl <$target:ty> for $t:ty) => {
223        impl Div<$t> for $target {
224            type Output = $target;
225
226            #[inline]
227            fn div(self, rhs: $t) -> $target {
228                <$t>::from(self).div(rhs).try_into().unwrap()
229            }
230        }
231
232        impl<'l> Div<$t> for &'l $target {
233            type Output = $target;
234
235            #[inline]
236            fn div(self, rhs: $t) -> $target {
237                <$t>::from(*self).div(rhs).try_into().unwrap()
238            }
239        }
240
241        impl<'r> Div<&'r $t> for $target {
242            type Output = $target;
243
244            #[inline]
245            fn div(self, rhs: &$t) -> $target {
246                <$t>::from(self).div(rhs).try_into().unwrap()
247            }
248        }
249
250        impl<'l, 'r> Div<&'r $t> for &'l $target {
251            type Output = $target;
252
253            #[inline]
254            fn div(self, rhs: &$t) -> $target {
255                <$t>::from(*self).div(rhs).try_into().unwrap()
256            }
257        }
258    };
259}
260
261macro_rules! impl_div_primitive_with_ubig {
262    ($($t:ty)*) => {$(
263        helper_macros::impl_binop_with_primitive!(impl Div<$t> for UBig, div);
264        impl_div_by_primitive!(impl <$t> for UBig);
265        helper_macros::impl_binop_with_primitive!(impl Rem<$t> for UBig, rem -> $t);
266        helper_macros::impl_binop_assign_with_primitive!(impl DivAssign<$t> for UBig, div_assign);
267
268        impl_divrem_with_primitive!(impl <$t> for UBig);
269        helper_macros::impl_binop_assign_with_primitive!(impl DivRemAssign<$t> for UBig, div_rem_assign, OutputRem = $t);
270    )*};
271}
272impl_div_primitive_with_ubig!(u8 u16 u32 u64 u128 usize);
273
274macro_rules! impl_div_primitive_with_ibig {
275    ($($t:ty)*) => {$(
276        helper_macros::impl_binop_with_primitive!(impl Div<$t> for IBig, div);
277        impl_div_by_primitive!(impl <$t> for IBig);
278        helper_macros::impl_binop_with_primitive!(impl Rem<$t> for IBig, rem -> $t);
279        helper_macros::impl_binop_assign_with_primitive!(impl DivAssign<$t> for IBig, div_assign);
280
281        impl_divrem_with_primitive!(impl <$t> for IBig);
282        helper_macros::impl_binop_assign_with_primitive!(impl DivRemAssign<$t> for IBig, div_rem_assign, OutputRem = $t);
283    )*};
284}
285impl_div_primitive_with_ibig!(u8 u16 u32 u64 u128 usize i8 i16 i32 i64 i128 isize);
286
287pub(crate) mod repr {
288    use super::*;
289    use crate::{
290        arch::word::{DoubleWord, Word},
291        buffer::Buffer,
292        div,
293        error::panic_divide_by_0,
294        helper_macros::debug_assert_zero,
295        memory::MemoryAllocation,
296        primitive::shrink_dword,
297        repr::{
298            Repr,
299            TypedRepr::{self, *},
300            TypedReprRef::{self, *},
301        },
302        shift,
303    };
304
305    impl DivRem<TypedRepr> for TypedRepr {
306        type OutputDiv = Repr;
307        type OutputRem = Repr;
308
309        #[inline]
310        fn div_rem(self, rhs: TypedRepr) -> (Repr, Repr) {
311            match (self, rhs) {
312                (Small(dword0), Small(dword1)) => div_rem_dword(dword0, dword1),
313                (Small(dword0), Large(_)) => (Repr::zero(), Repr::from_dword(dword0)),
314                (Large(buffer0), Small(dword1)) => div_rem_large_dword(buffer0, dword1),
315                (Large(buffer0), Large(buffer1)) => {
316                    if buffer0.len() >= buffer1.len() {
317                        div_rem_large(buffer0, buffer1)
318                    } else {
319                        (Repr::zero(), Repr::from_buffer(buffer0))
320                    }
321                }
322            }
323        }
324    }
325
326    impl<'l> DivRem<TypedRepr> for TypedReprRef<'l> {
327        type OutputDiv = Repr;
328        type OutputRem = Repr;
329
330        #[inline]
331        fn div_rem(self, rhs: TypedRepr) -> (Repr, Repr) {
332            match (self, rhs) {
333                (RefSmall(dword0), Small(dword1)) => div_rem_dword(dword0, dword1),
334                (RefSmall(dword0), Large(_)) => (Repr::zero(), Repr::from_dword(dword0)),
335                (RefLarge(words0), Small(dword1)) => div_rem_large_dword(words0.into(), dword1),
336                (RefLarge(words0), Large(mut buffer1)) => {
337                    if words0.len() >= buffer1.len() {
338                        div_rem_large(words0.into(), buffer1)
339                    } else {
340                        // Reuse buffer1 for the remainder.
341                        buffer1.clone_from_slice(words0);
342                        (Repr::zero(), Repr::from_buffer(buffer1))
343                    }
344                }
345            }
346        }
347    }
348
349    impl<'r> DivRem<TypedReprRef<'r>> for TypedRepr {
350        type OutputDiv = Repr;
351        type OutputRem = Repr;
352
353        #[inline]
354        fn div_rem(self, rhs: TypedReprRef) -> (Repr, Repr) {
355            match (self, rhs) {
356                (Small(dword0), RefSmall(dword1)) => div_rem_dword(dword0, dword1),
357                (Small(dword0), RefLarge(_)) => (Repr::zero(), Repr::from_dword(dword0)),
358                (Large(buffer0), RefSmall(dword1)) => div_rem_large_dword(buffer0, dword1),
359                (Large(buffer0), RefLarge(words1)) => {
360                    if buffer0.len() >= words1.len() {
361                        div_rem_large(buffer0, words1.into())
362                    } else {
363                        (Repr::zero(), Repr::from_buffer(buffer0))
364                    }
365                }
366            }
367        }
368    }
369
370    impl<'l, 'r> DivRem<TypedReprRef<'r>> for TypedReprRef<'l> {
371        type OutputDiv = Repr;
372        type OutputRem = Repr;
373
374        #[inline]
375        fn div_rem(self, rhs: TypedReprRef) -> (Repr, Repr) {
376            match (self, rhs) {
377                (RefSmall(dword0), RefSmall(dword1)) => div_rem_dword(dword0, dword1),
378                (RefSmall(dword0), RefLarge(_)) => (Repr::zero(), Repr::from_dword(dword0)),
379                (RefLarge(words0), RefSmall(dword1)) => div_rem_large_dword(words0.into(), dword1),
380                (RefLarge(words0), RefLarge(words1)) => {
381                    if words0.len() >= words1.len() {
382                        div_rem_large(words0.into(), words1.into())
383                    } else {
384                        (Repr::zero(), Repr::from_buffer(words0.into()))
385                    }
386                }
387            }
388        }
389    }
390
391    #[inline]
392    fn div_rem_dword(lhs: DoubleWord, rhs: DoubleWord) -> (Repr, Repr) {
393        // If division works, remainder also works.
394        match lhs.checked_div(rhs) {
395            Some(res) => (Repr::from_dword(res), Repr::from_dword(lhs % rhs)),
396            None => panic_divide_by_0(),
397        }
398    }
399
400    fn div_rem_large_dword(mut buffer: Buffer, rhs: DoubleWord) -> (Repr, Repr) {
401        if rhs == 0 {
402            panic_divide_by_0();
403        }
404        if let Some(word) = shrink_dword(rhs) {
405            let rem = div::div_by_word_in_place(&mut buffer, word);
406            (Repr::from_buffer(buffer), Repr::from_word(rem))
407        } else {
408            let rem = div::div_by_dword_in_place(&mut buffer, rhs);
409            (Repr::from_buffer(buffer), Repr::from_dword(rem))
410        }
411    }
412
413    fn div_rem_large(mut lhs: Buffer, mut rhs: Buffer) -> (Repr, Repr) {
414        let shift = div_rem_in_lhs(&mut lhs, &mut rhs);
415        let n = rhs.len();
416        rhs.copy_from_slice(&lhs[..n]);
417        debug_assert_zero!(shift::shr_in_place(&mut rhs, shift));
418        lhs.erase_front(n);
419        (Repr::from_buffer(lhs), Repr::from_buffer(rhs))
420    }
421
422    /// lhs = [lhs % rhs, lhs / rhs]
423    ///
424    /// Returns the number of shift bits produced by normalization.
425    #[inline]
426    fn div_rem_in_lhs(lhs: &mut Buffer, rhs: &mut Buffer) -> u32 {
427        let mut allocation =
428            MemoryAllocation::new(div::memory_requirement_exact(lhs.len(), rhs.len()));
429        let (shift, fast_div_top) = div::normalize(rhs);
430        let quo_carry = div::div_rem_unshifted_in_place(
431            lhs,
432            rhs,
433            shift,
434            fast_div_top,
435            &mut allocation.memory(),
436        );
437        lhs.push_resizing(quo_carry);
438        shift
439    }
440
441    impl Div<TypedRepr> for TypedRepr {
442        type Output = Repr;
443
444        #[inline]
445        fn div(self, rhs: TypedRepr) -> Repr {
446            match (self, rhs) {
447                (Small(dword0), Small(dword1)) => div_dword(dword0, dword1),
448                (Small(_), Large(_)) => Repr::zero(),
449                (Large(buffer0), Small(dword1)) => div_large_dword(buffer0, dword1),
450                (Large(buffer0), Large(buffer1)) => {
451                    if buffer0.len() >= buffer1.len() {
452                        div_large(buffer0, buffer1)
453                    } else {
454                        Repr::zero()
455                    }
456                }
457            }
458        }
459    }
460
461    impl<'r> Div<TypedReprRef<'r>> for TypedRepr {
462        type Output = Repr;
463
464        #[inline]
465        fn div(self, rhs: TypedReprRef<'r>) -> Repr {
466            match (self, rhs) {
467                (Small(dword0), RefSmall(dword1)) => div_dword(dword0, dword1),
468                (Small(_), RefLarge(_)) => Repr::zero(),
469                (Large(buffer0), RefSmall(dword1)) => div_large_dword(buffer0, dword1),
470                (Large(buffer0), RefLarge(words1)) => {
471                    if buffer0.len() >= words1.len() {
472                        div_large(buffer0, words1.into())
473                    } else {
474                        Repr::zero()
475                    }
476                }
477            }
478        }
479    }
480
481    impl<'l> Div<TypedRepr> for TypedReprRef<'l> {
482        type Output = Repr;
483
484        #[inline]
485        fn div(self, rhs: TypedRepr) -> Repr {
486            match (self, rhs) {
487                (RefSmall(dword0), Small(dword1)) => div_dword(dword0, dword1),
488                (RefSmall(_), Large(_)) => Repr::zero(),
489                (RefLarge(words0), Small(dword1)) => div_large_dword(words0.into(), dword1),
490                (RefLarge(words1), Large(buffer1)) => {
491                    if words1.len() >= buffer1.len() {
492                        div_large(words1.into(), buffer1)
493                    } else {
494                        Repr::zero()
495                    }
496                }
497            }
498        }
499    }
500
501    impl<'l, 'r> Div<TypedReprRef<'r>> for TypedReprRef<'l> {
502        type Output = Repr;
503
504        #[inline]
505        fn div(self, rhs: TypedReprRef) -> Repr {
506            match (self, rhs) {
507                (RefSmall(dword0), RefSmall(dword1)) => div_dword(dword0, dword1),
508                (RefSmall(_), RefLarge(_)) => Repr::zero(),
509                (RefLarge(words0), RefSmall(dword1)) => div_large_dword(words0.into(), dword1),
510                (RefLarge(words0), RefLarge(words1)) => {
511                    if words0.len() >= words1.len() {
512                        div_large(words0.into(), words1.into())
513                    } else {
514                        Repr::zero()
515                    }
516                }
517            }
518        }
519    }
520
521    #[inline]
522    fn div_dword(lhs: DoubleWord, rhs: DoubleWord) -> Repr {
523        match lhs.checked_div(rhs) {
524            Some(res) => Repr::from_dword(res),
525            None => panic_divide_by_0(),
526        }
527    }
528
529    #[inline]
530    fn div_large_dword(lhs: Buffer, rhs: DoubleWord) -> Repr {
531        let (q, _) = div_rem_large_dword(lhs, rhs);
532        q
533    }
534
535    fn div_large(mut lhs: Buffer, mut rhs: Buffer) -> Repr {
536        let _shift = div_rem_in_lhs(&mut lhs, &mut rhs);
537        lhs.erase_front(rhs.len());
538        Repr::from_buffer(lhs)
539    }
540
541    impl Rem<TypedRepr> for TypedRepr {
542        type Output = Repr;
543
544        #[inline]
545        fn rem(self, rhs: TypedRepr) -> Repr {
546            match (self, rhs) {
547                (Small(dword0), Small(dword1)) => rem_dword(dword0, dword1),
548                (Small(dword0), Large(_)) => Repr::from_dword(dword0),
549                (Large(buffer0), Small(dword1)) => rem_large_dword(&buffer0, dword1),
550                (Large(buffer0), Large(buffer1)) => {
551                    if buffer0.len() >= buffer1.len() {
552                        rem_large(buffer0, buffer1)
553                    } else {
554                        Repr::from_buffer(buffer0)
555                    }
556                }
557            }
558        }
559    }
560
561    impl<'r> Rem<TypedReprRef<'r>> for TypedRepr {
562        type Output = Repr;
563
564        #[inline]
565        fn rem(self, rhs: TypedReprRef) -> Repr {
566            match (self, rhs) {
567                (Small(dword0), RefSmall(dword1)) => rem_dword(dword0, dword1),
568                (Small(dword0), RefLarge(_)) => Repr::from_dword(dword0),
569                (Large(buffer0), RefSmall(dword1)) => rem_large_dword(&buffer0, dword1),
570                (Large(buffer0), RefLarge(words1)) => {
571                    if buffer0.len() >= words1.len() {
572                        rem_large(buffer0, words1.into())
573                    } else {
574                        Repr::from_buffer(buffer0)
575                    }
576                }
577            }
578        }
579    }
580
581    impl<'l> Rem<TypedRepr> for TypedReprRef<'l> {
582        type Output = Repr;
583
584        #[inline]
585        fn rem(self, rhs: TypedRepr) -> Repr {
586            match (self, rhs) {
587                (RefSmall(dword0), Small(dword1)) => rem_dword(dword0, dword1),
588                (RefSmall(dword0), Large(_)) => Repr::from_dword(dword0),
589                (RefLarge(words0), Small(dword1)) => rem_large_dword(words0, dword1),
590                (RefLarge(words0), Large(mut buffer1)) => {
591                    if words0.len() >= buffer1.len() {
592                        rem_large(words0.into(), buffer1)
593                    } else {
594                        // Reuse buffer1 for the remainder.
595                        buffer1.clone_from_slice(words0);
596                        Repr::from_buffer(buffer1)
597                    }
598                }
599            }
600        }
601    }
602
603    impl<'l, 'r> Rem<TypedReprRef<'r>> for TypedReprRef<'l> {
604        type Output = Repr;
605
606        #[inline]
607        fn rem(self, rhs: TypedReprRef) -> Repr {
608            match (self, rhs) {
609                (RefSmall(dword0), RefSmall(dword1)) => rem_dword(dword0, dword1),
610                (RefSmall(dword0), RefLarge(_)) => Repr::from_dword(dword0),
611                (RefLarge(words0), RefSmall(dword1)) => rem_large_dword(words0, dword1),
612                (RefLarge(words0), RefLarge(words1)) => {
613                    if words0.len() >= words1.len() {
614                        rem_large(words0.into(), words1.into())
615                    } else {
616                        Repr::from_buffer(words0.into())
617                    }
618                }
619            }
620        }
621    }
622
623    #[inline]
624    fn rem_dword(lhs: DoubleWord, rhs: DoubleWord) -> Repr {
625        match lhs.checked_rem(rhs) {
626            Some(res) => Repr::from_dword(res),
627            None => panic_divide_by_0(),
628        }
629    }
630
631    #[inline]
632    fn rem_large_dword(lhs: &[Word], rhs: DoubleWord) -> Repr {
633        if rhs == 0 {
634            panic_divide_by_0();
635        }
636        if let Some(word) = shrink_dword(rhs) {
637            Repr::from_word(div::rem_by_word(lhs, word))
638        } else {
639            Repr::from_dword(div::rem_by_dword(lhs, rhs))
640        }
641    }
642
643    pub(crate) fn rem_large(mut lhs: Buffer, mut rhs: Buffer) -> Repr {
644        let shift = div_rem_in_lhs(&mut lhs, &mut rhs);
645        let n = rhs.len();
646        rhs.copy_from_slice(&lhs[..n]);
647        debug_assert_zero!(shift::shr_in_place(&mut rhs, shift));
648        Repr::from_buffer(rhs)
649    }
650
651    #[rustversion::since(1.64)]
652    impl<'a> TypedReprRef<'a> {
653        pub(super) const fn is_multiple_of_dword(self, divisor: DoubleWord) -> bool {
654            use crate::primitive::extend_word;
655            if let Some(w) = shrink_dword(divisor) {
656                match self {
657                    TypedReprRef::RefSmall(dword) => dword % extend_word(w) == 0,
658                    TypedReprRef::RefLarge(words) => div::rem_by_word(words, w) == 0,
659                }
660            } else {
661                match self {
662                    TypedReprRef::RefSmall(dword) => dword % divisor == 0,
663                    TypedReprRef::RefLarge(words) => div::rem_by_dword(words, divisor) == 0,
664                }
665            }
666        }
667    }
668}
669
670impl UBig {
671    /// Determine whether the integer is perfectly divisible by the divisor.
672    ///
673    /// # Examples
674    ///
675    /// ```
676    /// # use dashu_int::UBig;
677    /// let a = UBig::from(24u8);
678    /// let b = UBig::from(6u8);
679    /// assert!(a.is_multiple_of(&b));
680    /// ```
681    ///
682    /// # Panics
683    ///
684    /// Panics if the divisor is zero.
685    #[inline]
686    pub fn is_multiple_of(&self, divisor: &Self) -> bool {
687        (self % divisor).is_zero()
688    }
689
690    /// A const version of [UBig::is_multiple_of], but only accepts [DoubleWord][crate::DoubleWord] divisors.
691    ///
692    /// # Availability
693    ///
694    /// Since Rust 1.64
695    #[rustversion::since(1.64)]
696    #[inline]
697    pub const fn is_multiple_of_const(&self, divisor: crate::DoubleWord) -> bool {
698        self.repr().is_multiple_of_dword(divisor)
699    }
700}
701
702impl IBig {
703    /// Determine whether the integer is perfectly divisible by the divisor.
704    ///
705    /// # Examples
706    ///
707    /// ```
708    /// # use dashu_int::IBig;
709    /// let a = IBig::from(24);
710    /// let b = IBig::from(-6);
711    /// assert!(a.is_multiple_of(&b));
712    /// ```
713    ///
714    /// # Panics
715    ///
716    /// Panics if the divisor is zero.
717    #[inline]
718    pub fn is_multiple_of(&self, divisor: &Self) -> bool {
719        (self % divisor).is_zero()
720    }
721
722    /// A const version of [IBig::is_multiple_of], but only accepts [DoubleWord][crate::DoubleWord] divisors.
723    ///
724    /// # Availability
725    ///
726    /// Since Rust 1.64
727    #[rustversion::since(1.64)]
728    #[inline]
729    pub const fn is_multiple_of_const(&self, divisor: crate::DoubleWord) -> bool {
730        let (_, repr) = self.as_sign_repr();
731        repr.is_multiple_of_dword(divisor)
732    }
733}
dashu_int/div_ops.rs

dashu_int/
div_ops.rs
