dashu_int/
remove.rs

1use crate::ubig::UBig;
2use alloc::vec;
3use dashu_base::{DivRem, PowerOfTwo};
4
5impl UBig {
6    /// Divide out all multiples of the factor from the integer,
7    /// returns the exponent of the removed factor.
8    ///
9    /// For self = 0 or factor = 0 or 1, this method returns None.
10    pub fn remove(&mut self, factor: &UBig) -> Option<usize> {
11        if self.is_zero() || factor.is_zero() || factor.is_one() {
12            return None;
13        }
14
15        // shortcut for power of 2
16        if factor.is_power_of_two() {
17            let bits = factor.trailing_zeros().unwrap();
18            let exp = self.trailing_zeros().unwrap() / bits;
19            *self >>= exp * bits;
20            return Some(exp);
21        }
22
23        let (mut q, r) = (&*self).div_rem(factor);
24        if !r.is_zero() {
25            return Some(0);
26        }
27
28        // first stage, division with exponentially growing factors
29        let mut exp = 1;
30        let mut pows = vec![factor.sqr()];
31        loop {
32            let last = pows.last().unwrap();
33            let (new_q, r) = (&q).div_rem(last);
34            if !r.is_zero() {
35                break;
36            }
37
38            exp += 1 << pows.len();
39            q = new_q;
40            let next_sq = last.sqr();
41            pows.push(next_sq);
42        }
43
44        // second stage, division from highest power to the lowest
45        while let Some(last) = pows.pop() {
46            let (new_q, r) = (&q).div_rem(last);
47            if r.is_zero() {
48                exp += 1 << (pows.len() + 1);
49                q = new_q;
50            }
51        }
52
53        // last division
54        let (new_q, r) = (&q).div_rem(factor);
55        if r.is_zero() {
56            exp += 1;
57            q = new_q;
58        }
59
60        *self = q;
61        Some(exp)
62    }
63}
dashu_int/remove.rs

dashu_int/
remove.rs
