delsum-lib 1.0.0

Library with most functionality for the delsum crate
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

use crate::bitnum::BitNum;
// binary gcd algorithm
pub fn gcd<N: BitNum>(mut a: N, mut b: N) -> N {
    if a.is_zero() {
        return b;
    }
    if b.is_zero() {
        return a;
    }
    let a_shift = a.trail_zeros() as usize;
    let b_shift = b.trail_zeros() as usize;
    a = a >> a_shift;
    b = b >> b_shift;
    let common_shift = a_shift.min(b_shift);
    loop {
        if b > a {
            std::mem::swap(&mut a, &mut b);
        }
        a = a - b;
        if a.is_zero() {
            return b << common_shift;
        }
        a = a >> a.trail_zeros() as usize;
    }
}

// given a factorization `facs`, finds all combination divisors of facs with low <= d <= high
fn div_combs(mut cur: u128, facs: &[(u128, u8)], low: u128, high: u128) -> Vec<u128> {
    let mut ret = Vec::new();
    match facs.split_last() {
        Some(((fac, mul), other_facs)) => {
            ret.append(&mut div_combs(cur, other_facs, low, high));
            for _ in 0..*mul {
                let (new_cur, ov) = fac.overflowing_mul(cur);
                if ov || new_cur > high {
                    break;
                } else {
                    cur = new_cur;
                    ret.append(&mut div_combs(cur, other_facs, low, high));
                }
            }
        }
        None => {
            if cur >= low && cur <= high {
                ret.push(cur);
            }
        }
    }
    ret
}

/// Finds all divisors of number with low <= d <= high
pub fn divisors_range(number: u128, low: u128, high: u128) -> Vec<u128> {
    let switch_div = number / low > high;
    let (new_high, new_low) = if switch_div {
        (number / low, number / high)
    } else {
        (high, low)
    };
    let (facs, p) = num_prime::nt_funcs::factors(number, None);
    assert!(p.is_none());
    let facs = facs
        .into_iter()
        .map(|(p, e)| (p, e as u8))
        .collect::<Vec<_>>();
    let mut divs = div_combs(1, &facs, new_low, new_high);
    if switch_div {
        divs = divs
            .iter()
            .map(|x| number / x)
            .filter(|&x| x <= high && x >= low)
            .collect();
    }
    divs.sort_unstable();
    divs
}

#[cfg(test)]
mod tests {
    use super::*;
    use quickcheck::TestResult;
    #[test]
    fn gcd_u128() {
        assert_eq!(
            gcd::<u128>(
                806181092647704672515872930213587774,
                701634946365911841808990539472970814
            ),
            13497319857138975198
        );
        assert_eq!(
            gcd::<u128>(806181092647704672515872930213587774, 0),
            806181092647704672515872930213587774
        );
        assert_eq!(
            gcd::<u128>(0, 806181092647704672515872930213587774),
            806181092647704672515872930213587774
        );
    }
    #[quickcheck]
    fn qc_gcd(a: u64, b: u64, c: u64) -> TestResult {
        let a_c = a as u128 * c as u128;
        let b_c = b as u128 * c as u128;
        let result = gcd(a_c, b_c);
        if c == 0 && result == 0 {
            return TestResult::passed();
        }
        TestResult::from_bool(gcd(a_c, b_c) % c as u128 == 0)
    }
    #[test]
    fn combs() {
        assert_eq!(
            divisors_range(21627638661127035875894778593280, 65530, 65536),
            vec![65530, 65531, 65532, 65533, 65534, 65535, 65536]
        );
        assert_eq!(
            divisors_range(21627638661127035875894778593280, 65531, 65535),
            vec![65531, 65532, 65533, 65534, 65535]
        );
        assert_eq!(divisors_range(13875613813, 7000000, 8000000), vec![7299113]);
        assert_eq!(
            divisors_range(1749336101070558, 500000, 600000),
            vec![
                513799, 517881, 528171, 531973, 536851, 540813, 542542, 542543, 553322, 555529,
                566566, 572894, 577122, 598262
            ]
        );
        assert_eq!(
            divisors_range(287000, 1000, 1500),
            vec![1000, 1025, 1148, 1400, 1435]
        );
    }
}