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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143

//! bigint: declares the BigInt type and implements all its operations.

use crate::traits::{Digit, SignedDigit};
use crate::BigUint;
use core::cmp::Ordering;

pub(crate) mod fmt;
pub(crate) mod froms;
pub(crate) mod ops;

#[cfg(test)]
mod test;

// TODO: implement ilog2 and that sort of things

/// Representation of an signed integer with an infinite number of bits.
///
/// The internal representation has 2 members: a BigUint for the absolute value, and
/// a boolean for the sign.
#[derive(Clone, Debug, Eq)]
pub struct BigInt<T: Digit> {
    pub uint: BigUint<T>,
    pub sign: bool,
}

impl<T: Digit> BigInt<T> {
    /// Trivial constructor: from a single `i32` \
    /// Integers higher than `i32::MAX` or lowar than `i32::MIN` are supposed
    /// to be constructed using the various `From<T>` implementations.
    pub fn new(val: T::Signed) -> BigInt<T> {
        BigInt::<T> {
            uint: BigUint::<T>::new(val.abs()),
            sign: val.is_positive(),
        }
    }

    #[inline]
    pub(crate) fn with_capacity(mut self, capacity: usize) -> Self {
        self.uint.set_capacity(capacity);
        self
    }

    pub fn from_unsigned(val: T) -> BigInt<T> {
        BigInt::<T> {
            uint: BigUint::<T>::new(val),
            sign: true,
        }
    }

    /// Returns true if the integer is strictly higher than 0, false otherwise
    pub fn is_sign_positive(&self) -> bool {
        self.uint != BigUint::default() && self.sign
    }
    /// Returns true if the integer is strictly lower than 0, false otherwise
    pub fn is_sign_negative(&self) -> bool {
        self.uint != BigUint::default() && !self.sign
    }

    /// Copies data from other into self, keeping self's allocation if possible
    pub fn copy_from(&mut self, other: &Self) {
        self.uint.copy_from(&other.uint);
        self.sign = other.sign;
    }

    pub(crate) fn signed_eq(&self, other_sign: bool, other: &[T]) -> bool {
        &self.uint.val == other && ((self.sign == other_sign) || (self.uint.val == vec![T::ZERO]))
    }

    pub(crate) fn signed_ord(&self, other_sign: bool, other: &[T]) -> Ordering {
        match (self.sign, other_sign) {
            (true, true) => self.uint.ord(other),
            (true, false) => Ordering::Greater,
            (false, true) => Ordering::Less,
            (false, false) => self.uint.ord(other).reverse(),
        }
    }
}

/// Default implementation for BigUint: returns 0 with positive sign.
impl<T: Digit> Default for BigInt<T> {
    fn default() -> BigInt<T> {
        BigInt::<T> {
            uint: Default::default(),
            sign: true,
        }
    }
}

impl<T: Digit> std::hash::Hash for BigInt<T> {
    fn hash<H>(&self, state: &mut H)
    where
        H: std::hash::Hasher,
    {
        self.uint.hash(state);
        self.sign.hash(state);
    }
}

impl<T: Digit> PartialOrd<BigUint<T>> for BigInt<T> {
    fn partial_cmp(&self, other: &BigUint<T>) -> Option<Ordering> {
        Some(self.signed_ord(true, &other.val))
    }
}

impl<T: Digit> PartialOrd<BigInt<T>> for BigUint<T> {
    fn partial_cmp(&self, other: &BigInt<T>) -> Option<Ordering> {
        Some(other.signed_ord(true, &self.val).reverse())
    }
}

impl<T: Digit> PartialOrd<BigInt<T>> for BigInt<T> {
    fn partial_cmp(&self, other: &BigInt<T>) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl<T: Digit> Ord for BigInt<T> {
    fn cmp(&self, other: &BigInt<T>) -> Ordering {
        self.signed_ord(other.sign, &other.uint.val)
    }
}

/// Test for equality. Returns true if the integers are equal.
///
/// In particular, handles the case where the 2 operands are 0, but with opposite
/// sign. In that case the test still returns true.
impl<T: Digit> PartialEq for BigInt<T> {
    fn eq(&self, other: &Self) -> bool {
        self.signed_eq(other.sign, &other.uint.val)
    }
}

impl<T: Digit> PartialEq<BigUint<T>> for BigInt<T> {
    fn eq(&self, other: &BigUint<T>) -> bool {
        self.signed_eq(true, &other.val)
    }
}

impl<T: Digit> PartialEq<BigInt<T>> for BigUint<T> {
    fn eq(&self, other: &BigInt<T>) -> bool {
        other.signed_eq(true, &self.val)
    }
}