cas_domain/
integer.rs

1//! 任意精度整数：i64 内联 + 大数后备。
2//!
3//! 规范形：凡能放进 i64 的值一律是 `Small`，`Big` 只存越界值。
4//! 这条不变量由 [`Integer::from_big`] 在所有构造路径上保证，
5//! 因此相等、序、哈希都与具体表示无关，跨表示比较无需分配。
6
7use num_bigint::BigInt;
8use std::cmp::Ordering;
9use std::fmt;
10use std::hash::{Hash, Hasher};
11
12/// `BigInt::sign()`（`Sign` 枚举）到 `Ordering` 的换算。
13pub(crate) fn big_sign(b: &BigInt) -> Ordering {
14    match b.sign() {
15        num_bigint::Sign::Minus => Ordering::Less,
16        num_bigint::Sign::NoSign => Ordering::Equal,
17        num_bigint::Sign::Plus => Ordering::Greater,
18    }
19}
20
21/// 大数 gcd（非负）。用 num-integer 的实现（num-bigint 对 BigUint 有
22/// 优化算法）；手写欧几里得在几千比特的操作数上是平方级灾难——大幂折叠
23/// 产生的有理系数会直接把它引爆（perf_probe 实测）。
24pub(crate) fn big_gcd(a: &BigInt, b: &BigInt) -> BigInt {
25    use num_integer::Integer as _;
26    a.gcd(b)
27}
28
29#[derive(Clone, Debug, PartialEq, Eq)]
30enum Repr {
31    Small(i64),
32    Big(Box<BigInt>),
33}
34
35/// 任意精度整数，规范形见模块文档。
36#[derive(Clone, Debug, PartialEq, Eq)]
37pub struct Integer(Repr);
38
39impl Integer {
40    pub const fn zero() -> Self {
41        Integer(Repr::Small(0))
42    }
43
44    pub const fn one() -> Self {
45        Integer(Repr::Small(1))
46    }
47
48    pub const fn from_i64(v: i64) -> Self {
49        Integer(Repr::Small(v))
50    }
51
52    /// 解析十进制字面量（可带负号）；超出 i64 自动落大数表示。
53    pub fn parse(s: &str) -> Option<Self> {
54        if let Ok(v) = s.parse::<i64>() {
55            return Some(Integer(Repr::Small(v)));
56        }
57        BigInt::parse_bytes(s.as_bytes(), 10).map(Self::from_big)
58    }
59
60    pub fn is_zero(&self) -> bool {
61        matches!(self.0, Repr::Small(0))
62    }
63
64    pub fn is_one(&self) -> bool {
65        matches!(self.0, Repr::Small(1))
66    }
67
68    pub fn is_negative(&self) -> bool {
69        self.sign() < 0
70    }
71
72    pub fn sign(&self) -> i32 {
73        match &self.0 {
74            Repr::Small(v) => v.signum() as i32,
75            Repr::Big(b) => match big_sign(b) {
76                Ordering::Less => -1,
77                Ordering::Equal => 0,
78                Ordering::Greater => 1,
79            },
80        }
81    }
82
83    pub fn to_i64(&self) -> Option<i64> {
84        match &self.0 {
85            Repr::Small(v) => Some(*v),
86            Repr::Big(_) => None,
87        }
88    }
89
90    /// 非负值且不超过 u64 时返回（Rational 的 Small 分母可到 u64 上界；
91    /// Big 表示按值判断——(i64::MAX, u64::MAX] 区间的值在 Integer 是 Big，
92    /// 但作为 Rational 分母仍应落 Small，故此处不能只看表示）。
93    pub fn to_u64(&self) -> Option<u64> {
94        match &self.0 {
95            Repr::Small(v) if *v >= 0 => Some(*v as u64),
96            Repr::Small(_) => None,
97            Repr::Big(b) => u64::try_from(b.as_ref()).ok(),
98        }
99    }
100
101    /// u64 落位：能进 i64 用 Small，否则 Big（规范形要求）。
102    pub fn from_u64(v: u64) -> Self {
103        match i64::try_from(v) {
104            Ok(s) => Integer(Repr::Small(s)),
105            Err(_) => Integer(Repr::Big(Box::new(BigInt::from(v)))),
106        }
107    }
108
109    /// 数值的二进制位数（0 返回 0）。expr 层用它做幂折叠的规模守卫。
110    pub fn bit_len(&self) -> u64 {
111        match &self.0 {
112            Repr::Small(v) => {
113                let m = v.unsigned_abs();
114                (u64::BITS - m.leading_zeros()) as u64
115            }
116            Repr::Big(b) => b.bits(),
117        }
118    }
119
120    pub fn abs(&self) -> Self {
121        match &self.0 {
122            Repr::Small(v) => match v.checked_abs() {
123                Some(a) => Integer(Repr::Small(a)),
124                // i64::MIN：|v| = 2^63 越界，落大数
125                None => Self::from_big(-self.as_big()),
126            },
127            Repr::Big(b) => match big_sign(b) {
128                Ordering::Less => Self::from_big(-(b.as_ref().clone())),
129                _ => self.clone(),
130            },
131        }
132    }
133
134    pub fn neg(&self) -> Self {
135        match &self.0 {
136            Repr::Small(v) => match v.checked_neg() {
137                Some(n) => Integer(Repr::Small(n)),
138                None => Self::from_big(-self.as_big()),
139            },
140            Repr::Big(b) => Self::from_big(-(**b).clone()),
141        }
142    }
143
144    pub fn add(&self, other: &Self) -> Self {
145        if let (Repr::Small(a), Repr::Small(b)) = (&self.0, &other.0) {
146            if let Some(s) = a.checked_add(*b) {
147                return Integer(Repr::Small(s));
148            }
149        }
150        Self::from_big(self.as_big() + other.as_big())
151    }
152
153    pub fn sub(&self, other: &Self) -> Self {
154        if let (Repr::Small(a), Repr::Small(b)) = (&self.0, &other.0) {
155            if let Some(s) = a.checked_sub(*b) {
156                return Integer(Repr::Small(s));
157            }
158        }
159        Self::from_big(self.as_big() - other.as_big())
160    }
161
162    pub fn mul(&self, other: &Self) -> Self {
163        if let (Repr::Small(a), Repr::Small(b)) = (&self.0, &other.0) {
164            if let Some(p) = a.checked_mul(*b) {
165                return Integer(Repr::Small(p));
166            }
167        }
168        Self::from_big(self.as_big() * other.as_big())
169    }
170
171    /// 非负整数幂。规模守卫由调用方（expr 层）负责，本方法不做上限检查。
172    pub fn pow(&self, exp: u32) -> Self {
173        if let Repr::Small(v) = &self.0 {
174            if let Some(p) = v.checked_pow(exp) {
175                return Integer(Repr::Small(p));
176            }
177        }
178        Self::from_big(self.as_big().pow(exp))
179    }
180
181    /// 辗转相除，结果非负；`gcd(0, 0) = 0`。
182    pub fn gcd(&self, other: &Self) -> Self {
183        if let (Repr::Small(a), Repr::Small(b)) = (&self.0, &other.0) {
184            Integer(Repr::Small(
185                gcd_u64(a.unsigned_abs(), b.unsigned_abs()) as i64
186            ))
187        } else {
188            Self::from_big(big_gcd(&self.as_big(), &other.as_big()))
189        }
190    }
191
192    /// 精确除法；调用方保证整除（Rational 规范化路径）。
193    pub fn div_exact(&self, divisor: &Self) -> Self {
194        Self::from_big(self.as_big() / divisor.as_big())
195    }
196
197    fn from_big(b: BigInt) -> Self {
198        match i64::try_from(&b) {
199            Ok(v) => Integer(Repr::Small(v)),
200            Err(_) => Integer(Repr::Big(Box::new(b))),
201        }
202    }
203
204    /// 由大数构造（自动落回 Small 表示，若值在 i64 内）。
205    pub fn from_bigint(b: BigInt) -> Self {
206        Self::from_big(b)
207    }
208
209    fn as_big(&self) -> BigInt {
210        match &self.0 {
211            Repr::Small(v) => BigInt::from(*v),
212            Repr::Big(b) => (**b).clone(),
213        }
214    }
215
216    /// 导出为大数表示（Rational 跨表示运算的提升通道）。
217    pub fn to_bigint(&self) -> BigInt {
218        self.as_big()
219    }
220}
221
222pub(crate) fn gcd_u64(mut a: u64, mut b: u64) -> u64 {
223    while b != 0 {
224        let r = a % b;
225        a = b;
226        b = r;
227    }
228    a
229}
230
231impl Ord for Integer {
232    fn cmp(&self, other: &Self) -> Ordering {
233        match (&self.0, &other.0) {
234            (Repr::Small(a), Repr::Small(b)) => a.cmp(b),
235            (Repr::Big(a), Repr::Big(b)) => a.cmp(b),
236            // Big 一定在 i64 范围之外：正大数比一切 i64 大，负大数比一切 i64 小
237            (_, Repr::Big(b)) => big_sign(b).reverse(),
238            (Repr::Big(a), Repr::Small(_)) => big_sign(a),
239        }
240    }
241}
242
243impl PartialOrd for Integer {
244    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
245        Some(self.cmp(other))
246    }
247}
248
249impl Hash for Integer {
250    fn hash<H: Hasher>(&self, state: &mut H) {
251        match &self.0 {
252            Repr::Small(v) => state.write_i64(*v),
253            Repr::Big(b) => b.hash(state),
254        }
255    }
256}
257
258impl fmt::Display for Integer {
259    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
260        match &self.0 {
261            Repr::Small(v) => write!(f, "{v}"),
262            Repr::Big(b) => write!(f, "{b}"),
263        }
264    }
265}
266
267#[cfg(test)]
268mod tests {
269    use super::*;
270
271    #[test]
272    fn 小数路径与规范形() {
273        assert_eq!(
274            Integer::from_i64(2).add(&Integer::from_i64(3)),
275            Integer::from_i64(5)
276        );
277        assert!(!Integer::from_i64(5).is_one());
278        // 越界即落 Big，且 from_big 回收可表示值
279        let big = Integer::from_i64(i64::MAX).add(&Integer::one());
280        assert_eq!(big.to_string(), "9223372036854775808");
281        assert_eq!(big.sub(&Integer::one()), Integer::from_i64(i64::MAX));
282    }
283
284    #[test]
285    fn i64_min_边界() {
286        let m = Integer::from_i64(i64::MIN);
287        // |MIN| = 2^63 只能落大数
288        assert_eq!(m.abs().to_string(), "9223372036854775808");
289        assert_eq!(m.neg().to_string(), "9223372036854775808");
290        assert_eq!(m.mul(&Integer::from_i64(1)), m);
291        // MIN 是负数，且小于一切 Small
292        assert!(m.is_negative());
293        assert!(m.cmp(&Integer::from_i64(i64::MAX)) == Ordering::Less);
294    }
295
296    #[test]
297    fn 跨表示序与相等() {
298        let big = Integer::parse("9223372036854775808").unwrap();
299        assert_eq!(big, Integer::parse("9223372036854775808").unwrap());
300        assert!(Integer::from_i64(-1).cmp(&big) == Ordering::Less);
301        assert!(big.cmp(&Integer::from_i64(i64::MAX)) == Ordering::Greater);
302        let neg_big = big.neg();
303        // -(2^63) 的值恰为 i64::MIN：归一化后两者相等
304        assert_eq!(neg_big.cmp(&Integer::from_i64(i64::MIN)), Ordering::Equal);
305        let below_min = Integer::parse("-9223372036854775809").unwrap();
306        assert_eq!(below_min.cmp(&Integer::from_i64(i64::MIN)), Ordering::Less);
307    }
308
309    #[test]
310    fn 幂与位数() {
311        assert_eq!(Integer::from_i64(2).pow(10).to_string(), "1024");
312        assert_eq!(
313            Integer::from_i64(2).pow(100).to_string(),
314            "1267650600228229401496703205376"
315        );
316        assert_eq!(Integer::from_i64(0).bit_len(), 0);
317        assert_eq!(Integer::from_i64(255).bit_len(), 8);
318        assert_eq!(
319            Integer::parse("1267650600228229401496703205376")
320                .unwrap()
321                .bit_len(),
322            101
323        );
324    }
325
326    #[test]
327    fn 最大公约数() {
328        assert_eq!(
329            Integer::from_i64(12).gcd(&Integer::from_i64(18)),
330            Integer::from_i64(6)
331        );
332        assert_eq!(
333            Integer::from_i64(0).gcd(&Integer::from_i64(5)),
334            Integer::from_i64(5)
335        );
336        let big = Integer::parse("1000000007").unwrap();
337        assert_eq!(big.gcd(&Integer::from_i64(3)), Integer::one());
338    }
339}
cas_domain/integer.rs

cas_domain/
integer.rs
