twibint 0.3.2

Crate for arithmetic on arbitrarily large integers. Provides Python bindings as well.
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

use core::ops::{Shl, ShlAssign, Shr, ShrAssign};

use crate::traits::Digit;
use crate::BigUint;

impl<T: Digit> Shl<usize> for &BigUint<T> {
    type Output = BigUint<T>;
    fn shl(self, other: usize) -> BigUint<T> {
        let mut ret = self.clone();
        ret <<= other;
        ret
    }
}
impl<T: Digit> Shl<usize> for BigUint<T> {
    type Output = BigUint<T>;
    fn shl(mut self, other: usize) -> BigUint<T> {
        self <<= other;
        self
    }
}
impl<T: Digit> ShlAssign<usize> for BigUint<T> {
    fn shl_assign(&mut self, mut b: usize) {
        if self == &BigUint::<T>::new(T::ZERO) {
            return;
        }

        // First apply whole word shifts (by decreasing b by steps of T::NB_BITS)
        let u32_shifts = b / T::NB_BITS;

        let prev_len = self.val.len();
        self.val.resize(self.val.len() + u32_shifts, T::ZERO);
        self.val.copy_within(..prev_len, u32_shifts);
        self.val[..u32_shifts].fill(T::ZERO);
        b %= T::NB_BITS;

        // Early exit
        if b == 0 {
            return;
        }

        // remaining: shift by less than T::NB_BITS
        let mut overflowing_bits: T;
        let mut carry = T::ZERO;
        for val in &mut self.val[(u32_shifts)..] {
            overflowing_bits = *val >> (T::NB_BITS - b);
            *val <<= b;
            *val |= carry;
            carry = overflowing_bits
        }

        if carry > T::ZERO {
            self.val.push(carry);
        }
    }
}

fn small_shr_assign<T: Digit>(n: &mut BigUint<T>, b: usize) {
    debug_assert!(b < T::NB_BITS);
    // Early exit
    if b == 0 {
        return;
    }

    // remaining: shift by less than T::NB_BITS
    let mut underflowing_bits: T;
    let mut carry = T::ZERO;
    for val in n.val.iter_mut().rev() {
        underflowing_bits = *val << (T::NB_BITS - b);
        *val >>= b;
        *val |= carry;
        carry = underflowing_bits
    }

    n.remove_leading_zeros();
}

impl<T: Digit> Shr<usize> for &BigUint<T> {
    type Output = BigUint<T>;
    fn shr(self, other: usize) -> BigUint<T> {
        if other >= self.nb_bits() {
            return BigUint::<T>::default();
        }

        let mut ret = BigUint::<T>::from(self.val[other / T::NB_BITS..].to_vec());
        small_shr_assign(&mut ret, other % T::NB_BITS);
        ret
    }
}
impl<T: Digit> Shr<usize> for BigUint<T> {
    type Output = BigUint<T>;
    fn shr(mut self, other: usize) -> BigUint<T> {
        self >>= other;
        self
    }
}
impl<T: Digit> ShrAssign<usize> for BigUint<T> {
    fn shr_assign(&mut self, b: usize) {
        if b >= self.nb_bits() {
            self.val = vec![T::ZERO];
            return;
        }

        // First apply whole word shifts (by decreasing b by steps of 32)
        self.val.drain(..b / T::NB_BITS);

        // shift by less than 32
        small_shr_assign(self, b % T::NB_BITS)
    }
}

#[cfg(test)]
mod tests {
    use crate::traits::Digit;
    use crate::BigUint;

    use typed_test_gen::test_with;

    #[test_with(u32, u64)]
    fn capacity_conservation<T: Digit>() {
        let mut a = BigUint::from(vec![T::MAX, T::MAX]).with_capacity(T::NB_BITS * 10);

        a >>= 5;
        assert_eq!(a.capacity(), T::NB_BITS * 10);

        a <<= 12;
        assert_eq!(a.capacity(), T::NB_BITS * 10);
    }
}