1use core::cmp::Ordering;
41
42const BILLION: u32 = 1_000_000_000;
44
45#[derive(Clone, Debug, PartialEq, Eq)]
47pub(crate) struct Nat {
48 limbs: Vec<u32>,
50}
51
52#[inline]
54#[allow(clippy::cast_possible_truncation)] fn low32(x: u64) -> u32 {
56 x as u32
57}
58
59impl Nat {
60 pub(crate) fn zero() -> Self {
62 Self { limbs: Vec::new() }
63 }
64
65 pub(crate) fn from_u64(x: u64) -> Self {
67 let mut n = Self {
68 limbs: vec![low32(x), low32(x >> 32)],
69 };
70 n.trim();
71 n
72 }
73
74 pub(crate) fn from_decimal_digits(digits: &[u8]) -> Self {
77 let mut n = Self::zero();
78 for chunk in digits.chunks(9) {
79 let mut scale = 1_u32;
80 let mut value = 0_u32;
81 for &d in chunk {
82 debug_assert!(d <= 9, "not a decimal digit");
83 scale *= 10;
84 value = value * 10 + u32::from(d);
85 }
86 n.mul_small(scale);
87 n.add_small(value);
88 }
89 n
90 }
91
92 pub(crate) fn pow10(k: u32) -> Self {
94 let mut n = Self::from_u64(1);
95 for _ in 0..k / 9 {
96 n.mul_small(BILLION);
97 }
98 n.mul_small(10_u32.pow(k % 9));
99 n
100 }
101
102 fn trim(&mut self) {
104 while self.limbs.last() == Some(&0) {
105 self.limbs.pop();
106 }
107 }
108
109 pub(crate) fn is_zero(&self) -> bool {
111 self.limbs.is_empty()
112 }
113
114 pub(crate) fn bits(&self) -> u64 {
116 match self.limbs.last() {
117 None => 0,
118 Some(&top) => 32 * self.limbs.len() as u64 - u64::from(top.leading_zeros()),
119 }
120 }
121
122 pub(crate) fn mul_small(&mut self, m: u32) {
124 let mut carry = 0_u64;
125 for limb in &mut self.limbs {
126 let t = u64::from(*limb) * u64::from(m) + carry;
127 *limb = low32(t);
128 carry = t >> 32;
129 }
130 if carry != 0 {
131 self.limbs.push(low32(carry));
132 }
133 self.trim();
134 }
135
136 pub(crate) fn add_small(&mut self, a: u32) {
138 let mut carry = u64::from(a);
139 for limb in &mut self.limbs {
140 if carry == 0 {
141 return;
142 }
143 let t = u64::from(*limb) + carry;
144 *limb = low32(t);
145 carry = t >> 32;
146 }
147 if carry != 0 {
148 self.limbs.push(low32(carry));
149 }
150 }
151
152 pub(crate) fn div_rem_small(&mut self, d: u32) -> u32 {
154 debug_assert!(d != 0, "division by zero");
155 let mut rem = 0_u64;
156 for limb in self.limbs.iter_mut().rev() {
157 let t = (rem << 32) | u64::from(*limb);
158 *limb = low32(t / u64::from(d));
159 rem = t % u64::from(d);
160 }
161 self.trim();
162 low32(rem)
163 }
164
165 pub(crate) fn shl(&self, s: u64) -> Self {
167 if self.is_zero() {
168 return Self::zero();
169 }
170 let words = usize::try_from(s / 32).expect("shift fits memory");
171 let bits = s % 32;
172 let mut limbs = vec![0_u32; words];
173 limbs.reserve(self.limbs.len() + 1);
174 let mut carry = 0_u64;
175 for &limb in &self.limbs {
176 let t = (u64::from(limb) << bits) | carry;
177 limbs.push(low32(t));
178 carry = t >> 32;
179 }
180 if carry != 0 {
181 limbs.push(low32(carry));
182 }
183 Self { limbs }
184 }
185
186 pub(crate) fn split_at_bit(&self, s: u64) -> (Self, Self) {
188 let words = usize::try_from(s / 32).unwrap_or(usize::MAX);
189 if words >= self.limbs.len() {
190 return (Self::zero(), self.clone());
191 }
192 let bits = s % 32;
193 let mut low = Self {
194 limbs: self.limbs[..=words].to_vec(),
195 };
196 low.limbs[words] &= (1_u32 << bits) - 1;
197 low.trim();
198 let mut high = Vec::with_capacity(self.limbs.len() - words);
199 for i in words..self.limbs.len() {
200 let here = u64::from(self.limbs[i]) >> bits;
201 let above = self.limbs.get(i + 1).map_or(0, |&l| u64::from(l));
202 high.push(low32(here | (above << (32 - bits))));
203 }
204 let mut high = Self { limbs: high };
205 high.trim();
206 (high, low)
207 }
208
209 pub(crate) fn add(&self, other: &Self) -> Self {
211 let (long, short) = if self.limbs.len() >= other.limbs.len() {
212 (self, other)
213 } else {
214 (other, self)
215 };
216 let mut limbs = Vec::with_capacity(long.limbs.len() + 1);
217 let mut carry = 0_u64;
218 for (i, &l) in long.limbs.iter().enumerate() {
219 let t = u64::from(l) + short.limbs.get(i).map_or(0, |&s| u64::from(s)) + carry;
220 limbs.push(low32(t));
221 carry = t >> 32;
222 }
223 if carry != 0 {
224 limbs.push(low32(carry));
225 }
226 Self { limbs }
227 }
228
229 pub(crate) fn sub(&self, other: &Self) -> Self {
231 debug_assert!(*self >= *other, "Nat::sub would be negative");
232 let mut limbs = Vec::with_capacity(self.limbs.len());
233 let mut borrow = 0_i64;
234 for (i, &l) in self.limbs.iter().enumerate() {
235 let t = i64::from(l) - other.limbs.get(i).map_or(0, |&s| i64::from(s)) - borrow;
236 borrow = i64::from(t < 0);
237 limbs.push(low32(t.rem_euclid(1_i64 << 32).unsigned_abs()));
238 }
239 debug_assert_eq!(borrow, 0, "Nat::sub underflowed");
240 let mut n = Self { limbs };
241 n.trim();
242 n
243 }
244
245 pub(crate) fn mul(&self, other: &Self) -> Self {
247 if self.is_zero() || other.is_zero() {
248 return Self::zero();
249 }
250 let mut limbs = vec![0_u32; self.limbs.len() + other.limbs.len()];
251 for (i, &a) in self.limbs.iter().enumerate() {
252 let mut carry = 0_u64;
253 for (j, &b) in other.limbs.iter().enumerate() {
254 let t = u64::from(a) * u64::from(b) + u64::from(limbs[i + j]) + carry;
255 limbs[i + j] = low32(t);
256 carry = t >> 32;
257 }
258 limbs[i + other.limbs.len()] = low32(carry);
259 }
260 let mut n = Self { limbs };
261 n.trim();
262 n
263 }
264
265 pub(crate) fn short_quotient(&self, den: &Self) -> (u128, bool) {
268 debug_assert!(!den.is_zero(), "division by zero");
269 let mut rem = self.clone(); let mut q = 0_u128;
271 let k = self.bits().saturating_sub(den.bits());
272 debug_assert!(k < 128, "short_quotient: the quotient does not fit");
273 for i in (0..=k).rev() {
274 let t = den.shl(i);
276 if t <= rem {
277 rem = rem.sub(&t);
278 q |= 1_u128 << i;
279 }
280 }
281 (q, !rem.is_zero()) }
283
284 pub(crate) fn to_decimal_digits(&self) -> Vec<u8> {
287 let mut n = self.clone();
288 let mut out = Vec::new();
289 while !n.is_zero() {
290 let mut chunk = n.div_rem_small(BILLION);
291 for _ in 0..9 {
292 out.push(u8::try_from(chunk % 10).expect("a digit"));
293 chunk /= 10;
294 }
295 }
296 while out.last() == Some(&0) {
297 out.pop();
298 }
299 out.reverse();
300 out
301 }
302
303 #[cfg(test)]
305 pub(crate) fn check_invariants(&self) -> Result<(), &'static str> {
306 if self.limbs.last() == Some(&0) {
307 return Err("N1: a leading zero digit");
308 }
309 Ok(())
310 }
311}
312
313impl PartialOrd for Nat {
314 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
315 Some(self.cmp(other))
316 }
317}
318
319impl Ord for Nat {
320 fn cmp(&self, other: &Self) -> Ordering {
321 self.limbs
322 .len()
323 .cmp(&other.limbs.len())
324 .then_with(|| self.limbs.iter().rev().cmp(other.limbs.iter().rev()))
325 }
326}
327
328#[cfg(test)]
329mod tests {
330 use super::*;
331
332 fn nat(s: &str) -> Nat {
333 let digits: Vec<u8> = s.bytes().map(|b| b - b'0').collect();
334 let n = Nat::from_decimal_digits(&digits);
335 n.check_invariants().unwrap();
336 n
337 }
338
339 fn dec(n: &Nat) -> String {
340 n.check_invariants().unwrap();
341 let d = n.to_decimal_digits();
342 if d.is_empty() {
343 "0".into()
344 } else {
345 d.iter().map(|&b| char::from(b + b'0')).collect()
346 }
347 }
348
349 #[test]
350 fn decimal_round_trip() {
351 for s in [
352 "0",
353 "7",
354 "4294967296",
355 "999999999",
356 "1000000000",
357 "340282366920938463463374607431768211456",
358 "123456789012345678901234567890123456789012345678901234567890",
359 ] {
360 assert_eq!(dec(&nat(s)), s);
361 }
362 assert_eq!(dec(&nat("000123")), "123");
363 assert_eq!(dec(&Nat::from_u64(u64::MAX)), "18446744073709551615");
364 assert_eq!(dec(&Nat::pow10(0)), "1");
365 assert_eq!(dec(&Nat::pow10(25)), "10000000000000000000000000");
366 }
367
368 #[test]
369 fn arithmetic() {
370 let a = nat("340282366920938463463374607431768211456"); let b = nat("18446744073709551615"); assert_eq!(a.bits(), 129);
373 assert_eq!(b.bits(), 64);
374 assert_eq!(Nat::zero().bits(), 0);
375 assert_eq!(dec(&a.add(&b)), "340282366920938463481821351505477763071");
376 assert_eq!(dec(&b.add(&a)), "340282366920938463481821351505477763071");
377 assert_eq!(dec(&a.sub(&b)), "340282366920938463444927863358058659841");
378 assert_eq!(dec(&a.sub(&a)), "0");
379 assert_eq!(
380 dec(&a.mul(&b)),
381 "6277101735386680763495507056286727952638980837032266301440"
382 );
383 assert_eq!(dec(&a.mul(&Nat::zero())), "0");
384 assert!(b < a);
385 assert!(a > b);
386 assert_eq!(a, a.clone());
387 assert!(nat("4294967296") > nat("4294967295"));
388 }
389
390 #[test]
391 fn shifts() {
392 let one = Nat::from_u64(1);
393 assert_eq!(
394 dec(&one.shl(128)),
395 "340282366920938463463374607431768211456"
396 );
397 assert_eq!(dec(&Nat::from_u64(5).shl(33)), "42949672960");
398 assert_eq!(dec(&Nat::zero().shl(77)), "0");
399 let n = nat("123456789012345678901234567890");
400 for s in [0, 1, 31, 32, 33, 64, 70, 96, 97, 200] {
401 let (high, low) = n.split_at_bit(s);
402 high.check_invariants().unwrap();
403 low.check_invariants().unwrap();
404 assert_eq!(high.shl(s).add(&low), n, "s = {s}");
405 assert!(low.bits() <= s);
406 }
407 }
408
409 #[test]
410 fn small_operations() {
411 let mut n = nat("99999999999999999999");
412 n.add_small(1);
413 assert_eq!(dec(&n), "100000000000000000000");
414 n.mul_small(7);
415 assert_eq!(dec(&n), "700000000000000000000");
416 assert_eq!(n.div_rem_small(9), 7);
417 assert_eq!(dec(&n), "77777777777777777777");
418 n.mul_small(0);
419 assert!(n.is_zero());
420 n.add_small(3);
421 assert_eq!(dec(&n), "3");
422 }
423
424 #[test]
425 fn short_quotients() {
426 let n = nat("1000000000000000000000000000000");
427 assert_eq!(
428 n.short_quotient(&nat("7")),
429 (142_857_142_857_142_857_142_857_142_857, true)
430 );
431 assert_eq!(
432 n.short_quotient(&nat("1000000000000")),
433 (1_000_000_000_000_000_000, false)
434 );
435 assert_eq!(nat("5").short_quotient(&nat("7")), (0, true));
436 assert_eq!(Nat::zero().short_quotient(&nat("7")), (0, false));
437 assert_eq!(nat("49").short_quotient(&nat("7")), (7, false));
438 }
439}