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_div_rem {
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_div_rem
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_div {
148    ($mag0:ident, $sign1:ident, $mag1:ident) => {
149        IBig(($mag0 / $mag1).with_sign($sign1))
150    };
151}
152macro_rules! impl_ubig_ibig_rem {
153    ($mag0:ident, $sign1:ident, $mag1:ident) => {{
154        let _unused = $sign1;
155        UBig($mag0 % $mag1)
156    }};
157}
158macro_rules! impl_ubig_ibig_divrem {
159    ($mag0:ident, $sign1:ident, $mag1:ident) => {{
160        let (q, r) = $mag0.div_rem($mag1);
161        (IBig(q.with_sign($sign1)), UBig(r))
162    }};
163}
164helper_macros::forward_ubig_ibig_binop_to_repr!(impl Div, div, Output = IBig, impl_ubig_ibig_div);
165helper_macros::forward_ubig_ibig_binop_to_repr!(impl Rem, rem, Output = UBig, impl_ubig_ibig_rem);
166helper_macros::forward_ubig_ibig_binop_to_repr!(impl DivRem, div_rem -> (IBig, UBig), OutputDiv = IBig, OutputRem = UBig, impl_ubig_ibig_divrem);
167helper_macros::impl_binop_assign_by_taking!(impl RemAssign<IBig> for UBig, rem_assign, rem);
168
169macro_rules! impl_ibig_ubig_div {
170    ($sign0:ident, $mag0:ident, $mag1:ident) => {
171        // truncate towards 0.
172        IBig(($mag0 / $mag1).with_sign($sign0))
173    };
174}
175macro_rules! impl_ibig_ubig_rem {
176    ($sign0:ident, $mag0:ident, $mag1:ident) => {{
177        // remainder with truncating division has same sign as lhs.
178        IBig(($mag0 % $mag1).with_sign($sign0))
179    }};
180}
181macro_rules! impl_ibig_ubig_divrem {
182    ($sign0:ident, $mag0:ident, $mag1:ident) => {{
183        // remainder with truncating division has same sign as lhs.
184        let (q, r) = $mag0.div_rem($mag1);
185        (IBig(q.with_sign($sign0)), IBig(r.with_sign($sign0)))
186    }};
187}
188helper_macros::forward_ibig_ubig_binop_to_repr!(impl Div, div, Output = IBig, impl_ibig_ubig_div);
189helper_macros::forward_ibig_ubig_binop_to_repr!(impl Rem, rem, Output = IBig, impl_ibig_ubig_rem);
190helper_macros::forward_ibig_ubig_binop_to_repr!(impl DivRem, div_rem -> (IBig, IBig), OutputDiv = IBig, OutputRem = IBig, impl_ibig_ubig_divrem);
191helper_macros::impl_binop_assign_by_taking!(impl DivAssign<UBig> for IBig, div_assign, div);
192helper_macros::impl_binop_assign_by_taking!(impl RemAssign<UBig> for IBig, rem_assign, rem);
193
194// Ops with primitives
195
196macro_rules! impl_divrem_with_primitive {
197    (impl <$target:ty> for $t:ty) => {
198        impl DivRem<$target> for $t {
199            type OutputDiv = $t;
200            type OutputRem = $target;
201
202            #[inline]
203            fn div_rem(self, rhs: $target) -> ($t, $target) {
204                let (q, r) = self.div_rem(<$t>::from(rhs));
205                (q, r.try_into().unwrap())
206            }
207        }
208
209        impl<'l> DivRem<$target> for &'l $t {
210            type OutputDiv = $t;
211            type OutputRem = $target;
212
213            #[inline]
214            fn div_rem(self, rhs: $target) -> ($t, $target) {
215                let (q, r) = self.div_rem(<$t>::from(rhs));
216                (q, r.try_into().unwrap())
217            }
218        }
219
220        impl<'r> DivRem<&'r $target> for $t {
221            type OutputDiv = $t;
222            type OutputRem = $target;
223
224            #[inline]
225            fn div_rem(self, rhs: &$target) -> ($t, $target) {
226                let (q, r) = self.div_rem(<$t>::from(*rhs));
227                (q, r.try_into().unwrap())
228            }
229        }
230
231        impl<'l, 'r> DivRem<&'r $target> for &'l $t {
232            type OutputDiv = $t;
233            type OutputRem = $target;
234
235            #[inline]
236            fn div_rem(self, rhs: &$target) -> ($t, $target) {
237                let (q, r) = self.div_rem(<$t>::from(*rhs));
238                (q, r.try_into().unwrap())
239            }
240        }
241    };
242}
243
244macro_rules! impl_div_primitive_with_ubig {
245    ($($t:ty)*) => {$(
246        helper_macros::impl_binop_with_primitive!(impl Div<$t> for UBig, div);
247        helper_macros::impl_binop_with_primitive!(impl Rem<$t> for UBig, rem -> $t);
248        helper_macros::impl_binop_assign_with_primitive!(impl DivAssign<$t> for UBig, div_assign);
249
250        impl_divrem_with_primitive!(impl <$t> for UBig);
251        helper_macros::impl_binop_assign_with_primitive!(impl DivRemAssign<$t> for UBig, div_rem_assign, OutputRem = $t);
252    )*};
253}
254impl_div_primitive_with_ubig!(u8 u16 u32 u64 u128 usize);
255
256macro_rules! impl_div_primitive_with_ibig {
257    ($($t:ty)*) => {$(
258        helper_macros::impl_binop_with_primitive!(impl Div<$t> for IBig, div);
259        helper_macros::impl_binop_with_primitive!(impl Rem<$t> for IBig, rem -> $t);
260        helper_macros::impl_binop_assign_with_primitive!(impl DivAssign<$t> for IBig, div_assign);
261
262        impl_divrem_with_primitive!(impl <$t> for IBig);
263        helper_macros::impl_binop_assign_with_primitive!(impl DivRemAssign<$t> for IBig, div_rem_assign, OutputRem = $t);
264    )*};
265}
266impl_div_primitive_with_ibig!(u8 u16 u32 u64 u128 usize i8 i16 i32 i64 i128 isize);
267
268pub(crate) mod repr {
269    use super::*;
270    use crate::{
271        arch::word::{DoubleWord, Word},
272        buffer::Buffer,
273        div,
274        error::panic_divide_by_0,
275        helper_macros::debug_assert_zero,
276        memory::MemoryAllocation,
277        primitive::shrink_dword,
278        repr::{
279            Repr,
280            TypedRepr::{self, *},
281            TypedReprRef::{self, *},
282        },
283        shift,
284    };
285
286    impl DivRem<TypedRepr> for TypedRepr {
287        type OutputDiv = Repr;
288        type OutputRem = Repr;
289
290        #[inline]
291        fn div_rem(self, rhs: TypedRepr) -> (Repr, Repr) {
292            match (self, rhs) {
293                (Small(dword0), Small(dword1)) => div_rem_dword(dword0, dword1),
294                (Small(dword0), Large(_)) => (Repr::zero(), Repr::from_dword(dword0)),
295                (Large(buffer0), Small(dword1)) => div_rem_large_dword(buffer0, dword1),
296                (Large(buffer0), Large(buffer1)) => {
297                    if buffer0.len() >= buffer1.len() {
298                        div_rem_large(buffer0, buffer1)
299                    } else {
300                        (Repr::zero(), Repr::from_buffer(buffer0))
301                    }
302                }
303            }
304        }
305    }
306
307    impl<'l> DivRem<TypedRepr> for TypedReprRef<'l> {
308        type OutputDiv = Repr;
309        type OutputRem = Repr;
310
311        #[inline]
312        fn div_rem(self, rhs: TypedRepr) -> (Repr, Repr) {
313            match (self, rhs) {
314                (RefSmall(dword0), Small(dword1)) => div_rem_dword(dword0, dword1),
315                (RefSmall(dword0), Large(_)) => (Repr::zero(), Repr::from_dword(dword0)),
316                (RefLarge(words0), Small(dword1)) => div_rem_large_dword(words0.into(), dword1),
317                (RefLarge(words0), Large(mut buffer1)) => {
318                    if words0.len() >= buffer1.len() {
319                        div_rem_large(words0.into(), buffer1)
320                    } else {
321                        // Reuse buffer1 for the remainder.
322                        buffer1.clone_from_slice(words0);
323                        (Repr::zero(), Repr::from_buffer(buffer1))
324                    }
325                }
326            }
327        }
328    }
329
330    impl<'r> DivRem<TypedReprRef<'r>> for TypedRepr {
331        type OutputDiv = Repr;
332        type OutputRem = Repr;
333
334        #[inline]
335        fn div_rem(self, rhs: TypedReprRef) -> (Repr, Repr) {
336            match (self, rhs) {
337                (Small(dword0), RefSmall(dword1)) => div_rem_dword(dword0, dword1),
338                (Small(dword0), RefLarge(_)) => (Repr::zero(), Repr::from_dword(dword0)),
339                (Large(buffer0), RefSmall(dword1)) => div_rem_large_dword(buffer0, dword1),
340                (Large(buffer0), RefLarge(words1)) => {
341                    if buffer0.len() >= words1.len() {
342                        div_rem_large(buffer0, words1.into())
343                    } else {
344                        (Repr::zero(), Repr::from_buffer(buffer0))
345                    }
346                }
347            }
348        }
349    }
350
351    impl<'l, 'r> DivRem<TypedReprRef<'r>> for TypedReprRef<'l> {
352        type OutputDiv = Repr;
353        type OutputRem = Repr;
354
355        #[inline]
356        fn div_rem(self, rhs: TypedReprRef) -> (Repr, Repr) {
357            match (self, rhs) {
358                (RefSmall(dword0), RefSmall(dword1)) => div_rem_dword(dword0, dword1),
359                (RefSmall(dword0), RefLarge(_)) => (Repr::zero(), Repr::from_dword(dword0)),
360                (RefLarge(words0), RefSmall(dword1)) => div_rem_large_dword(words0.into(), dword1),
361                (RefLarge(words0), RefLarge(words1)) => {
362                    if words0.len() >= words1.len() {
363                        div_rem_large(words0.into(), words1.into())
364                    } else {
365                        (Repr::zero(), Repr::from_buffer(words0.into()))
366                    }
367                }
368            }
369        }
370    }
371
372    #[inline]
373    fn div_rem_dword(lhs: DoubleWord, rhs: DoubleWord) -> (Repr, Repr) {
374        // If division works, remainder also works.
375        match lhs.checked_div(rhs) {
376            Some(res) => (Repr::from_dword(res), Repr::from_dword(lhs % rhs)),
377            None => panic_divide_by_0(),
378        }
379    }
380
381    fn div_rem_large_dword(mut buffer: Buffer, rhs: DoubleWord) -> (Repr, Repr) {
382        if rhs == 0 {
383            panic_divide_by_0();
384        }
385        if let Some(word) = shrink_dword(rhs) {
386            let rem = div::div_by_word_in_place(&mut buffer, word);
387            (Repr::from_buffer(buffer), Repr::from_word(rem))
388        } else {
389            let rem = div::div_by_dword_in_place(&mut buffer, rhs);
390            (Repr::from_buffer(buffer), Repr::from_dword(rem))
391        }
392    }
393
394    fn div_rem_large(mut lhs: Buffer, mut rhs: Buffer) -> (Repr, Repr) {
395        let shift = div_rem_in_lhs(&mut lhs, &mut rhs);
396        let n = rhs.len();
397        rhs.copy_from_slice(&lhs[..n]);
398        debug_assert_zero!(shift::shr_in_place(&mut rhs, shift));
399        lhs.erase_front(n);
400        (Repr::from_buffer(lhs), Repr::from_buffer(rhs))
401    }
402
403    /// lhs = [lhs % rhs, lhs / rhs]
404    ///
405    /// Returns the number of shift bits produced by normalization.
406    #[inline]
407    fn div_rem_in_lhs(lhs: &mut Buffer, rhs: &mut Buffer) -> u32 {
408        let mut allocation =
409            MemoryAllocation::new(div::memory_requirement_exact(lhs.len(), rhs.len()));
410        let (shift, fast_div_top) = div::normalize(rhs);
411        let quo_carry = div::div_rem_unshifted_in_place(
412            lhs,
413            rhs,
414            shift,
415            fast_div_top,
416            &mut allocation.memory(),
417        );
418        lhs.push_resizing(quo_carry);
419        shift
420    }
421
422    impl Div<TypedRepr> for TypedRepr {
423        type Output = Repr;
424
425        #[inline]
426        fn div(self, rhs: TypedRepr) -> Repr {
427            match (self, rhs) {
428                (Small(dword0), Small(dword1)) => div_dword(dword0, dword1),
429                (Small(_), Large(_)) => Repr::zero(),
430                (Large(buffer0), Small(dword1)) => div_large_dword(buffer0, dword1),
431                (Large(buffer0), Large(buffer1)) => {
432                    if buffer0.len() >= buffer1.len() {
433                        div_large(buffer0, buffer1)
434                    } else {
435                        Repr::zero()
436                    }
437                }
438            }
439        }
440    }
441
442    impl<'r> Div<TypedReprRef<'r>> for TypedRepr {
443        type Output = Repr;
444
445        #[inline]
446        fn div(self, rhs: TypedReprRef<'r>) -> Repr {
447            match (self, rhs) {
448                (Small(dword0), RefSmall(dword1)) => div_dword(dword0, dword1),
449                (Small(_), RefLarge(_)) => Repr::zero(),
450                (Large(buffer0), RefSmall(dword1)) => div_large_dword(buffer0, dword1),
451                (Large(buffer0), RefLarge(words1)) => {
452                    if buffer0.len() >= words1.len() {
453                        div_large(buffer0, words1.into())
454                    } else {
455                        Repr::zero()
456                    }
457                }
458            }
459        }
460    }
461
462    impl<'l> Div<TypedRepr> for TypedReprRef<'l> {
463        type Output = Repr;
464
465        #[inline]
466        fn div(self, rhs: TypedRepr) -> Repr {
467            match (self, rhs) {
468                (RefSmall(dword0), Small(dword1)) => div_dword(dword0, dword1),
469                (RefSmall(_), Large(_)) => Repr::zero(),
470                (RefLarge(words0), Small(dword1)) => div_large_dword(words0.into(), dword1),
471                (RefLarge(words1), Large(buffer1)) => {
472                    if words1.len() >= buffer1.len() {
473                        div_large(words1.into(), buffer1)
474                    } else {
475                        Repr::zero()
476                    }
477                }
478            }
479        }
480    }
481
482    impl<'l, 'r> Div<TypedReprRef<'r>> for TypedReprRef<'l> {
483        type Output = Repr;
484
485        #[inline]
486        fn div(self, rhs: TypedReprRef) -> Repr {
487            match (self, rhs) {
488                (RefSmall(dword0), RefSmall(dword1)) => div_dword(dword0, dword1),
489                (RefSmall(_), RefLarge(_)) => Repr::zero(),
490                (RefLarge(words0), RefSmall(dword1)) => div_large_dword(words0.into(), dword1),
491                (RefLarge(words0), RefLarge(words1)) => {
492                    if words0.len() >= words1.len() {
493                        div_large(words0.into(), words1.into())
494                    } else {
495                        Repr::zero()
496                    }
497                }
498            }
499        }
500    }
501
502    #[inline]
503    fn div_dword(lhs: DoubleWord, rhs: DoubleWord) -> Repr {
504        match lhs.checked_div(rhs) {
505            Some(res) => Repr::from_dword(res),
506            None => panic_divide_by_0(),
507        }
508    }
509
510    #[inline]
511    fn div_large_dword(lhs: Buffer, rhs: DoubleWord) -> Repr {
512        let (q, _) = div_rem_large_dword(lhs, rhs);
513        q
514    }
515
516    fn div_large(mut lhs: Buffer, mut rhs: Buffer) -> Repr {
517        let _shift = div_rem_in_lhs(&mut lhs, &mut rhs);
518        lhs.erase_front(rhs.len());
519        Repr::from_buffer(lhs)
520    }
521
522    impl Rem<TypedRepr> for TypedRepr {
523        type Output = Repr;
524
525        #[inline]
526        fn rem(self, rhs: TypedRepr) -> Repr {
527            match (self, rhs) {
528                (Small(dword0), Small(dword1)) => rem_dword(dword0, dword1),
529                (Small(dword0), Large(_)) => Repr::from_dword(dword0),
530                (Large(buffer0), Small(dword1)) => rem_large_dword(&buffer0, dword1),
531                (Large(buffer0), Large(buffer1)) => {
532                    if buffer0.len() >= buffer1.len() {
533                        rem_large(buffer0, buffer1)
534                    } else {
535                        Repr::from_buffer(buffer0)
536                    }
537                }
538            }
539        }
540    }
541
542    impl<'r> Rem<TypedReprRef<'r>> for TypedRepr {
543        type Output = Repr;
544
545        #[inline]
546        fn rem(self, rhs: TypedReprRef) -> Repr {
547            match (self, rhs) {
548                (Small(dword0), RefSmall(dword1)) => rem_dword(dword0, dword1),
549                (Small(dword0), RefLarge(_)) => Repr::from_dword(dword0),
550                (Large(buffer0), RefSmall(dword1)) => rem_large_dword(&buffer0, dword1),
551                (Large(buffer0), RefLarge(words1)) => {
552                    if buffer0.len() >= words1.len() {
553                        rem_large(buffer0, words1.into())
554                    } else {
555                        Repr::from_buffer(buffer0)
556                    }
557                }
558            }
559        }
560    }
561
562    impl<'l> Rem<TypedRepr> for TypedReprRef<'l> {
563        type Output = Repr;
564
565        #[inline]
566        fn rem(self, rhs: TypedRepr) -> Repr {
567            match (self, rhs) {
568                (RefSmall(dword0), Small(dword1)) => rem_dword(dword0, dword1),
569                (RefSmall(dword0), Large(_)) => Repr::from_dword(dword0),
570                (RefLarge(words0), Small(dword1)) => rem_large_dword(words0, dword1),
571                (RefLarge(words0), Large(mut buffer1)) => {
572                    if words0.len() >= buffer1.len() {
573                        rem_large(words0.into(), buffer1)
574                    } else {
575                        // Reuse buffer1 for the remainder.
576                        buffer1.clone_from_slice(words0);
577                        Repr::from_buffer(buffer1)
578                    }
579                }
580            }
581        }
582    }
583
584    impl<'l, 'r> Rem<TypedReprRef<'r>> for TypedReprRef<'l> {
585        type Output = Repr;
586
587        #[inline]
588        fn rem(self, rhs: TypedReprRef) -> Repr {
589            match (self, rhs) {
590                (RefSmall(dword0), RefSmall(dword1)) => rem_dword(dword0, dword1),
591                (RefSmall(dword0), RefLarge(_)) => Repr::from_dword(dword0),
592                (RefLarge(words0), RefSmall(dword1)) => rem_large_dword(words0, dword1),
593                (RefLarge(words0), RefLarge(words1)) => {
594                    if words0.len() >= words1.len() {
595                        rem_large(words0.into(), words1.into())
596                    } else {
597                        Repr::from_buffer(words0.into())
598                    }
599                }
600            }
601        }
602    }
603
604    #[inline]
605    fn rem_dword(lhs: DoubleWord, rhs: DoubleWord) -> Repr {
606        match lhs.checked_rem(rhs) {
607            Some(res) => Repr::from_dword(res),
608            None => panic_divide_by_0(),
609        }
610    }
611
612    #[inline]
613    fn rem_large_dword(lhs: &[Word], rhs: DoubleWord) -> Repr {
614        if rhs == 0 {
615            panic_divide_by_0();
616        }
617        if let Some(word) = shrink_dword(rhs) {
618            Repr::from_word(div::rem_by_word(lhs, word))
619        } else {
620            Repr::from_dword(div::rem_by_dword(lhs, rhs))
621        }
622    }
623
624    pub(crate) fn rem_large(mut lhs: Buffer, mut rhs: Buffer) -> Repr {
625        let shift = div_rem_in_lhs(&mut lhs, &mut rhs);
626        let n = rhs.len();
627        rhs.copy_from_slice(&lhs[..n]);
628        debug_assert_zero!(shift::shr_in_place(&mut rhs, shift));
629        Repr::from_buffer(rhs)
630    }
631
632    #[rustversion::since(1.64)]
633    impl<'a> TypedReprRef<'a> {
634        pub(super) const fn is_multiple_of_dword(self, divisor: DoubleWord) -> bool {
635            use crate::primitive::extend_word;
636            if let Some(w) = shrink_dword(divisor) {
637                match self {
638                    TypedReprRef::RefSmall(dword) => dword % extend_word(w) == 0,
639                    TypedReprRef::RefLarge(words) => div::rem_by_word(words, w) == 0,
640                }
641            } else {
642                match self {
643                    TypedReprRef::RefSmall(dword) => dword % divisor == 0,
644                    TypedReprRef::RefLarge(words) => div::rem_by_dword(words, divisor) == 0,
645                }
646            }
647        }
648    }
649}
650
651impl UBig {
652    /// Determine whether the integer is perfectly divisible by the divisor.
653    ///
654    /// # Examples
655    ///
656    /// ```
657    /// # use dashu_int::UBig;
658    /// let a = UBig::from(24u8);
659    /// let b = UBig::from(6u8);
660    /// assert!(a.is_multiple_of(&b));
661    /// ```
662    ///
663    /// # Panics
664    ///
665    /// Panics if the divisor is zero.
666    #[inline]
667    pub fn is_multiple_of(&self, divisor: &Self) -> bool {
668        (self % divisor).is_zero()
669    }
670
671    /// A const version of [UBig::is_multiple_of], but only accepts [DoubleWord][crate::DoubleWord] divisors.
672    ///
673    /// # Availability
674    ///
675    /// Since Rust 1.64
676    #[rustversion::since(1.64)]
677    #[inline]
678    pub const fn is_multiple_of_const(&self, divisor: crate::DoubleWord) -> bool {
679        self.repr().is_multiple_of_dword(divisor)
680    }
681}
682
683impl IBig {
684    /// Determine whether the integer is perfectly divisible by the divisor.
685    ///
686    /// # Examples
687    ///
688    /// ```
689    /// # use dashu_int::IBig;
690    /// let a = IBig::from(24);
691    /// let b = IBig::from(-6);
692    /// assert!(a.is_multiple_of(&b));
693    /// ```
694    ///
695    /// # Panics
696    ///
697    /// Panics if the divisor is zero.
698    #[inline]
699    pub fn is_multiple_of(&self, divisor: &Self) -> bool {
700        (self % divisor).is_zero()
701    }
702
703    /// A const version of [IBig::is_multiple_of], but only accepts [DoubleWord][crate::DoubleWord] divisors.
704    ///
705    /// # Availability
706    ///
707    /// Since Rust 1.64
708    #[rustversion::since(1.64)]
709    #[inline]
710    pub const fn is_multiple_of_const(&self, divisor: crate::DoubleWord) -> bool {
711        let (_, repr) = self.as_sign_repr();
712        repr.is_multiple_of_dword(divisor)
713    }
714}
dashu_int/div_ops.rs

dashu_int/
div_ops.rs
