dashu_int/
div_const.rs

1//! Public interface for creating a constant divisor.
2
3use core::{
4    fmt::{Display, Formatter},
5    mem,
6    ops::{Div, DivAssign, Rem, RemAssign},
7};
8use dashu_base::{DivRem, DivRemAssign};
9use num_modular::{DivExact, DivExactAssign, PreMulInv2by1, PreMulInv3by2};
10
11use crate::{
12    arch::word::{DoubleWord, Word},
13    buffer::Buffer,
14    div,
15    error::panic_divide_by_0,
16    helper_macros::debug_assert_zero,
17    math::{shl_dword, FastDivideNormalized2},
18    memory::MemoryAllocation,
19    primitive::{double_word, extend_word, shrink_dword},
20    repr::Repr,
21    repr::TypedRepr,
22    shift,
23    ubig::UBig,
24    IBig,
25};
26use alloc::boxed::Box;
27
28#[derive(Debug, PartialEq, Eq)]
29pub(crate) struct ConstSingleDivisor(pub(crate) PreMulInv2by1<Word>);
30
31#[derive(Debug, PartialEq, Eq)]
32pub(crate) struct ConstDoubleDivisor(pub(crate) PreMulInv3by2<Word, DoubleWord>);
33
34#[derive(Debug, PartialEq, Eq)]
35pub(crate) struct ConstLargeDivisor {
36    pub(crate) normalized_divisor: Box<[Word]>,
37    pub(crate) shift: u32,
38    pub(crate) fast_div_top: FastDivideNormalized2,
39}
40
41impl ConstSingleDivisor {
42    /// Create a single word const divisor
43    #[inline]
44    pub const fn new(n: Word) -> Self {
45        debug_assert!(n != 0);
46        Self(PreMulInv2by1::<Word>::new(n))
47    }
48
49    /// Get the original (unnormalized) divisor
50    #[inline]
51    pub const fn divisor(&self) -> Word {
52        self.0.divisor() >> self.0.shift()
53    }
54
55    #[inline]
56    pub const fn normalized_divisor(&self) -> Word {
57        self.0.divisor()
58    }
59    pub const fn shift(&self) -> u32 {
60        self.0.shift()
61    }
62
63    /// Calculate (word << self.shift) % self
64    #[inline]
65    pub const fn rem_word(&self, word: Word) -> Word {
66        if self.0.shift() == 0 {
67            self.0.divider().div_rem_1by1(word).1
68        } else {
69            self.0
70                .divider()
71                .div_rem_2by1(extend_word(word) << self.0.shift())
72                .1
73        }
74    }
75
76    /// Calculate (dword << self.shift) % self
77    #[inline]
78    pub const fn rem_dword(&self, dword: DoubleWord) -> Word {
79        if self.0.shift() == 0 {
80            self.0.divider().div_rem_2by1(dword).1
81        } else {
82            let (n0, n1, n2) = shl_dword(dword, self.0.shift());
83            let (_, r1) = self.0.divider().div_rem_2by1(double_word(n1, n2));
84            self.0.divider().div_rem_2by1(double_word(n0, r1)).1
85        }
86    }
87
88    /// Calculate (words << self.shift) % self
89    pub fn rem_large(&self, words: &[Word]) -> Word {
90        let mut rem = div::fast_rem_by_normalized_word(words, *self.0.divider());
91        if self.0.shift() != 0 {
92            rem = self
93                .0
94                .divider()
95                .div_rem_2by1(extend_word(rem) << self.0.shift())
96                .1
97        }
98        rem
99    }
100}
101
102impl ConstDoubleDivisor {
103    /// Create a double word const divisor
104    #[inline]
105    pub const fn new(n: DoubleWord) -> Self {
106        debug_assert!(n > Word::MAX as DoubleWord);
107        Self(PreMulInv3by2::<Word, DoubleWord>::new(n))
108    }
109
110    /// Get the original (unnormalized) divisor
111    #[inline]
112    pub const fn divisor(&self) -> DoubleWord {
113        self.0.divisor() >> self.0.shift()
114    }
115
116    #[inline]
117    pub const fn normalized_divisor(&self) -> DoubleWord {
118        self.0.divisor()
119    }
120    pub const fn shift(&self) -> u32 {
121        self.0.shift()
122    }
123
124    /// Calculate (dword << self.shift) % self
125    #[inline]
126    pub const fn rem_dword(&self, dword: DoubleWord) -> DoubleWord {
127        if self.0.shift() == 0 {
128            self.0.divider().div_rem_2by2(dword).1
129        } else {
130            let (n0, n1, n2) = shl_dword(dword, self.0.shift());
131            self.0.divider().div_rem_3by2(n0, double_word(n1, n2)).1
132        }
133    }
134
135    /// Calculate (words << self.shift) % self
136    pub fn rem_large(&self, words: &[Word]) -> DoubleWord {
137        let mut rem = div::fast_rem_by_normalized_dword(words, *self.0.divider());
138        if self.0.shift() != 0 {
139            let (r0, r1, r2) = shl_dword(rem, self.0.shift());
140            rem = self.0.divider().div_rem_3by2(r0, double_word(r1, r2)).1
141        }
142        rem
143    }
144}
145
146impl ConstLargeDivisor {
147    /// Create a const divisor with multiple words
148    pub fn new(mut n: Buffer) -> Self {
149        let (shift, fast_div_top) = crate::div::normalize(&mut n);
150        Self {
151            normalized_divisor: n.into_boxed_slice(),
152            shift,
153            fast_div_top,
154        }
155    }
156
157    /// Get the original (unnormalized) divisor
158    pub fn divisor(&self) -> Buffer {
159        let mut buffer = Buffer::from(self.normalized_divisor.as_ref());
160        debug_assert_zero!(shift::shr_in_place(&mut buffer, self.shift));
161        buffer
162    }
163
164    /// Calculate (words << self.shift) % self
165    #[inline]
166    pub fn rem_large(&self, mut words: Buffer) -> Buffer {
167        // shift
168        let carry = shift::shl_in_place(&mut words, self.shift);
169        words.push_resizing(carry);
170
171        // reduce
172        let modulus = &self.normalized_divisor;
173        if words.len() >= modulus.len() {
174            let mut allocation =
175                MemoryAllocation::new(div::memory_requirement_exact(words.len(), modulus.len()));
176            let _overflow = div::div_rem_in_place(
177                &mut words,
178                modulus,
179                self.fast_div_top,
180                &mut allocation.memory(),
181            );
182            words.truncate(modulus.len());
183        }
184        words
185    }
186
187    /// Calculate (x << self.shift) % self
188    #[inline]
189    pub fn rem_repr(&self, x: TypedRepr) -> Buffer {
190        match x {
191            TypedRepr::Small(dword) => {
192                let (lo, mid, hi) = shl_dword(dword, self.shift);
193                let mut buffer = Buffer::allocate_exact(self.normalized_divisor.len());
194                buffer.push(lo);
195                buffer.push(mid);
196                buffer.push(hi);
197
198                // because ConstLargeDivisor is used only for integer with more than two words,
199                // word << ring.shift() must be smaller than the normalized modulus
200                buffer
201            }
202            TypedRepr::Large(words) => self.rem_large(words),
203        }
204    }
205}
206
207#[derive(Debug, PartialEq, Eq)]
208pub(crate) enum ConstDivisorRepr {
209    Single(ConstSingleDivisor),
210    Double(ConstDoubleDivisor),
211    Large(ConstLargeDivisor),
212}
213
214/// An [UBig] with some pre-computed fields to support faster division.
215#[derive(Debug, PartialEq, Eq)]
216pub struct ConstDivisor(pub(crate) ConstDivisorRepr);
217
218impl ConstDivisor {
219    /// Create a [`ConstDivisor`] precomputing the division helper fields for `n`.
220    ///
221    /// # Panics
222    ///
223    /// Panics if `n` is zero.
224    pub fn new(n: UBig) -> ConstDivisor {
225        Self(match n.into_repr() {
226            TypedRepr::Small(0) => panic_divide_by_0(),
227            TypedRepr::Small(dword) => {
228                if let Some(word) = shrink_dword(dword) {
229                    ConstDivisorRepr::Single(ConstSingleDivisor::new(word))
230                } else {
231                    ConstDivisorRepr::Double(ConstDoubleDivisor::new(dword))
232                }
233            }
234            TypedRepr::Large(words) => ConstDivisorRepr::Large(ConstLargeDivisor::new(words)),
235        })
236    }
237
238    /// Create a [`ConstDivisor`] from a single word.
239    ///
240    /// # Panics
241    ///
242    /// Panics if `word` is zero.
243    #[inline]
244    pub const fn from_word(word: Word) -> Self {
245        if word == 0 {
246            panic_divide_by_0()
247        }
248        Self(ConstDivisorRepr::Single(ConstSingleDivisor::new(word)))
249    }
250
251    /// Create a [`ConstDivisor`] from a double word.
252    ///
253    /// # Panics
254    ///
255    /// Panics if `dword` is zero.
256    #[inline]
257    pub const fn from_dword(dword: DoubleWord) -> Self {
258        if dword == 0 {
259            panic_divide_by_0()
260        }
261
262        Self(if let Some(word) = shrink_dword(dword) {
263            ConstDivisorRepr::Single(ConstSingleDivisor::new(word))
264        } else {
265            ConstDivisorRepr::Double(ConstDoubleDivisor::new(dword))
266        })
267    }
268
269    /// Return the divisor value as a [`UBig`].
270    #[inline]
271    pub fn value(&self) -> UBig {
272        UBig(match &self.0 {
273            ConstDivisorRepr::Single(d) => Repr::from_word(d.divisor()),
274            ConstDivisorRepr::Double(d) => Repr::from_dword(d.divisor()),
275            ConstDivisorRepr::Large(d) => Repr::from_buffer(d.divisor()),
276        })
277    }
278}
279
280impl Display for ConstDivisor {
281    fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
282        Display::fmt(&self.value(), f)
283    }
284}
285
286impl Div<&ConstDivisor> for UBig {
287    type Output = UBig;
288
289    #[inline]
290    fn div(self, rhs: &ConstDivisor) -> UBig {
291        UBig(self.into_repr() / &rhs.0)
292    }
293}
294impl Div<&ConstDivisor> for &UBig {
295    type Output = UBig;
296
297    #[inline]
298    fn div(self, rhs: &ConstDivisor) -> UBig {
299        UBig(self.clone().into_repr() / &rhs.0)
300    }
301}
302impl DivAssign<&ConstDivisor> for UBig {
303    #[inline]
304    fn div_assign(&mut self, rhs: &ConstDivisor) {
305        *self = mem::take(self) / rhs;
306    }
307}
308
309impl Rem<&ConstDivisor> for UBig {
310    type Output = UBig;
311
312    #[inline]
313    fn rem(self, rhs: &ConstDivisor) -> UBig {
314        UBig(self.into_repr() % &rhs.0)
315    }
316}
317impl Rem<&ConstDivisor> for &UBig {
318    type Output = UBig;
319
320    #[inline]
321    fn rem(self, rhs: &ConstDivisor) -> UBig {
322        UBig(self.repr() % &rhs.0)
323    }
324}
325impl RemAssign<&ConstDivisor> for UBig {
326    #[inline]
327    fn rem_assign(&mut self, rhs: &ConstDivisor) {
328        *self = mem::take(self) % rhs;
329    }
330}
331
332impl DivRem<&ConstDivisor> for UBig {
333    type OutputDiv = UBig;
334    type OutputRem = UBig;
335
336    #[inline]
337    fn div_rem(self, rhs: &ConstDivisor) -> (UBig, UBig) {
338        let (q, r) = self.into_repr().div_rem(&rhs.0);
339        (UBig(q), UBig(r))
340    }
341}
342impl DivRem<&ConstDivisor> for &UBig {
343    type OutputDiv = UBig;
344    type OutputRem = UBig;
345
346    #[inline]
347    fn div_rem(self, rhs: &ConstDivisor) -> (UBig, UBig) {
348        let (q, r) = self.clone().into_repr().div_rem(&rhs.0);
349        (UBig(q), UBig(r))
350    }
351}
352impl DivRemAssign<&ConstDivisor> for UBig {
353    type OutputRem = UBig;
354    #[inline]
355    fn div_rem_assign(&mut self, rhs: &ConstDivisor) -> UBig {
356        let (q, r) = mem::take(self).div_rem(rhs);
357        *self = q;
358        r
359    }
360}
361
362/// Exact division using a precomputed [`ConstDivisor`] as the `Precompute`.
363///
364/// `d` must be the divisor that `pre` was built from (checked in debug builds). The quotient and
365/// remainder come from the precomputed general division ([`DivRem`]`<&ConstDivisor>`), so repeated
366/// exact divisions against a fixed divisor reuse the reciprocal/normalization instead of
367/// recomputing them. Provided for API completeness — the `()` (Hensel) path is unchanged and
368/// faster for small divisors, which this precompute does not feed.
369impl DivExact<UBig, ConstDivisor> for UBig {
370    type Output = UBig;
371
372    #[inline]
373    fn div_exact(self, d: UBig, pre: &ConstDivisor) -> Option<UBig> {
374        debug_assert_eq!(pre.value(), d, "the divisor must match the precomputed divisor");
375        let (q, r) = self.div_rem(pre);
376        if r.is_zero() {
377            Some(q)
378        } else {
379            None
380        }
381    }
382}
383
384impl DivExact<UBig, ConstDivisor> for &UBig {
385    type Output = UBig;
386
387    #[inline]
388    fn div_exact(self, d: UBig, pre: &ConstDivisor) -> Option<UBig> {
389        debug_assert_eq!(pre.value(), d, "the divisor must match the precomputed divisor");
390        let (q, r) = self.div_rem(pre);
391        if r.is_zero() {
392            Some(q)
393        } else {
394            None
395        }
396    }
397}
398
399impl DivExactAssign<UBig, ConstDivisor> for UBig {
400    #[inline]
401    fn div_exact_assign(&mut self, d: UBig, pre: &ConstDivisor) -> bool {
402        debug_assert_eq!(pre.value(), d, "the divisor must match the precomputed divisor");
403        let (q, r) = (&*self).div_rem(pre);
404        if r.is_zero() {
405            *self = q;
406            true
407        } else {
408            false
409        }
410    }
411}
412
413impl Div<&ConstDivisor> for IBig {
414    type Output = IBig;
415
416    #[inline]
417    fn div(self, rhs: &ConstDivisor) -> IBig {
418        let (sign, repr) = self.into_sign_repr();
419        IBig((repr / &rhs.0).with_sign(sign))
420    }
421}
422impl Div<&ConstDivisor> for &IBig {
423    type Output = IBig;
424
425    #[inline]
426    fn div(self, rhs: &ConstDivisor) -> IBig {
427        let (sign, repr) = self.clone().into_sign_repr();
428        IBig((repr / &rhs.0).with_sign(sign))
429    }
430}
431impl DivAssign<&ConstDivisor> for IBig {
432    #[inline]
433    fn div_assign(&mut self, rhs: &ConstDivisor) {
434        *self = mem::take(self) / rhs;
435    }
436}
437
438impl Rem<&ConstDivisor> for IBig {
439    type Output = IBig;
440
441    #[inline]
442    fn rem(self, rhs: &ConstDivisor) -> IBig {
443        let (sign, repr) = self.into_sign_repr();
444        IBig((repr % &rhs.0).with_sign(sign))
445    }
446}
447impl Rem<&ConstDivisor> for &IBig {
448    type Output = IBig;
449
450    #[inline]
451    fn rem(self, rhs: &ConstDivisor) -> IBig {
452        let (sign, repr) = self.as_sign_repr();
453        IBig((repr % &rhs.0).with_sign(sign))
454    }
455}
456impl RemAssign<&ConstDivisor> for IBig {
457    #[inline]
458    fn rem_assign(&mut self, rhs: &ConstDivisor) {
459        *self = mem::take(self) % rhs;
460    }
461}
462
463impl DivRem<&ConstDivisor> for IBig {
464    type OutputDiv = IBig;
465    type OutputRem = IBig;
466
467    #[inline]
468    fn div_rem(self, rhs: &ConstDivisor) -> (IBig, IBig) {
469        let (sign, repr) = self.into_sign_repr();
470        let (q, r) = repr.div_rem(&rhs.0);
471        (IBig(q.with_sign(sign)), IBig(r.with_sign(sign)))
472    }
473}
474impl DivRem<&ConstDivisor> for &IBig {
475    type OutputDiv = IBig;
476    type OutputRem = IBig;
477
478    #[inline]
479    fn div_rem(self, rhs: &ConstDivisor) -> (IBig, IBig) {
480        let (sign, repr) = self.clone().into_sign_repr();
481        let (q, r) = repr.div_rem(&rhs.0);
482        (IBig(q.with_sign(sign)), IBig(r.with_sign(sign)))
483    }
484}
485impl DivRemAssign<&ConstDivisor> for IBig {
486    type OutputRem = IBig;
487    #[inline]
488    fn div_rem_assign(&mut self, rhs: &ConstDivisor) -> IBig {
489        let (q, r) = mem::take(self).div_rem(rhs);
490        *self = q;
491        r
492    }
493}
494
495mod repr {
496    use super::*;
497    use crate::repr::{
498        Repr,
499        TypedRepr::{self, *},
500        TypedReprRef::{self, *},
501    };
502
503    impl Div<&ConstDivisorRepr> for TypedRepr {
504        type Output = Repr;
505        fn div(self, rhs: &ConstDivisorRepr) -> Repr {
506            match (self, rhs) {
507                (Small(dword), ConstDivisorRepr::Single(div)) => {
508                    Repr::from_dword(div_rem_small_single(dword, div).0)
509                }
510                (Small(dword), ConstDivisorRepr::Double(div)) => {
511                    Repr::from_word(div_rem_small_double(dword, div).0)
512                }
513                (Small(_), ConstDivisorRepr::Large(_)) => {
514                    // lhs must be less than rhs
515                    Repr::zero()
516                }
517                (Large(mut buffer), ConstDivisorRepr::Single(div)) => {
518                    let _rem = div::fast_div_by_word_in_place(
519                        &mut buffer,
520                        div.0.shift(),
521                        *div.0.divider(),
522                    );
523                    Repr::from_buffer(buffer)
524                }
525                (Large(mut buffer), ConstDivisorRepr::Double(div)) => {
526                    let _rem = div::fast_div_by_dword_in_place(
527                        &mut buffer,
528                        div.0.shift(),
529                        *div.0.divider(),
530                    );
531                    Repr::from_buffer(buffer)
532                }
533                (Large(mut buffer), ConstDivisorRepr::Large(div)) => {
534                    let div_len = div.normalized_divisor.len();
535                    if buffer.len() < div_len {
536                        Repr::zero()
537                    } else {
538                        let mut allocation = MemoryAllocation::new(div::memory_requirement_exact(
539                            buffer.len(),
540                            div_len,
541                        ));
542                        let q_top = div::div_rem_unshifted_in_place(
543                            &mut buffer,
544                            &div.normalized_divisor,
545                            div.shift,
546                            div.fast_div_top,
547                            &mut allocation.memory(),
548                        );
549                        buffer.erase_front(div_len);
550                        buffer.push_resizing(q_top);
551                        Repr::from_buffer(buffer)
552                    }
553                }
554            }
555        }
556    }
557
558    impl Rem<&ConstDivisorRepr> for TypedRepr {
559        type Output = Repr;
560
561        fn rem(self, rhs: &ConstDivisorRepr) -> Repr {
562            match (self, rhs) {
563                (Small(dword), ConstDivisorRepr::Single(div)) => {
564                    Repr::from_word(div.rem_dword(dword) >> div.0.shift())
565                }
566                (Small(dword), ConstDivisorRepr::Double(div)) => {
567                    Repr::from_dword(div.rem_dword(dword) >> div.0.shift())
568                }
569                (Small(dword), ConstDivisorRepr::Large(_)) => {
570                    // lhs must be less than rhs
571                    Repr::from_dword(dword)
572                }
573                (Large(buffer), ConstDivisorRepr::Single(div)) => {
574                    Repr::from_word(div.rem_large(&buffer) >> div.0.shift())
575                }
576                (Large(buffer), ConstDivisorRepr::Double(div)) => {
577                    Repr::from_dword(div.rem_large(&buffer) >> div.0.shift())
578                }
579                (Large(buffer), ConstDivisorRepr::Large(div)) => rem_large_large(buffer, div),
580            }
581        }
582    }
583
584    impl<'l, 'r> Rem<&'r ConstDivisorRepr> for TypedReprRef<'l> {
585        type Output = Repr;
586
587        fn rem(self, rhs: &ConstDivisorRepr) -> Repr {
588            match (self, rhs) {
589                (RefSmall(dword), ConstDivisorRepr::Single(div)) => {
590                    Repr::from_word(div.rem_dword(dword) >> div.0.shift())
591                }
592                (RefSmall(dword), ConstDivisorRepr::Double(div)) => {
593                    Repr::from_dword(div.rem_dword(dword) >> div.0.shift())
594                }
595                (RefSmall(dword), ConstDivisorRepr::Large(_)) => {
596                    // lhs must be less than rhs
597                    Repr::from_dword(dword)
598                }
599                (RefLarge(words), ConstDivisorRepr::Single(div)) => {
600                    Repr::from_word(div.rem_large(words) >> div.0.shift())
601                }
602                (RefLarge(words), ConstDivisorRepr::Double(div)) => {
603                    Repr::from_dword(div.rem_large(words) >> div.0.shift())
604                }
605                (RefLarge(words), ConstDivisorRepr::Large(div)) => {
606                    rem_large_large(words.into(), div)
607                }
608            }
609        }
610    }
611
612    impl DivRem<&ConstDivisorRepr> for TypedRepr {
613        type OutputDiv = Repr;
614        type OutputRem = Repr;
615
616        fn div_rem(self, rhs: &ConstDivisorRepr) -> (Repr, Repr) {
617            match (self, rhs) {
618                (Small(dword), ConstDivisorRepr::Single(div)) => {
619                    let (q, r) = div_rem_small_single(dword, div);
620                    (Repr::from_dword(q), Repr::from_word(r))
621                }
622                (Small(dword), ConstDivisorRepr::Double(div)) => {
623                    let (q, r) = div_rem_small_double(dword, div);
624                    (Repr::from_word(q), Repr::from_dword(r))
625                }
626                (Small(dword), ConstDivisorRepr::Large(_)) => {
627                    // lhs must be less than rhs
628                    (Repr::zero(), Repr::from_dword(dword))
629                }
630                (Large(mut buffer), ConstDivisorRepr::Single(div)) => {
631                    let r = div::fast_div_by_word_in_place(
632                        &mut buffer,
633                        div.0.shift(),
634                        *div.0.divider(),
635                    );
636                    (Repr::from_buffer(buffer), Repr::from_word(r))
637                }
638                (Large(mut buffer), ConstDivisorRepr::Double(div)) => {
639                    let r = div::fast_div_by_dword_in_place(
640                        &mut buffer,
641                        div.0.shift(),
642                        *div.0.divider(),
643                    );
644                    (Repr::from_buffer(buffer), Repr::from_dword(r))
645                }
646                (Large(mut buffer), ConstDivisorRepr::Large(div)) => {
647                    let div_len = div.normalized_divisor.len();
648                    if buffer.len() < div_len {
649                        (Repr::zero(), Repr::from_buffer(buffer))
650                    } else {
651                        let mut allocation = MemoryAllocation::new(div::memory_requirement_exact(
652                            buffer.len(),
653                            div_len,
654                        ));
655                        let q_top = div::div_rem_unshifted_in_place(
656                            &mut buffer,
657                            &div.normalized_divisor,
658                            div.shift,
659                            div.fast_div_top,
660                            &mut allocation.memory(),
661                        );
662
663                        let mut q = Buffer::from(&buffer[div_len..]);
664                        q.push_resizing(q_top);
665                        buffer.truncate(div_len);
666                        debug_assert_zero!(shift::shr_in_place(&mut buffer, div.shift));
667                        (Repr::from_buffer(q), Repr::from_buffer(buffer))
668                    }
669                }
670            }
671        }
672    }
673
674    fn div_rem_small_single(lhs: DoubleWord, rhs: &ConstSingleDivisor) -> (DoubleWord, Word) {
675        let (lo, mid, hi) = shl_dword(lhs, rhs.0.shift());
676        let (q1, r1) = rhs.0.divider().div_rem_2by1(double_word(mid, hi));
677        let (q0, r0) = rhs.0.divider().div_rem_2by1(double_word(lo, r1));
678        (double_word(q0, q1), r0 >> rhs.0.shift())
679    }
680
681    fn div_rem_small_double(lhs: DoubleWord, rhs: &ConstDoubleDivisor) -> (Word, DoubleWord) {
682        let (lo, mid, hi) = shl_dword(lhs, rhs.0.shift());
683        let (q, r) = rhs.0.divider().div_rem_3by2(lo, double_word(mid, hi));
684        (q, r >> rhs.0.shift())
685    }
686
687    fn rem_large_large(mut lhs: Buffer, rhs: &ConstLargeDivisor) -> Repr {
688        let modulus = &rhs.normalized_divisor;
689
690        // only reduce if lhs can be larger than rhs
691        if lhs.len() >= modulus.len() {
692            let mut allocation =
693                MemoryAllocation::new(div::memory_requirement_exact(lhs.len(), modulus.len()));
694            let _qtop = div::div_rem_unshifted_in_place(
695                &mut lhs,
696                modulus,
697                rhs.shift,
698                rhs.fast_div_top,
699                &mut allocation.memory(),
700            );
701
702            lhs.truncate(modulus.len());
703            debug_assert_zero!(shift::shr_in_place(&mut lhs, rhs.shift));
704        }
705        Repr::from_buffer(lhs)
706    }
707}
708
709#[cfg(test)]
710mod tests {
711    use super::*;
712    use num_modular::{DivExact, DivExactAssign};
713
714    /// `DivExact` / `DivExactAssign` with a `ConstDivisor` precompute: exact quotients agree with
715    /// `div_rem`, non-divisible cases return `None` (leaving the dividend unchanged for the
716    /// in-place form).
717    #[test]
718    fn test_div_exact_with_const_divisor() {
719        for d in [
720            UBig::from(1001u32),      // single word
721            (UBig::ONE << 64) + 3u8,  // double word on 64-bit
722            UBig::from(10u8).pow(50), // multi word
723        ] {
724            let pre = ConstDivisor::new(d.clone());
725            for i in 1..5usize {
726                let n = d.clone().pow(i) * 7u8;
727                let (q, r) = (&n).div_rem(&d);
728                assert!(r.is_zero(), "d={d:?} i={i}");
729                assert_eq!(n.clone().div_exact(d.clone(), &pre), Some(q.clone()), "d={d:?} i={i}");
730
731                // in-place form, exact division
732                let mut m = n;
733                assert!(m.div_exact_assign(d.clone(), &pre), "d={d:?} i={i}");
734                assert_eq!(m, q, "d={d:?} i={i}");
735            }
736
737            // not divisible → None / unchanged
738            let n = d.clone().pow(2) + 1u8;
739            assert_eq!(n.clone().div_exact(d.clone(), &pre), None, "d={d:?}");
740            let mut m = n;
741            let before = m.clone();
742            assert!(!m.div_exact_assign(d.clone(), &pre), "d={d:?}");
743            assert_eq!(m, before, "d={d:?}");
744        }
745
746        // reference receiver keeps the dividend borrowable
747        let d = UBig::from(1001u32);
748        let pre = ConstDivisor::new(d.clone());
749        let a = UBig::from(7u8) * &d;
750        assert_eq!((&a).div_exact(d.clone(), &pre), Some(UBig::from(7u8)));
751        assert_eq!(a, UBig::from(7u8) * d); // unchanged
752    }
753}
dashu_int/div_const.rs

dashu_int/
div_const.rs
