1#![no_std]
16#![forbid(unsafe_code)]
17#![allow(clippy::should_implement_trait)]
18#![allow(clippy::result_unit_err)]
19#![allow(clippy::needless_range_loop)]
20#![allow(clippy::collapsible_if)]
21
22use core::cmp::Ordering;
23use core::fmt;
24
25pub const MPZ_MAX_LIMBS: usize = 8;
31
32pub const MAX_BITS: usize = MPZ_MAX_LIMBS * 64;
34
35pub const MAX_DECIMAL_DIGITS: usize = 154;
38
39pub const LIMBS: usize = MPZ_MAX_LIMBS;
41
42const SMALL_PRIMES: [u64; 64] = [
44 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
45 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193,
46 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307,
47 311,
48];
49
50#[derive(Debug, Clone, Copy, PartialEq, Eq)]
56pub struct CapacityError;
57
58#[derive(Debug, Clone, Copy, PartialEq, Eq)]
60pub enum ParseError {
61 InvalidInput,
63 CapacityOverflow,
65}
66
67#[derive(Debug, Clone, Copy, PartialEq, Eq)]
69pub enum Endian {
70 Native,
72 Little,
74 Big,
76}
77
78const fn native_is_little() -> bool {
80 cfg!(target_endian = "little")
83}
84
85#[derive(Clone, Debug, Eq)]
97pub struct Mpz {
98 sign: i8,
100 len: usize,
102 mag: [u64; MPZ_MAX_LIMBS],
104}
105
106impl PartialEq for Mpz {
111 fn eq(&self, other: &Self) -> bool {
112 if self.sign != other.sign || self.len != other.len {
113 return false;
114 }
115 self.mag[..self.len] == other.mag[..other.len]
116 }
117}
118
119impl Default for Mpz {
120 fn default() -> Self {
121 Mpz::new()
122 }
123}
124
125impl fmt::Display for Mpz {
126 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
127 let mut buf = [0u8; 192];
128 let len = self.write_decimal_buf(&mut buf);
129 let s = core::str::from_utf8(&buf[..len]).map_err(|_| fmt::Error)?;
130 f.write_str(s)
131 }
132}
133
134impl PartialOrd for Mpz {
135 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
136 Some(Ord::cmp(self, other))
137 }
138}
139
140impl Ord for Mpz {
141 fn cmp(&self, other: &Self) -> Ordering {
142 Mpz::cmp(self, other)
143 }
144}
145
146impl core::ops::AddAssign<&Mpz> for Mpz {
148 fn add_assign(&mut self, other: &Mpz) {
149 *self = self.try_add(other).unwrap_or_else(|_| Mpz::new());
150 }
151}
152
153impl core::ops::SubAssign<&Mpz> for Mpz {
154 fn sub_assign(&mut self, other: &Mpz) {
155 *self = self.try_sub(other).unwrap_or_else(|_| Mpz::new());
156 }
157}
158
159impl core::ops::MulAssign<&Mpz> for Mpz {
160 fn mul_assign(&mut self, other: &Mpz) {
161 *self = self.try_mul(other).unwrap_or_else(|_| Mpz::new());
162 }
163}
164
165impl Mpz {
170 pub fn limbs(&self) -> &[u64] {
177 &self.mag[..self.len]
178 }
179
180 pub fn is_zero(&self) -> bool {
182 self.sign == 0
183 }
184
185 #[cfg(test)]
187 #[doc(hidden)]
188 pub fn __from_parts(sign: i8, len: usize, mag: [u64; MPZ_MAX_LIMBS]) -> Option<Self> {
189 if len > MPZ_MAX_LIMBS {
190 return None;
191 }
192 if len == 0 && sign != 0 {
193 return None;
194 }
195 if len > 0 && sign == 0 {
196 return None;
197 }
198 if len > 0 && mag[len - 1] == 0 {
199 return None;
200 }
201 Some(Mpz { sign, len, mag })
202 }
203
204 fn trim(&mut self) {
209 while self.len > 0 && self.mag[self.len - 1] == 0 {
210 self.len -= 1;
211 }
212 if self.len == 0 {
213 self.sign = 0;
214 }
215 }
216
217 fn mag_add_len(a: &[u64], b: &[u64], out: &mut [u64]) -> Option<usize> {
219 let max = a.len().max(b.len());
220 let mut carry = 0u128;
221 for i in 0..max {
222 let va = if i < a.len() { a[i] as u128 } else { 0 };
223 let vb = if i < b.len() { b[i] as u128 } else { 0 };
224 let s = va + vb + carry;
225 if i < out.len() {
226 out[i] = s as u64;
227 }
228 carry = s >> 64;
229 }
230 if carry != 0 {
231 if max >= MPZ_MAX_LIMBS {
232 return None;
233 }
234 out[max] = carry as u64;
235 Some(max + 1)
236 } else {
237 Some(max)
238 }
239 }
240
241 fn mag_sub_len(a: &[u64], b: &[u64], out: &mut [u64]) -> usize {
243 let mut borrow: i128 = 0;
244 for i in 0..a.len() {
245 let bi = if i < b.len() { b[i] as i128 } else { 0 };
246 let mut cur = a[i] as i128 - bi - borrow;
247 if cur < 0 {
248 cur += 1i128 << 64;
249 borrow = 1;
250 } else {
251 borrow = 0;
252 }
253 out[i] = cur as u64;
254 }
255 let mut rl = a.len();
256 while rl > 0 && out[rl - 1] == 0 {
257 rl -= 1;
258 }
259 rl
260 }
261
262 fn mag_mul_len(a: &[u64], b: &[u64], out: &mut [u64]) -> Option<usize> {
263 if a.is_empty() || b.is_empty() {
264 return Some(0);
265 }
266 let max_idx = if a.len() + b.len() > MPZ_MAX_LIMBS {
271 MPZ_MAX_LIMBS - 1
274 } else {
275 a.len() + b.len() - 1
276 };
277 for o in out.iter_mut().take(max_idx + 1) {
278 *o = 0;
279 }
280 for (i, &ai) in a.iter().enumerate() {
281 let mut carry = 0u128;
282 for (j, &bj) in b.iter().enumerate() {
284 let idx = i + j;
285 if idx > max_idx {
286 carry += ai as u128 * bj as u128;
290 break;
291 }
292 let cur = out[idx] as u128 + ai as u128 * bj as u128 + carry;
293 out[idx] = cur as u64;
294 carry = cur >> 64;
295 }
296 let next_idx = i + b.len();
298 if carry != 0 {
299 if next_idx > max_idx {
300 return None;
302 }
303 out[next_idx] = out[next_idx].wrapping_add(carry as u64);
304 }
305 }
306 let mut rl2 = max_idx + 1;
307 while rl2 > 0 && out[rl2 - 1] == 0 {
308 rl2 -= 1;
309 }
310 Some(rl2)
311 }
312
313 fn mag_divmod_u64_len(a: &[u64], d: u64, qbuf: &mut [u64]) -> (usize, u64) {
315 let mut rem: u128 = 0;
316 for i in (0..a.len()).rev() {
317 let cur = (rem << 64) | a[i] as u128;
318 qbuf[i] = (cur / d as u128) as u64;
319 rem = cur % d as u128;
320 }
321 let mut ql = a.len();
322 while ql > 0 && qbuf[ql - 1] == 0 {
323 ql -= 1;
324 }
325 (ql, rem as u64)
326 }
327
328 fn mag_divmod_knuth(
340 u: &[u64],
341 v: &[u64],
342 qbuf: &mut [u64],
343 rbuf: &mut [u64],
344 ) -> (usize, usize) {
345 let n = v.len();
346 let m = u.len() - n; for q in qbuf.iter_mut().take(m + 1) {
350 *q = 0;
351 }
352
353 let s = v[n - 1].leading_zeros();
355 let mut uu = [0u64; MPZ_MAX_LIMBS + 2]; let mut vv = [0u64; MPZ_MAX_LIMBS + 1]; if s == 0 {
360 vv[..n].copy_from_slice(v);
361 } else {
362 let mut carry = 0u64;
363 for i in 0..n {
364 let cur = (v[i] as u128) << s | carry as u128;
365 vv[i] = cur as u64;
366 carry = (cur >> 64) as u64;
367 }
368 }
369
370 if s == 0 {
372 uu[..u.len()].copy_from_slice(u);
373 uu[u.len()] = 0;
374 } else {
375 let mut carry = 0u64;
376 for i in 0..u.len() {
377 let cur = (u[i] as u128) << s | carry as u128;
378 uu[i] = cur as u64;
379 carry = (cur >> 64) as u64;
380 }
381 uu[u.len()] = carry;
382 }
383
384 let vn1 = vv[n - 1];
385 let vn2 = vv[n - 2];
386
387 for j in (0..=m).rev() {
389 let ujn = uu[j + n] as u128;
391 let ujn1 = uu[j + n - 1] as u128;
392 let ujn2 = if j + n >= 2 { uu[j + n - 2] as u128 } else { 0 };
393
394 let mut q_hat = if ujn == vn1 as u128 {
395 u64::MAX as u128
396 } else {
397 ((ujn << 64) | ujn1) / vn1 as u128
398 };
399
400 let mut r_hat = if ujn == vn1 as u128 {
402 (ujn << 64) | ujn1.wrapping_sub(q_hat * vn1 as u128)
405 } else {
406 ((ujn << 64) | ujn1) - q_hat * vn1 as u128
407 };
408
409 if q_hat >= (1u128 << 64) {
411 q_hat = u64::MAX as u128;
412 r_hat = (ujn << 64) | ujn1;
413 r_hat = r_hat.wrapping_sub(q_hat * vn1 as u128);
414 }
415
416 loop {
419 let qvn2 = q_hat * vn2 as u128;
421 let rhs = (r_hat << 64) | ujn2;
422 if qvn2 <= rhs {
423 break;
424 }
425 q_hat -= 1;
426 r_hat += vn1 as u128;
427 if r_hat >= (1u128 << 64) {
428 break;
430 }
431 }
432
433 let qh = q_hat as u64;
435 let mut borrow: i128 = 0;
436 for i in 0..n {
437 let (prod_lo, prod_hi) = umul(qh, vv[i]);
438 let total = prod_lo as i128 + borrow;
439 let mut cur = uu[j + i] as i128 - total;
440 if cur < 0 {
441 cur += 1i128 << 64;
442 borrow = (prod_hi as i128) + 1;
443 } else {
444 borrow = prod_hi as i128;
445 }
446 uu[j + i] = cur as u64;
447 }
448 let mut cur = uu[j + n] as i128 - borrow;
450 let needs_add_back = cur < 0;
451 if cur < 0 {
452 cur += 1i128 << 64;
453 }
454 uu[j + n] = cur as u64;
455
456 if needs_add_back {
458 let mut carry = 0u128;
460 for i in 0..n {
461 let sum = uu[j + i] as u128 + vv[i] as u128 + carry;
462 uu[j + i] = sum as u64;
463 carry = sum >> 64;
464 }
465 uu[j + n] = uu[j + n].wrapping_add(carry as u64);
466 qbuf[j] = qh.wrapping_sub(1);
467 } else {
468 qbuf[j] = qh;
469 }
470 }
471
472 if s == 0 {
474 rbuf[..n].copy_from_slice(&uu[..n]);
475 } else {
476 let mut carry = 0u64;
477 for i in (0..n).rev() {
478 let cur = (uu[i] as u128) << (64 - s) | carry as u128;
479 rbuf[i] = (cur >> 64) as u64;
480 carry = (cur & 0xFFFF_FFFF_FFFF_FFFF) as u64;
481 }
483 let mut carry2 = 0u64;
485 for i in (0..n).rev() {
486 let val = (carry2 as u128) << 64 | uu[i] as u128;
487 rbuf[i] = (val >> s) as u64;
488 carry2 = (val & ((1u128 << s) - 1)) as u64;
489 }
490 }
491
492 let mut rlen = n;
494 while rlen > 0 && rbuf[rlen - 1] == 0 {
495 rlen -= 1;
496 }
497
498 let mut qlen = m + 1;
500 while qlen > 0 && qbuf[qlen - 1] == 0 {
501 qlen -= 1;
502 }
503
504 (qlen, rlen)
505 }
506
507 fn cmp_mag_slice(a: &[u64], b: &[u64]) -> Ordering {
508 if a.len() != b.len() {
509 return a.len().cmp(&b.len());
510 }
511 for i in (0..a.len()).rev() {
512 match a[i].cmp(&b[i]) {
513 Ordering::Equal => {}
514 o => return o,
515 }
516 }
517 Ordering::Equal
518 }
519
520 #[allow(dead_code)]
525 fn pos_rem(&self, d: &Mpz) -> (Mpz, Mpz) {
526 let (q, r) = self.tdiv_qr(d);
527 if r.sign < 0 {
528 let one = Mpz::from_u64(1);
530 let adj_q = q.try_sub(&one).unwrap_or_else(|_| Mpz::new());
531 let adj_r = r.try_add(d).unwrap_or_else(|_| Mpz::new());
532 (adj_q, adj_r)
533 } else {
534 (q, r)
535 }
536 }
537
538 #[allow(dead_code)]
540 fn ceil_rem(&self, d: &Mpz) -> (Mpz, Mpz) {
541 let (q, r) = self.tdiv_qr(d);
542 if r.sign != 0 && r.sign != d.sign {
543 let one = Mpz::from_u64(1);
545 let adj_q = q.try_add(&one).unwrap_or_else(|_| Mpz::new());
546 let adj_r = r.try_sub(d).unwrap_or_else(|_| Mpz::new());
547 (adj_q, adj_r)
548 } else {
549 (q, r)
550 }
551 }
552
553 pub fn new() -> Self {
558 Mpz {
559 sign: 0,
560 len: 0,
561 mag: [0u64; MPZ_MAX_LIMBS],
562 }
563 }
564
565 pub fn from_u64(v: u64) -> Self {
566 if v == 0 {
567 Mpz::new()
568 } else {
569 let mut mag = [0u64; MPZ_MAX_LIMBS];
570 mag[0] = v;
571 Mpz {
572 sign: 1,
573 len: 1,
574 mag,
575 }
576 }
577 }
578
579 pub fn from_i64(v: i64) -> Self {
580 if v == 0 {
581 return Mpz::new();
582 }
583 let mut mag = [0u64; MPZ_MAX_LIMBS];
584 if v > 0 {
585 mag[0] = v as u64;
586 Mpz {
587 sign: 1,
588 len: 1,
589 mag,
590 }
591 } else {
592 mag[0] = (v as i128).unsigned_abs() as u64;
593 Mpz {
594 sign: -1,
595 len: 1,
596 mag,
597 }
598 }
599 }
600
601 pub fn from_u128(v: u128) -> Self {
602 if v == 0 {
603 return Mpz::new();
604 }
605 let mut mag = [0u64; MPZ_MAX_LIMBS];
606 mag[0] = v as u64;
607 mag[1] = (v >> 64) as u64;
608 let len = if mag[1] != 0 { 2 } else { 1 };
609 Mpz { sign: 1, len, mag }
610 }
611
612 pub fn from_i128(v: i128) -> Self {
613 if v == 0 {
614 return Mpz::new();
615 }
616 let u = v.unsigned_abs();
617 let mut m = Self::from_u128(u);
618 if v < 0 {
619 m.sign = -1;
620 }
621 m
622 }
623
624 pub fn set_ull(val: u64) -> Self {
626 Self::from_u64(val)
627 }
628
629 pub fn mpz_set_sll(val: i64) -> Self {
631 Self::from_i64(val)
632 }
633
634 pub fn from_limbs_checked(sign: i8, limbs: &[u64]) -> Option<Mpz> {
644 if !(-1..=1).contains(&sign) {
645 return None;
646 }
647 if limbs.len() > LIMBS {
648 return None;
649 }
650 let mut len = limbs.len();
652 while len > 0 && limbs[len - 1] == 0 {
653 len -= 1;
654 }
655 if len == 0 {
656 if sign == 0 {
657 return Some(Mpz::new());
658 }
659 return None; }
661 if sign == 0 {
662 return None; }
664 let mut mag = [0u64; LIMBS];
665 mag[..len].copy_from_slice(&limbs[..len]);
666 Some(Mpz { sign, len, mag })
667 }
668
669 pub fn swap(&mut self, other: &mut Self) {
671 core::mem::swap(self, other);
672 }
673
674 pub fn set(&mut self, src: &Self) {
676 *self = src.clone();
677 }
678
679 pub fn from_d(v: f64) -> Result<Mpz, CapacityError> {
684 let bits = v.to_bits();
685 let sign = if (bits >> 63) == 0 { 1i8 } else { -1i8 };
686 let exp = ((bits >> 52) & 0x7FF) as i32 - 1023; let mant = bits & 0x000F_FFFF_FFFF_FFFF; if exp < -1074 {
691 return Ok(Mpz::new());
693 }
694 if exp == -1023 {
695 if mant == 0 {
697 return Ok(Mpz::new());
698 }
699 return Ok(Mpz::new());
702 }
703
704 if exp == 1024 {
706 return Err(CapacityError);
707 }
708
709 let mut full_mant = (1u128 << 52) | mant as u128; let mut total_exp = exp;
712
713 total_exp -= 52;
715
716 if total_exp < 0 {
717 let shift = (-total_exp) as u32;
719 if shift >= 53 {
720 return Ok(Mpz::new());
721 }
722 full_mant >>= shift;
723 if full_mant == 0 {
724 return Ok(Mpz::new());
725 }
726 let mut r = Mpz::new();
727 r.mag[0] = full_mant as u64;
728 r.len = 1;
729 if full_mant > u64::MAX as u128 {
730 r.mag[0] = full_mant as u64;
731 r.mag[1] = (full_mant >> 64) as u64;
732 r.len = 2;
733 }
734 r.sign = sign;
735 r.trim();
736 return Ok(r);
737 }
738
739 if total_exp > 0 {
741 let shift = total_exp as u32;
742 let bits_needed = 53 + shift;
743 let limbs_needed = bits_needed.div_ceil(64) as usize;
744 if limbs_needed > MPZ_MAX_LIMBS {
745 return Err(CapacityError);
746 }
747 let ls = (shift / 64) as usize;
748 let bs = shift % 64;
749 let mut r = Mpz::new();
750 if bs == 0 {
751 r.mag[ls] = full_mant as u64;
752 if full_mant > u64::MAX as u128 {
753 r.mag[ls + 1] = (full_mant >> 64) as u64;
754 r.len = ls + 2;
755 } else {
756 r.len = ls + 1;
757 }
758 } else {
759 let lo = (full_mant as u64) << bs;
760 let hi = (full_mant >> (64 - bs)) as u64;
761 r.mag[ls] = lo;
762 if hi != 0 || ls + 1 < r.mag.len() {
763 r.mag[ls + 1] = hi;
764 if full_mant > u64::MAX as u128 {
765 }
768 }
769 let mut max_idx = ls + 1;
771 if hi != 0 {
772 max_idx = ls + 2;
773 }
774 if (full_mant >> (64 - bs)) != 0 {
776 }
778 for i in 0..max_idx.min(MPZ_MAX_LIMBS) {
780 if r.mag[i] != 0 {
781 r.len = i + 1;
782 }
783 }
784 }
785 r.sign = sign;
786 r.trim();
787 Ok(r)
788 } else {
789 if full_mant == 0 {
791 return Ok(Mpz::new());
792 }
793 let mut r = Mpz::new();
794 r.mag[0] = full_mant as u64;
795 r.len = 1;
796 if full_mant > u64::MAX as u128 {
797 r.mag[0] = full_mant as u64;
798 r.mag[1] = (full_mant >> 64) as u64;
799 r.len = 2;
800 }
801 r.sign = sign;
802 r.trim();
803 Ok(r)
804 }
805 }
806
807 pub fn mpz_get_ull(&self) -> u64 {
812 if self.len == 0 {
813 0
814 } else {
815 self.mag[0]
816 }
817 }
818
819 pub fn mpz_get_sll(&self) -> i64 {
820 if self.sign == 0 {
821 return 0;
822 }
823 let vtmp = self.mag[0];
824 if self.sign > 0 {
825 (vtmp as i64) & i64::MAX
826 } else {
827 !(((vtmp as i64).wrapping_sub(1)) & i64::MAX)
828 }
829 }
830
831 pub fn get_ui(&self) -> u64 {
832 if self.len == 0 {
833 0
834 } else {
835 self.mag[0]
836 }
837 }
838
839 pub fn get_si(&self) -> i64 {
840 let lo = self.get_ui();
841 if self.sign < 0 {
842 (lo as i64).wrapping_neg()
843 } else {
844 lo as i64
845 }
846 }
847
848 pub fn get_d(&self) -> f64 {
850 if self.len == 0 {
851 return 0.0;
852 }
853 let mut val = 0.0f64;
854 for i in (0..self.len).rev() {
855 val = val * 18446744073709551616.0_f64 + self.mag[i] as f64;
856 }
857 if self.sign < 0 {
858 -val
859 } else {
860 val
861 }
862 }
863
864 pub fn get_d_2exp(&self) -> Option<(f64, i64)> {
866 if self.len == 0 {
867 return None;
868 }
869 let bits = self.sizeinbase2();
870 let top_bit = bits - 1;
872 let shift = top_bit.saturating_sub(52);
873 let reduced = self.fdiv_q_2exp(shift as u32);
874 let mantissa = if self.sign < 0 {
875 -reduced.get_d()
876 } else {
877 reduced.get_d()
878 };
879 if mantissa == 0.0 {
881 return None;
882 }
883 let mut m = mantissa;
884 let mut e = shift as i64;
885 while m >= 1.0 {
886 m *= 0.5;
887 e += 1;
888 }
889 while m < 0.5 {
890 m *= 2.0;
891 e -= 1;
892 }
893 Some((m, e))
894 }
895
896 pub fn fits_ulong(&self) -> bool {
897 self.sign >= 0 && self.len <= 1
898 }
899
900 pub fn fits_slong(&self) -> bool {
902 self.len <= 1 && {
903 let val = self.mag[0];
904 if self.sign >= 0 {
905 val <= i64::MAX as u64
906 } else {
907 val <= (i64::MIN as i128).unsigned_abs() as u64 && val != 0
908 }
909 }
910 }
911
912 pub fn fits_uint(&self) -> bool {
914 self.sign >= 0 && self.len <= 1 && self.mag[0] <= u32::MAX as u64
915 }
916
917 pub fn fits_sint(&self) -> bool {
919 if self.len > 1 {
920 return false;
921 }
922 if self.len == 0 {
923 return true;
924 }
925 if self.sign >= 0 {
926 self.mag[0] <= i32::MAX as u64
927 } else {
928 self.mag[0] <= (i32::MIN as i64).unsigned_abs()
929 }
930 }
931
932 pub fn fits_ushort(&self) -> bool {
934 self.sign >= 0 && self.len <= 1 && self.mag[0] <= u16::MAX as u64
935 }
936
937 pub fn fits_sshort(&self) -> bool {
939 if self.len > 1 {
940 return false;
941 }
942 if self.len == 0 {
943 return true;
944 }
945 if self.sign >= 0 {
946 self.mag[0] <= i16::MAX as u64
947 } else {
948 self.mag[0] <= (i16::MIN as i64).unsigned_abs()
949 }
950 }
951
952 pub fn to_i128(&self) -> Option<i128> {
953 if self.len > 2 {
954 return None;
955 }
956 let u = (self.mag[0] as u128) | ((self.mag.get(1).copied().unwrap_or(0) as u128) << 64);
957 if self.sign < 0 {
958 if u <= i128::MAX as u128 + 1 {
959 Some((u as i128).wrapping_neg())
960 } else {
961 None
962 }
963 } else if u <= i128::MAX as u128 {
964 Some(u as i128)
965 } else {
966 None
967 }
968 }
969
970 pub fn set_ui(&mut self, v: u64) {
975 *self = Self::from_u64(v);
976 }
977
978 pub fn set_si(&mut self, v: i64) {
979 *self = Self::from_i64(v);
980 }
981
982 pub fn sgn(&self) -> i32 {
987 self.sign as i32
988 }
989
990 pub fn neg(&mut self) {
991 self.sign = -self.sign;
992 }
993
994 pub fn abs(&mut self) {
995 if self.sign != 0 {
996 self.sign = 1;
997 }
998 }
999
1000 pub fn neg_to(&self) -> Mpz {
1002 let mut c = self.clone();
1003 c.sign = -c.sign;
1004 c
1005 }
1006
1007 pub fn abs_to(&self) -> Mpz {
1009 let mut c = self.clone();
1010 if c.sign != 0 {
1011 c.sign = 1;
1012 }
1013 c
1014 }
1015
1016 pub fn cmp(&self, other: &Mpz) -> Ordering {
1017 match self.sign.cmp(&other.sign) {
1018 Ordering::Equal => {
1019 if self.sign == 0 {
1020 Ordering::Equal
1021 } else if self.sign > 0 {
1022 self.cmpabs(other)
1023 } else {
1024 self.cmpabs(other).reverse()
1025 }
1026 }
1027 o => o,
1028 }
1029 }
1030
1031 pub fn cmpabs(&self, other: &Mpz) -> Ordering {
1032 if self.len != other.len {
1033 return self.len.cmp(&other.len);
1034 }
1035 for i in (0..self.len).rev() {
1036 match self.mag[i].cmp(&other.mag[i]) {
1037 Ordering::Equal => {}
1038 o => return o,
1039 }
1040 }
1041 Ordering::Equal
1042 }
1043
1044 pub fn cmp_si(&self, v: i64) -> Ordering {
1046 self.cmp(&Mpz::from_i64(v))
1047 }
1048
1049 pub fn cmp_ui(&self, v: u64) -> Ordering {
1051 self.cmp(&Mpz::from_u64(v))
1052 }
1053
1054 pub fn cmpabs_ui(&self, v: u64) -> Ordering {
1056 self.cmpabs(&Mpz::from_u64(v))
1057 }
1058
1059 pub fn size(&self) -> usize {
1060 self.len
1061 }
1062
1063 pub fn sizeinbase2(&self) -> usize {
1064 if self.len == 0 {
1065 return 1;
1066 }
1067 (self.len - 1) * 64 + (64 - self.mag[self.len - 1].leading_zeros() as usize)
1068 }
1069
1070 pub fn try_sizeinbase(&self, base: i32) -> Option<usize> {
1083 if !(2..=36).contains(&base) {
1084 return None;
1085 }
1086 if self.len == 0 {
1087 return Some(1);
1088 }
1089 let bits = self.sizeinbase2();
1090
1091 let (num, den) = match base {
1093 2 => (1, 1),
1094 4 => (1, 2),
1095 8 => (1, 3),
1096 16 => (1, 4),
1097 32 => (1, 5),
1098 _ => {
1099 let abs_val = self.abs_to();
1101 let mut power = Mpz::from_u64(1);
1102 let base_mpz = Mpz::from_u64(base as u64);
1103 let mut k = 1u32;
1104 loop {
1105 power = power.try_mul(&base_mpz).ok()?;
1106 if power.cmpabs(&abs_val) == Ordering::Greater {
1107 break;
1108 }
1109 k += 1;
1110 if k > 1024 {
1116 break;
1118 }
1119 }
1120 let sz = k as usize;
1121 return Some(sz + if self.sign < 0 { 1 } else { 0 });
1122 }
1123 };
1124 let sz = (bits * num).div_ceil(den);
1125 Some(sz + if self.sign < 0 { 1 } else { 0 })
1126 }
1127
1128 pub fn odd_p(&self) -> bool {
1130 self.len > 0 && (self.mag[0] & 1) == 1
1131 }
1132
1133 pub fn even_p(&self) -> bool {
1135 self.len == 0 || (self.mag[0] & 1) == 0
1136 }
1137
1138 pub fn try_add(&self, other: &Mpz) -> Result<Mpz, CapacityError> {
1143 if self.sign == 0 {
1144 return Ok(other.clone());
1145 }
1146 if other.sign == 0 {
1147 return Ok(self.clone());
1148 }
1149 let mut result = Mpz::new();
1150 if self.sign == other.sign {
1151 let len = Self::mag_add_len(
1152 &self.mag[..self.len],
1153 &other.mag[..other.len],
1154 &mut result.mag,
1155 )
1156 .ok_or(CapacityError)?;
1157 result.sign = self.sign;
1158 result.len = len;
1159 Ok(result)
1160 } else {
1161 match self.cmpabs(other) {
1162 Ordering::Equal => Ok(Mpz::new()),
1163 Ordering::Greater => {
1164 let len = Self::mag_sub_len(
1165 &self.mag[..self.len],
1166 &other.mag[..other.len],
1167 &mut result.mag,
1168 );
1169 result.sign = self.sign;
1170 result.len = len;
1171 Ok(result)
1172 }
1173 Ordering::Less => {
1174 let len = Self::mag_sub_len(
1175 &other.mag[..other.len],
1176 &self.mag[..self.len],
1177 &mut result.mag,
1178 );
1179 result.sign = other.sign;
1180 result.len = len;
1181 Ok(result)
1182 }
1183 }
1184 }
1185 }
1186
1187 pub fn try_sub(&self, other: &Mpz) -> Result<Mpz, CapacityError> {
1188 let mut neg_other = other.clone();
1189 neg_other.sign = -neg_other.sign;
1190 self.try_add(&neg_other)
1191 }
1192
1193 pub fn try_add_ui(&self, v: u64) -> Result<Mpz, CapacityError> {
1194 self.try_add(&Mpz::from_u64(v))
1195 }
1196
1197 pub fn try_sub_ui(&self, v: u64) -> Result<Mpz, CapacityError> {
1198 self.try_sub(&Mpz::from_u64(v))
1199 }
1200
1201 pub fn try_ui_sub(v: u64, other: &Mpz) -> Result<Mpz, CapacityError> {
1203 Mpz::from_u64(v).try_sub(other)
1204 }
1205
1206 pub fn try_mul(&self, other: &Mpz) -> Result<Mpz, CapacityError> {
1207 let mut result = Mpz::new();
1208 let len = Self::mag_mul_len(
1209 &self.mag[..self.len],
1210 &other.mag[..other.len],
1211 &mut result.mag,
1212 )
1213 .ok_or(CapacityError)?;
1214 result.sign = self.sign * other.sign;
1215 result.len = len;
1216 result.trim();
1217 Ok(result)
1218 }
1219
1220 pub fn try_mul_ui(&self, v: u64) -> Result<Mpz, CapacityError> {
1221 self.try_mul(&Mpz::from_u64(v))
1222 }
1223
1224 pub fn try_mul_si(&self, v: i64) -> Result<Mpz, CapacityError> {
1226 self.try_mul(&Mpz::from_i64(v))
1227 }
1228
1229 pub fn try_addmul(&mut self, op1: &Mpz, op2: &Mpz) -> Result<(), CapacityError> {
1231 let prod = op1.try_mul(op2)?;
1232 *self = self.try_add(&prod)?;
1233 Ok(())
1234 }
1235
1236 pub fn try_addmul_ui(&mut self, op: &Mpz, v: u64) -> Result<(), CapacityError> {
1238 let prod = op.try_mul_ui(v)?;
1239 *self = self.try_add(&prod)?;
1240 Ok(())
1241 }
1242
1243 pub fn try_submul(&mut self, op1: &Mpz, op2: &Mpz) -> Result<(), CapacityError> {
1245 let prod = op1.try_mul(op2)?;
1246 *self = self.try_sub(&prod)?;
1247 Ok(())
1248 }
1249
1250 pub fn try_submul_ui(&mut self, op: &Mpz, v: u64) -> Result<(), CapacityError> {
1252 let prod = op.try_mul_ui(v)?;
1253 *self = self.try_sub(&prod)?;
1254 Ok(())
1255 }
1256
1257 pub fn try_mul_2exp(&self, bits: u32) -> Result<Mpz, CapacityError> {
1258 if self.sign == 0 {
1259 return Ok(Mpz::new());
1260 }
1261 let ls = (bits / 64) as usize;
1262 let bs = bits % 64;
1263 if ls >= MPZ_MAX_LIMBS || self.len > MPZ_MAX_LIMBS - ls {
1265 return Err(CapacityError);
1266 }
1267 let mut r = Mpz::new();
1268 if bs == 0 {
1269 r.mag[ls..ls + self.len].copy_from_slice(&self.mag[..self.len]);
1270 r.len = ls + self.len;
1271 } else {
1272 let mut carry = 0u64;
1273 let mut idx = ls;
1274 for &l in self.mag[..self.len].iter() {
1275 if idx >= MPZ_MAX_LIMBS {
1276 return Err(CapacityError);
1277 }
1278 r.mag[idx] = (l << bs) | carry;
1279 carry = l >> (64 - bs);
1280 idx += 1;
1281 }
1282 if carry != 0 {
1283 if idx >= MPZ_MAX_LIMBS {
1284 return Err(CapacityError);
1285 }
1286 r.mag[idx] = carry;
1287 r.len = idx + 1;
1288 } else {
1289 r.len = idx;
1290 }
1291 }
1292 r.sign = self.sign;
1293 r.trim();
1294 Ok(r)
1295 }
1296
1297 pub fn try_ui_pow_ui(base: u64, exp: u32) -> Result<Mpz, CapacityError> {
1298 Mpz::from_u64(base).try_pow_ui(exp)
1299 }
1300
1301 pub fn try_pow_ui(&self, n: u32) -> Result<Mpz, CapacityError> {
1302 let mut r = Mpz::from_u64(1);
1303 let mut base = self.clone();
1304 let mut e = n;
1305 while e != 0 {
1306 if e & 1 == 1 {
1307 r = r.try_mul(&base)?;
1308 }
1309 e >>= 1;
1310 if e != 0 {
1311 base = base.try_mul(&base)?;
1312 }
1313 }
1314 Ok(r)
1315 }
1316
1317 pub fn try_powm(&self, exp: &Mpz, m: &Mpz) -> Result<Mpz, CapacityError> {
1319 let mut r = Mpz::from_u64(1);
1320 let base = self.try_mod(m)?;
1321 let e_bits = exp.sizeinbase2();
1322 for i in (0..e_bits).rev() {
1323 if i < e_bits - 1 {
1324 r = r.try_mul(&r)?;
1325 r = r.try_mod(m)?;
1326 }
1327 if exp.tstbit(i as u32) {
1328 r = r.try_mul(&base)?;
1329 r = r.try_mod(m)?;
1330 }
1331 }
1332 Ok(r)
1333 }
1334
1335 pub fn try_powm_ui(&self, exp: u32, m: &Mpz) -> Result<Mpz, CapacityError> {
1337 self.try_powm(&Mpz::from_u64(exp as u64), m)
1338 }
1339
1340 fn mag_divmod(&self, d: &Mpz) -> (Mpz, Mpz) {
1345 if Self::cmp_mag_slice(&self.mag[..self.len], &d.mag[..d.len]) == Ordering::Less {
1346 return (Mpz::new(), self.clone());
1347 }
1348 let mut qbuf = [0u64; MPZ_MAX_LIMBS];
1349 let mut rbuf = [0u64; MPZ_MAX_LIMBS];
1350 let (qlen, rlen) = if d.len == 1 {
1351 let (qlen, r_u64) =
1353 Self::mag_divmod_u64_len(&self.mag[..self.len], d.mag[0], &mut qbuf);
1354 rbuf[0] = r_u64;
1355 let rlen = if r_u64 == 0 { 0 } else { 1 };
1356 (qlen, rlen)
1357 } else {
1358 Self::mag_divmod_knuth(&self.mag[..self.len], &d.mag[..d.len], &mut qbuf, &mut rbuf)
1360 };
1361 let mut q = Mpz::new();
1362 q.mag[..qlen].copy_from_slice(&qbuf[..qlen]);
1363 q.len = qlen;
1364 q.sign = if qlen == 0 { 0 } else { self.sign * d.sign };
1365 let mut r = Mpz::new();
1366 r.mag[..rlen].copy_from_slice(&rbuf[..rlen]);
1367 r.len = rlen;
1368 r.sign = if rlen == 0 { 0 } else { self.sign };
1369 (q, r)
1370 }
1371
1372 pub fn tdiv_qr(&self, d: &Mpz) -> (Mpz, Mpz) {
1373 if d.len == 0 {
1374 panic!("gmp-rs: division by zero");
1375 }
1376 let (mut q, mut r) = self.mag_divmod(d);
1377 for _ in 0..2 {
1380 if r.sign != 0 && r.cmpabs(d) != Ordering::Less {
1381 if r.sign == d.sign || r.sign == 0 {
1382 let qs = if r.sign == 0 { d.sign } else { r.sign };
1383 if qs > 0 {
1384 q = q.try_add(&Mpz::from_u64(1)).unwrap_or(q);
1385 } else {
1386 q = q.try_sub(&Mpz::from_u64(1)).unwrap_or(q);
1387 }
1388 r = r.try_sub(d).unwrap_or_else(|_| r.clone());
1389 } else {
1390 if q.sign > 0 {
1391 q = q.try_sub(&Mpz::from_u64(1)).unwrap_or(q);
1392 } else {
1393 q = q.try_add(&Mpz::from_u64(1)).unwrap_or(q);
1394 }
1395 r = r.try_add(d).unwrap_or_else(|_| r.clone());
1396 }
1397 }
1398 if r.sign != 0 && r.sign != self.sign {
1399 if self.sign > 0 {
1400 q = q.try_sub(&Mpz::from_u64(1)).unwrap_or(q);
1401 r = r.try_add(d).unwrap_or_else(|_| r.clone());
1402 } else {
1403 q = q.try_add(&Mpz::from_u64(1)).unwrap_or(q);
1404 r = r.try_sub(d).unwrap_or_else(|_| r.clone());
1405 }
1406 }
1407 }
1408 (q, r)
1416 }
1417
1418 pub fn tdiv_q(&self, d: &Mpz) -> Mpz {
1419 self.tdiv_qr(d).0
1420 }
1421
1422 pub fn tdiv_r(&self, d: &Mpz) -> Mpz {
1423 self.tdiv_qr(d).1
1424 }
1425
1426 pub fn tdiv_q_2exp(&self, bits: u32) -> Mpz {
1428 self.fdiv_q_2exp(bits)
1429 }
1430
1431 pub fn tdiv_r_2exp(&self, bits: u32) -> Mpz {
1433 self.fdiv_r_2exp(bits)
1434 }
1435
1436 fn mag_divmod_u64(&self, d: u64) -> (Mpz, u64) {
1437 let mut q = Mpz::new();
1438 let (qlen, rem) = Self::mag_divmod_u64_len(&self.mag[..self.len], d, &mut q.mag);
1439 q.len = qlen;
1440 q.sign = if qlen == 0 { 0 } else { self.sign };
1441 (q, rem)
1442 }
1443
1444 pub fn tdiv_q_ui(&self, d: u64) -> Mpz {
1445 let (q, _) = self.mag_divmod_u64(d);
1446 q
1447 }
1448
1449 pub fn tdiv_r_ui(&self, d: u64) -> Mpz {
1451 let (_, r_u64) = self.mag_divmod_u64(d);
1452 Mpz::from_u64(r_u64)
1453 }
1454
1455 pub fn tdiv_ui(&self, d: u64) -> u64 {
1456 self.mag_divmod_u64(d).1
1457 }
1458
1459 pub fn try_fdiv_qr(&self, d: &Mpz) -> Result<(Mpz, Mpz), CapacityError> {
1464 let (q, r) = self.tdiv_qr(d);
1465 if r.sign != 0 && r.sign != d.sign {
1466 let one = Mpz::from_u64(1);
1467 let adj_q = q.try_sub(&one)?;
1468 let adj_r = r.try_add(d)?;
1469 Ok((adj_q, adj_r))
1470 } else {
1471 Ok((q, r))
1472 }
1473 }
1474
1475 pub fn try_fdiv_q(&self, d: &Mpz) -> Result<Mpz, CapacityError> {
1476 self.try_fdiv_qr(d).map(|(q, _)| q)
1477 }
1478
1479 pub fn try_fdiv_r(&self, d: &Mpz) -> Result<Mpz, CapacityError> {
1480 self.try_fdiv_qr(d).map(|(_, r)| r)
1481 }
1482
1483 pub fn try_fdiv_qr_ui(&self, d: u64) -> Result<(Mpz, u64), CapacityError> {
1485 let d_mpz = Mpz::from_u64(d);
1486 let (q, r) = self.try_fdiv_qr(&d_mpz)?;
1487 let r_u64 = r.get_ui();
1488 if r.sign < 0 {
1489 Ok((q, r_u64.wrapping_neg()))
1490 } else {
1491 Ok((q, r_u64))
1492 }
1493 }
1494
1495 pub fn try_fdiv_q_ui(&self, d: u64) -> Result<Mpz, CapacityError> {
1496 self.try_fdiv_qr_ui(d).map(|(q, _)| q)
1497 }
1498
1499 pub fn fdiv_ui(&self, d: u64) -> u64 {
1500 let (_, r) = self.mag_divmod_u64(d);
1501 if self.sign < 0 && r != 0 {
1502 d - r
1503 } else {
1504 r
1505 }
1506 }
1507
1508 pub fn try_cdiv_qr(&self, d: &Mpz) -> Result<(Mpz, Mpz), CapacityError> {
1513 let (q, r) = self.tdiv_qr(d);
1514 if r.sign != 0 && r.sign != d.sign {
1515 let neg_self = self.neg_to();
1517 let (fq, _) = neg_self.try_fdiv_qr(d)?;
1518 let q_ceil = fq.neg_to();
1519 let r_ceil = self.try_sub(&q_ceil.try_mul(d)?)?;
1520 Ok((q_ceil, r_ceil))
1521 } else {
1522 Ok((q, r))
1523 }
1524 }
1525
1526 pub fn try_cdiv_q(&self, d: &Mpz) -> Result<Mpz, CapacityError> {
1527 self.try_cdiv_qr(d).map(|(q, _)| q)
1528 }
1529
1530 pub fn try_cdiv_r(&self, d: &Mpz) -> Result<Mpz, CapacityError> {
1531 self.try_cdiv_qr(d).map(|(_, r)| r)
1532 }
1533
1534 pub fn try_cdiv_q_ui(&self, d: u64) -> Result<Mpz, CapacityError> {
1540 self.try_cdiv_q(&Mpz::from_u64(d))
1541 }
1542
1543 pub fn try_cdiv_r_ui(&self, d: u64) -> Result<Mpz, CapacityError> {
1545 self.try_cdiv_r(&Mpz::from_u64(d))
1546 }
1547
1548 pub fn try_cdiv_qr_ui(&self, d: u64) -> Result<(Mpz, u64), CapacityError> {
1551 let d_mpz = Mpz::from_u64(d);
1552 let (q, r) = self.try_cdiv_qr(&d_mpz)?;
1553 let r_u64 = r.get_ui();
1555 Ok((q, r_u64))
1556 }
1557
1558 pub fn cdiv_ui(&self, d: u64) -> u64 {
1560 let (_, r) = self.mag_divmod_u64(d);
1561 if self.sign > 0 && r != 0 {
1562 d - r
1563 } else {
1564 r
1565 }
1566 }
1567
1568 pub fn cdiv_q_2exp(&self, bits: u32) -> Mpz {
1570 let q = self.fdiv_q_2exp(bits);
1571 if self.sign >= 0 {
1572 let r = self.tdiv_r_2exp(bits);
1574 if r.is_zero() {
1575 q
1576 } else {
1577 q.try_add_ui(1).unwrap_or(q)
1578 }
1579 } else {
1580 let neg = self.neg_to();
1583 let floor_neg = neg.fdiv_q_2exp(bits);
1584 if floor_neg.is_zero() {
1585 Mpz::new()
1586 } else {
1587 let neg_r = neg.tdiv_r_2exp(bits);
1588 if neg_r.is_zero() {
1589 let mut r = floor_neg;
1591 r.sign = -r.sign;
1592 r
1593 } else {
1594 let mut r = floor_neg;
1603 r.sign = -r.sign;
1604 r
1605 }
1606 }
1607 }
1608 }
1609
1610 pub fn cdiv_r_2exp(&self, bits: u32) -> Mpz {
1613 let q = self.cdiv_q_2exp(bits);
1614 let q_times_mod = q.try_mul_2exp(bits).unwrap_or_else(|_| Mpz::new());
1615
1616 self.try_sub(&q_times_mod).unwrap_or_else(|_| Mpz::new())
1617 }
1618
1619 pub fn try_tdiv_qr_ui(&self, d: u64) -> Result<(Mpz, u64), CapacityError> {
1622 let d_mpz = Mpz::from_u64(d);
1623 let (q, r) = self.tdiv_qr(&d_mpz);
1624 let r_abs = r.get_ui();
1626 if r.sign < 0 {
1627 Ok((q, r_abs))
1629 } else {
1630 Ok((q, r_abs))
1631 }
1632 }
1633
1634 pub fn try_fdiv_r_ui(&self, d: u64) -> Result<Mpz, CapacityError> {
1636 let (_, r) = self.try_fdiv_qr(&Mpz::from_u64(d))?;
1637 Ok(r)
1638 }
1639
1640 pub fn try_mod(&self, d: &Mpz) -> Result<Mpz, CapacityError> {
1646 let r = self.tdiv_r(d);
1647 if r.sign < 0 {
1648 r.try_add(d)
1649 } else {
1650 Ok(r)
1651 }
1652 }
1653
1654 pub fn mod_ui(&self, d: u64) -> u64 {
1656 self.fdiv_ui(d)
1657 }
1658
1659 pub fn try_divexact(&self, d: &Mpz) -> Result<Mpz, CapacityError> {
1665 Ok(self.tdiv_q(d))
1666 }
1667
1668 pub fn try_divexact_ui(&self, d: u64) -> Result<Mpz, CapacityError> {
1670 Ok(self.tdiv_q_ui(d))
1671 }
1672
1673 pub fn divisible_ui(&self, d: u64) -> bool {
1678 self.sign == 0 || self.mag_divmod_u64(d).1 == 0
1679 }
1680
1681 pub fn divisible_p(&self, d: &Mpz) -> bool {
1683 if d.len == 0 {
1684 return false;
1685 }
1686 if self.sign == 0 {
1687 return true;
1688 }
1689 let r = self.tdiv_r(d);
1690 r.sign == 0
1691 }
1692
1693 pub fn divisible_2exp_p(&self, bits: u32) -> bool {
1695 if self.len == 0 {
1696 return true;
1697 }
1698 let limb = (bits / 64) as usize;
1699 let bit = bits % 64;
1700 for i in 0..limb.min(self.len) {
1701 if self.mag[i] != 0 {
1702 return false;
1703 }
1704 }
1705 if limb < self.len && bit > 0 {
1706 let mask = (1u64 << bit) - 1;
1707 if self.mag[limb] & mask != 0 {
1708 return false;
1709 }
1710 }
1711 true
1712 }
1713
1714 pub fn congruent_p(&self, c: &Mpz, d: &Mpz) -> bool {
1716 let diff = self.try_sub(c).unwrap_or_else(|_| Mpz::new());
1717 diff.divisible_p(d)
1718 }
1719
1720 pub fn congruent_ui_p(&self, c: u64, d: u64) -> bool {
1722 if d == 0 {
1723 return false;
1724 }
1725 let r1 = self.tdiv_ui(d);
1726 let r2 = c % d;
1727 r1 == r2
1728 }
1729
1730 pub fn congruent_2exp_p(&self, c: &Mpz, bits: u32) -> bool {
1734 let a_bits = self.twos_complement_low_bits(bits);
1736 let b_bits = c.twos_complement_low_bits(bits);
1737 a_bits == b_bits
1738 }
1739
1740 fn twos_complement_low_bits(&self, bits: u32) -> u128 {
1742 if bits == 0 {
1743 return 0;
1744 }
1745 let n_limbs = bits.div_ceil(64) as usize;
1746 let n_limbs_for_mask = n_limbs.min(MPZ_MAX_LIMBS);
1747 let _limb_mask_bits = bits % 64;
1748
1749 let mut val = 0u128;
1751 if self.sign >= 0 {
1752 for i in 0..n_limbs_for_mask {
1754 if i < self.len {
1755 val |= (self.mag[i] as u128) << (i * 64);
1756 }
1757 }
1758 } else {
1759 let mut carry = 1u128;
1761 for i in 0..n_limbs_for_mask {
1762 let inv = (!if i < self.len { self.mag[i] } else { 0 }) as u128;
1763 let sum = inv + carry;
1764 val |= (sum & 0xFFFF_FFFF_FFFF_FFFF) << (i * 64);
1765 carry = sum >> 64;
1766 }
1767 if n_limbs_for_mask > self.len && self.len > 0 {
1769 }
1773 }
1774
1775 if bits < 128 {
1777 val &= (1u128 << bits) - 1;
1778 }
1779 val
1780 }
1781
1782 pub fn fdiv_r_2exp(&self, bits: u32) -> Mpz {
1787 if self.sign == 0 {
1788 return Mpz::new();
1789 }
1790 let limbs = (bits / 64) as usize;
1791 let rem_bits = bits % 64;
1792 let mut result = self.clone();
1793 if limbs < MPZ_MAX_LIMBS {
1794 if rem_bits != 0 && result.len > limbs {
1795 result.mag[limbs] &= (1u64 << rem_bits) - 1;
1796 }
1797 for i in (limbs + if rem_bits != 0 { 1 } else { 0 })..result.len {
1798 result.mag[i] = 0;
1799 }
1800 }
1801 result.trim();
1802 result
1803 }
1804
1805 pub fn fdiv_q_2exp(&self, bits: u32) -> Mpz {
1806 if self.sign == 0 {
1807 return Mpz::new();
1808 }
1809 let ls = (bits / 64) as usize;
1810 let bs = bits % 64;
1811 if ls >= self.len {
1812 return Mpz::new();
1813 }
1814 let mut result = Mpz::new();
1815 let src_len = self.len - ls;
1816 result.mag[..src_len].copy_from_slice(&self.mag[ls..self.len]);
1817 result.len = src_len;
1818 result.sign = self.sign;
1819 if bs != 0 {
1820 let mut carry = 0u64;
1821 for i in (0..result.len).rev() {
1822 let new = (result.mag[i] >> bs) | carry;
1823 carry = result.mag[i] << (64 - bs);
1824 result.mag[i] = new;
1825 }
1826 }
1827 result.trim();
1828 result
1829 }
1830
1831 pub fn isqrt(&self) -> Mpz {
1836 if self.sgn() <= 0 {
1837 return Mpz::new();
1838 }
1839 let mut x = Mpz::from_u64(1);
1840 let shift = self.sizeinbase2().div_ceil(2) as u32;
1841 x = x.try_mul_2exp(shift).unwrap_or(
1842 Mpz::from_u64(1)
1843 .try_mul_2exp(127)
1844 .unwrap_or(Mpz::from_u64(1)),
1845 );
1846 loop {
1847 let y = x.try_add(&self.tdiv_q(&x)).unwrap().fdiv_q_2exp(1);
1848 if y.cmp(&x) != Ordering::Less {
1849 return x;
1850 }
1851 x = y;
1852 }
1853 }
1854
1855 pub fn try_sqrtrem(&self) -> Result<(Mpz, Mpz), CapacityError> {
1857 let root = self.isqrt();
1858 let rem = self.try_sub(&root.try_mul(&root)?)?;
1859 Ok((root, rem))
1860 }
1861
1862 pub fn try_root(&self, n: u32) -> Result<Mpz, CapacityError> {
1864 if self.sgn() <= 0 || n == 0 {
1865 return Ok(Mpz::new());
1866 }
1867 if n == 1 {
1868 return Ok(self.clone());
1869 }
1870 if n == 2 {
1871 return Ok(self.isqrt());
1872 }
1873 let bits = self.sizeinbase2();
1874 let shift = (bits as u32).div_ceil(n);
1875 let mut x = Mpz::from_u64(2).try_pow_ui(shift)?;
1876 let nm1 = Mpz::from_u64((n - 1) as u64);
1877 loop {
1878 let x_pow_nm1 = x.try_pow_ui(n - 1)?;
1879 let quotient = self.tdiv_q(&x_pow_nm1);
1880 let sum = x.try_mul(&nm1)?.try_add("ient)?;
1881 let y = sum.tdiv_q_ui(n as u64);
1882 if y.cmp(&x) != Ordering::Less {
1883 let y_p1 = y.try_add(&Mpz::from_u64(1))?;
1884 let y_p1_pow = y_p1.try_pow_ui(n)?;
1885 if y_p1_pow.cmp(self) == Ordering::Greater {
1886 return Ok(y);
1887 }
1888 return Ok(x);
1889 }
1890 x = y;
1891 }
1892 }
1893
1894 pub fn try_rootrem(&self, n: u32) -> Result<(Mpz, Mpz), CapacityError> {
1896 let root = self.try_root(n)?;
1897 let root_pow = root.try_pow_ui(n)?;
1898 let rem = self.try_sub(&root_pow)?;
1899 Ok((root, rem))
1900 }
1901
1902 pub fn perfect_square_p(&self) -> bool {
1904 if self.sgn() < 0 {
1905 return false;
1906 }
1907 let root = self.isqrt();
1908 root.try_mul(&root).map(|sq| sq == *self).unwrap_or(false)
1909 }
1910
1911 pub fn perfect_power_p(&self) -> bool {
1913 if self.sgn() <= 0 {
1914 return false;
1915 }
1916 if self.len == 1 {
1917 let v = self.mag[0];
1918 if v < 4 {
1919 return false;
1920 }
1921 for k in 2..64 {
1922 if (1u64 << k) > v {
1923 break;
1924 }
1925 let mut lo = 2u64;
1926 let mut hi = 1u64 << (63 / k + 1);
1927 hi = hi.min(v).min(1 << 26);
1928 while lo < hi {
1929 let mid = lo + (hi - lo) / 2;
1930 let mut pow = 1u128;
1931 for _ in 0..k {
1932 pow = pow.wrapping_mul(mid as u128);
1933 }
1934 if pow >= v as u128 {
1935 hi = mid;
1936 } else {
1937 lo = mid + 1;
1938 }
1939 }
1940 let mut pow = 1u128;
1941 for _ in 0..k {
1942 pow = pow.wrapping_mul(lo as u128);
1943 }
1944 if pow == v as u128 {
1945 return true;
1946 }
1947 }
1948 false
1949 } else {
1950 let max_k = self.sizeinbase2();
1951 for k in 2..=max_k.min(64) as u32 {
1952 if let Ok(root) = self.try_root(k) {
1953 if root.try_pow_ui(k).map(|p| p == *self).unwrap_or(false) {
1954 return true;
1955 }
1956 }
1957 }
1958 false
1959 }
1960 }
1961
1962 pub fn remove_pow10(&mut self) -> u32 {
1967 if self.sign == 0 {
1968 return 0;
1969 }
1970 let mut count = 0;
1971 loop {
1972 let mut qbuf = [0u64; MPZ_MAX_LIMBS];
1973 let (qlen, r) = Self::mag_divmod_u64_len(&self.mag[..self.len], 10, &mut qbuf);
1974 if r != 0 {
1975 break;
1976 }
1977 self.mag[..qlen].copy_from_slice(&qbuf[..qlen]);
1978 self.len = qlen;
1979 count += 1;
1980 }
1981 self.trim();
1982 count
1983 }
1984
1985 pub fn com(&self) -> Mpz {
1987 let one = Mpz::from_u64(1);
1988 let mut r = self.try_add(&one).unwrap_or_else(|_| Mpz::new());
1989 r.sign = -r.sign;
1990 r
1991 }
1992
1993 pub fn try_remove(&self, f: &Mpz) -> Result<(Mpz, u32), CapacityError> {
1995 if self.sign == 0 {
1996 return Ok((Mpz::new(), 0));
1997 }
1998 if f.len == 0 {
1999 return Err(CapacityError);
2000 }
2001 if f.len == 1 && f.mag[0] == 1 {
2002 return Ok((self.clone(), 0));
2003 }
2004 let mut val = self.clone();
2005 let mut count = 0;
2006 loop {
2007 let (q, r) = val.tdiv_qr(f);
2008 if r.sign != 0 {
2009 break;
2010 }
2011 val = q;
2012 count += 1;
2013 }
2014 Ok((val, count))
2015 }
2016
2017 pub fn try_gcd(&self, other: &Mpz) -> Result<Mpz, CapacityError> {
2023 let mut a = self.abs_to();
2024 let mut b = other.abs_to();
2025 if a.len == 0 {
2026 return Ok(b);
2027 }
2028 if b.len == 0 {
2029 return Ok(a);
2030 }
2031 let a_tz = a.mag[0].trailing_zeros();
2032 let b_tz = b.mag[0].trailing_zeros();
2033 let shift = a_tz.min(b_tz);
2034 a = a.fdiv_q_2exp(a_tz);
2035 b = b.fdiv_q_2exp(b_tz);
2036 loop {
2037 if a.len == 0 {
2038 b = b.try_mul_2exp(shift)?;
2039 b.sign = 1;
2040 return Ok(b);
2041 }
2042 if b.len == 0 {
2043 a = a.try_mul_2exp(shift)?;
2044 a.sign = 1;
2045 return Ok(a);
2046 }
2047 let cmp = a.cmpabs(&b);
2048 if cmp == Ordering::Greater || cmp == Ordering::Equal {
2049 a = a.try_sub(&b)?;
2050 a = a.fdiv_q_2exp(a.mag[0].trailing_zeros());
2051 } else {
2052 b = b.try_sub(&a)?;
2053 b = b.fdiv_q_2exp(b.mag[0].trailing_zeros());
2054 }
2055 }
2056 }
2057
2058 pub fn gcd_ui(&self, v: u64) -> u64 {
2060 if v == 0 {
2061 return self.get_ui();
2062 }
2063 let mut a = self.get_ui();
2064 let mut b = v;
2065 while b != 0 {
2066 let t = b;
2067 b = a % b;
2068 a = t;
2069 }
2070 a
2071 }
2072
2073 pub fn try_gcdext(&self, other: &Mpz) -> Result<(Mpz, Mpz, Mpz), CapacityError> {
2075 let mut old_r = self.abs_to();
2076 let mut r = other.abs_to();
2077 let mut old_s = Mpz::from_u64(1);
2078 let mut s = Mpz::new();
2079 let mut old_t = Mpz::new();
2080 let mut t = Mpz::from_u64(1);
2081 while r.len != 0 {
2082 let (q, _) = old_r.tdiv_qr(&r);
2083 let new_r = old_r.try_sub(&q.try_mul(&r)?)?;
2084 let new_s = old_s.try_sub(&q.try_mul(&s)?)?;
2085 let new_t = old_t.try_sub(&q.try_mul(&t)?)?;
2086 old_r = r;
2087 r = new_r;
2088 old_s = s;
2089 s = new_s;
2090 old_t = t;
2091 t = new_t;
2092 }
2093 let mut g = old_r;
2094 if self.sign < 0 {
2095 g.sign = -g.sign;
2096 old_s.sign = -old_s.sign;
2097 }
2098 if other.sign < 0 {
2099 old_t.sign = -old_t.sign;
2100 }
2101 Ok((g, old_s, old_t))
2102 }
2103
2104 pub fn try_lcm(&self, other: &Mpz) -> Result<Mpz, CapacityError> {
2106 if self.len == 0 || other.len == 0 {
2107 return Ok(Mpz::new());
2108 }
2109 let g = self.try_gcd(other)?;
2110 let q = self.tdiv_q(&g);
2111 q.try_mul(other)
2112 }
2113
2114 pub fn try_lcm_ui(&self, v: u64) -> Result<Mpz, CapacityError> {
2116 self.try_lcm(&Mpz::from_u64(v))
2117 }
2118
2119 pub fn try_invert(&self, m: &Mpz) -> Result<Mpz, ()> {
2121 if m.len == 0 {
2122 return Err(());
2123 }
2124 let (g, s, _t) = self.try_gcdext(m).map_err(|_| ())?;
2125 if g.len != 1 || g.mag[0] != 1 {
2126 return Err(());
2127 }
2128 let mut r = s.try_mod(m).map_err(|_| ())?;
2129 if r.sign < 0 {
2130 r = r.try_add(m).map_err(|_| ())?;
2131 }
2132 Ok(r)
2133 }
2134
2135 pub fn jacobi(&self, other: &Mpz) -> i32 {
2137 if other.even_p() {
2138 return 0;
2139 }
2140 let mut n = other.abs_to();
2141 if n.len == 1 && n.mag[0] == 1 {
2143 return 1;
2144 }
2145 let mut a = self.try_mod(&n).unwrap_or_else(|_| Mpz::new());
2146 if a.is_zero() {
2148 return 0;
2149 }
2150 let mut t = 1i32;
2151 loop {
2152 let mut e = 0u32;
2153 while a.even_p() && !a.is_zero() {
2154 a = a.fdiv_q_2exp(1);
2155 e += 1;
2156 }
2157 if e % 2 == 1 {
2158 let n_mod_8 = n.mag[0] & 7;
2159 if n_mod_8 == 3 || n_mod_8 == 5 {
2160 t = -t;
2161 }
2162 }
2163 core::mem::swap(&mut a, &mut n);
2165 if a.len > 0 && n.len > 0 && a.mag[0] % 4 == 3 && n.mag[0] % 4 == 3 {
2166 t = -t;
2167 }
2168 a = a.try_mod(&n).unwrap_or_else(|_| Mpz::new());
2169 if a.is_zero() {
2170 if n.len == 1 && n.mag[0] == 1 {
2172 return t;
2173 }
2174 return 0;
2175 }
2176 if n.len == 1 && n.mag[0] == 1 {
2177 return t;
2178 }
2179 }
2180 }
2181
2182 pub fn try_legendre(&self, p: &Mpz) -> i32 {
2184 self.jacobi(p)
2185 }
2186
2187 pub fn try_kronecker(&self, other: &Mpz) -> i32 {
2191 if other.is_zero() {
2192 return if self.len == 1 && self.mag[0] == 1 {
2194 1
2195 } else {
2196 0
2197 };
2198 }
2199 if other.sign < 0 {
2200 let pos = other.abs_to();
2204 let j = self.try_kronecker(&pos);
2205 if self.sign < 0 {
2206 -j
2207 } else {
2208 j
2209 }
2210 } else {
2211 self.jacobi(other)
2212 }
2213 }
2214
2215 pub fn try_kronecker_si(&self, a: i64) -> i32 {
2217 Self::try_si_kronecker(a, self)
2218 }
2219
2220 pub fn try_kronecker_ui(&self, a: u64) -> i32 {
2222 Self::try_ui_kronecker(a, self)
2223 }
2224
2225 pub fn try_si_kronecker(a: i64, other: &Mpz) -> i32 {
2227 Mpz::from_i64(a).try_kronecker(other)
2228 }
2229
2230 pub fn try_ui_kronecker(a: u64, other: &Mpz) -> i32 {
2232 Mpz::from_u64(a).try_kronecker(other)
2233 }
2234
2235 pub fn try_fac_ui(n: u32) -> Result<Mpz, CapacityError> {
2237 let mut r = Mpz::from_u64(1);
2238 for i in 2..=n as u64 {
2239 r = r.try_mul_ui(i)?;
2240 }
2241 Ok(r)
2242 }
2243
2244 pub fn try_2fac_ui(n: u32) -> Result<Mpz, CapacityError> {
2249 if n <= 1 {
2250 return Ok(Mpz::from_u64(1));
2251 }
2252 let mut r = Mpz::from_u64(n as u64);
2253 let mut i = n as u64;
2254 loop {
2255 if i < 2 {
2256 break;
2257 }
2258 i = i.wrapping_sub(2);
2259 if i == 0 {
2260 break;
2261 }
2262 r = r.try_mul_ui(i)?;
2263 }
2264 Ok(r)
2265 }
2266
2267 pub fn try_primorial_ui(n: u32) -> Result<Mpz, CapacityError> {
2269 if n <= 1 {
2270 return Ok(Mpz::from_u64(1));
2271 }
2272 let mut r = Mpz::from_u64(1);
2273 for &p in SMALL_PRIMES.iter() {
2274 if p > n as u64 {
2275 break;
2276 }
2277 r = r.try_mul_ui(p)?;
2278 }
2279 Ok(r)
2280 }
2281
2282 pub fn try_bin_uiui(n: u32, k: u32) -> Result<Mpz, CapacityError> {
2284 let k = k.min(n - k);
2285 if k == 0 {
2286 return Ok(Mpz::from_u64(1));
2287 }
2288 let mut r = Mpz::from_u64(n as u64 - k as u64 + 1);
2289 for i in 2..=k {
2290 r = r.try_mul_ui(n as u64 - k as u64 + i as u64)?;
2291 r = r.tdiv_q_ui(i as u64);
2292 }
2293 Ok(r)
2294 }
2295
2296 pub fn try_bin_ui(&self, k: u32) -> Result<Mpz, CapacityError> {
2299 if self.sign < 0 {
2300 let neg = self.neg_to(); let km1 = Mpz::from_u64(k as u64);
2303 let adjusted = neg.try_add(&km1)?; let _abs_k = k.min(k);
2305 let mut r = adjusted.try_bin_uiui_rec(k)?;
2306 if k % 2 == 1 {
2307 r.sign = -r.sign;
2308 }
2309 Ok(r)
2310 } else {
2311 self.try_bin_uiui_rec(k)
2312 }
2313 }
2314
2315 fn try_bin_uiui_rec(&self, k: u32) -> Result<Mpz, CapacityError> {
2318 if self.is_zero() {
2319 return if k == 0 {
2320 Ok(Mpz::from_u64(1))
2321 } else {
2322 Ok(Mpz::new())
2323 };
2324 }
2325 if k == 0 {
2326 return Ok(Mpz::from_u64(1));
2327 }
2328 if self.len == 1 && (self.mag[0] as u128) < k as u128 {
2331 return Ok(Mpz::new());
2332 }
2333 if self.len > 1 {
2334 }
2336 let k = k.min(if self.len == 1 && self.mag[0] <= u32::MAX as u64 {
2337 self.mag[0] as u32
2338 } else {
2339 k
2340 });
2341 let _k_min = k.min(if self.len == 1 {
2342 (self.mag[0] as u32).saturating_sub(k)
2343 } else {
2344 k
2345 });
2346 let n_val = if self.len == 1 { self.mag[0] } else { u64::MAX };
2348 let k_actual = if self.len == 1 && (k as u64) > n_val / 2 {
2349 (n_val - k as u64) as u32
2350 } else {
2351 k
2352 };
2353 let k = k_actual;
2354
2355 let n_minus_k = if self.len == 1 {
2356 Mpz::from_u64(self.mag[0] - k as u64)
2357 } else {
2358 self.try_sub(&Mpz::from_u64(k as u64))?
2360 };
2361
2362 let mut r = Mpz::from_u64(1);
2363 for i in 1..=k {
2364 let term = n_minus_k.try_add_ui(i as u64)?;
2365 r = r.try_mul(&term)?;
2366 r = r.tdiv_q_ui(i as u64);
2367 }
2368 Ok(r)
2369 }
2370
2371 pub fn try_fib_ui(n: u32) -> Result<Mpz, CapacityError> {
2373 if n == 0 {
2374 return Ok(Mpz::new());
2375 }
2376 if n == 1 {
2377 return Ok(Mpz::from_u64(1));
2378 }
2379 let mut a = Mpz::new(); let mut b = Mpz::from_u64(1); for _ in 2..=n {
2382 let c = a.try_add(&b)?;
2383 a = b;
2384 b = c;
2385 }
2386 Ok(b)
2387 }
2388
2389 pub fn try_fib2_ui(n: u32) -> Result<(Mpz, Mpz), CapacityError> {
2391 if n == 0 {
2392 return Ok((Mpz::new(), Mpz::from_u64(1)));
2393 }
2394 if n == 1 {
2395 return Ok((Mpz::from_u64(1), Mpz::new()));
2396 }
2397 let mut a = Mpz::new(); let mut b = Mpz::from_u64(1); for _ in 2..=n {
2400 let c = a.try_add(&b)?;
2401 a = b;
2402 b = c;
2403 }
2404 Ok((b.clone(), a))
2405 }
2406
2407 pub fn try_lucnum_ui(n: u32) -> Result<Mpz, CapacityError> {
2409 if n == 0 {
2410 return Ok(Mpz::from_u64(2));
2411 }
2412 if n == 1 {
2413 return Ok(Mpz::from_u64(1));
2414 }
2415 let mut a = Mpz::from_u64(2); let mut b = Mpz::from_u64(1); for _ in 2..=n {
2418 let c = a.try_add(&b)?;
2419 a = b;
2420 b = c;
2421 }
2422 Ok(b)
2423 }
2424
2425 pub fn try_lucnum2_ui(n: u32) -> Result<(Mpz, Mpz), CapacityError> {
2427 if n == 0 {
2428 return Ok((Mpz::from_u64(2), Mpz::from_i64(-1)));
2429 }
2430 if n == 1 {
2431 return Ok((Mpz::from_u64(1), Mpz::from_u64(2)));
2432 }
2433 let mut a = Mpz::from_u64(2); let mut b = Mpz::from_u64(1); for _ in 2..=n {
2436 let c = a.try_add(&b)?;
2437 a = b;
2438 b = c;
2439 }
2440 Ok((b.clone(), a))
2441 }
2442
2443 fn to_twos_complement(&self, out: &mut [u64]) -> (usize, bool) {
2451 if self.sign == 0 {
2452 return (0, false);
2453 }
2454 let n = self.len + 1;
2455 if self.sign > 0 {
2456 out[..self.len].copy_from_slice(&self.mag[..self.len]);
2457 out[self.len] = 0;
2458 (n, false)
2459 } else {
2460 let mut carry = 1u128;
2461 for i in 0..self.len {
2462 let inv = (!self.mag[i]) as u128;
2463 let sum = inv + carry;
2464 out[i] = sum as u64;
2465 carry = sum >> 64;
2466 }
2467 if carry != 0 {
2468 out[self.len] = 0;
2469 } else {
2470 out[self.len] = !0u64;
2471 }
2472 (n, true)
2473 }
2474 }
2475
2476 fn from_twos_complement(limbs: &[u64], negative: bool) -> Mpz {
2478 if !negative {
2479 let mut r = Mpz::new();
2480 let n = limbs.len().min(MPZ_MAX_LIMBS);
2481 r.mag[..n].copy_from_slice(&limbs[..n]);
2482 r.len = n;
2483 r.sign = if n == 0 { 0 } else { 1 };
2484 r.trim();
2485 return r;
2486 }
2487 let mut r = Mpz::new();
2488 let n = limbs.len().min(MPZ_MAX_LIMBS);
2489 let mut carry = 1u128;
2490 for i in 0..n {
2491 let inv = (!limbs[i]) as u128;
2492 let sum = inv + carry;
2493 r.mag[i] = sum as u64;
2494 carry = sum >> 64;
2495 }
2496 if carry != 0 && n < MPZ_MAX_LIMBS {
2497 r.mag[n] = carry as u64;
2498 r.len = n + 1;
2499 } else {
2500 r.len = n;
2501 }
2502 r.sign = -1;
2503 r.trim();
2504 r
2505 }
2506
2507 fn bitwise_op<F>(&self, other: &Mpz, op: F) -> Result<Mpz, CapacityError>
2509 where
2510 F: Fn(u64, u64) -> u64,
2511 {
2512 let max_limbs = self.len.max(other.len) + 1;
2514 if max_limbs > MPZ_MAX_LIMBS {
2515 return Err(CapacityError);
2516 }
2517 let mut a_buf = [0u64; MPZ_MAX_LIMBS];
2518 let mut b_buf = [0u64; MPZ_MAX_LIMBS];
2519 let (a_len, a_neg) = self.to_twos_complement(&mut a_buf);
2520 let (b_len, b_neg) = other.to_twos_complement(&mut b_buf);
2521
2522 let work_len = max_limbs;
2526
2527 let mut result_limbs = [0u64; MPZ_MAX_LIMBS];
2528 let sign_a = if a_neg { !0u64 } else { 0 };
2529 let sign_b = if b_neg { !0u64 } else { 0 };
2530
2531 for i in 0..work_len {
2532 let va = if i < a_len { a_buf[i] } else { sign_a };
2533 let vb = if i < b_len { b_buf[i] } else { sign_b };
2534 result_limbs[i] = op(va, vb);
2535 }
2536
2537 let top_limb = result_limbs[work_len - 1];
2539 let negative = (top_limb >> 63) == 1;
2540
2541 if !negative {
2542 let mut rlen = work_len;
2544 while rlen > 0 && result_limbs[rlen - 1] == 0 {
2545 rlen -= 1;
2546 }
2547 let mut r = Mpz::new();
2548 r.mag[..rlen].copy_from_slice(&result_limbs[..rlen]);
2549 r.len = rlen;
2550 r.sign = if rlen == 0 { 0 } else { 1 };
2551 Ok(r)
2552 } else {
2553 let full_len = work_len;
2555 Ok(Self::from_twos_complement(&result_limbs[..full_len], true))
2556 }
2557 }
2558
2559 pub fn try_and(&self, other: &Mpz) -> Result<Mpz, CapacityError> {
2560 if self.len == 0 || other.len == 0 {
2562 return Ok(Mpz::new());
2563 }
2564 if core::ptr::eq(self, other) || self == other {
2565 return Ok(self.clone());
2566 }
2567 self.bitwise_op(other, |a, b| a & b)
2568 }
2569
2570 pub fn try_ior(&self, other: &Mpz) -> Result<Mpz, CapacityError> {
2571 if self.len == 0 {
2573 return Ok(other.clone());
2574 }
2575 if other.len == 0 {
2576 return Ok(self.clone());
2577 }
2578 if core::ptr::eq(self, other) || self == other {
2579 return Ok(self.clone());
2580 }
2581 self.bitwise_op(other, |a, b| a | b)
2582 }
2583
2584 pub fn try_xor(&self, other: &Mpz) -> Result<Mpz, CapacityError> {
2585 if self.len == 0 {
2587 return Ok(other.clone());
2588 }
2589 if other.len == 0 {
2590 return Ok(self.clone());
2591 }
2592 if core::ptr::eq(self, other) || self == other {
2593 return Ok(Mpz::new());
2594 }
2595 self.bitwise_op(other, |a, b| a ^ b)
2596 }
2597
2598 pub fn popcount(&self) -> Option<u32> {
2600 if self.sign < 0 {
2601 return None;
2602 }
2603 let mut count = 0u32;
2604 for i in 0..self.len {
2605 count += self.mag[i].count_ones();
2606 }
2607 Some(count)
2608 }
2609
2610 pub fn hamdist(&self, other: &Mpz) -> Option<u32> {
2612 self.try_xor(other).ok()?.popcount()
2613 }
2614
2615 pub fn scan0(&self, start: u32) -> u32 {
2617 let start_limb = (start / 64) as usize;
2618 let start_bit = start % 64;
2619 for i in start_limb..self.len {
2620 let mut w = self.mag[i];
2621 if i == start_limb && start_bit > 0 {
2622 w |= (1u64 << start_bit) - 1;
2623 }
2624 let zeros = (!w).trailing_zeros();
2625 if zeros < 64 {
2626 return (i * 64 + zeros as usize) as u32;
2627 }
2628 }
2629 (self.len * 64) as u32
2630 }
2631
2632 pub fn scan1(&self, start: u32) -> Option<u32> {
2634 let start_limb = (start / 64) as usize;
2635 let start_bit = start % 64;
2636 for i in start_limb..self.len {
2637 let mut w = self.mag[i];
2638 if i == start_limb {
2639 w >>= start_bit;
2640 w <<= start_bit;
2641 }
2642 if w != 0 {
2643 return Some((i * 64 + w.trailing_zeros() as usize) as u32);
2644 }
2645 }
2646 None
2647 }
2648
2649 pub fn tstbit(&self, bit: u32) -> bool {
2653 let limb = (bit / 64) as usize;
2654 let bit_idx = bit % 64;
2655 if limb >= self.len {
2656 return self.sign < 0;
2659 }
2660 (self.mag[limb] >> bit_idx) & 1 == 1
2661 }
2662
2663 pub fn try_setbit(&mut self, bit: u32) -> Result<(), CapacityError> {
2665 let limb = (bit / 64) as usize;
2666 let bit_idx = bit % 64;
2667 if limb >= MPZ_MAX_LIMBS {
2668 return Err(CapacityError);
2669 }
2670 if limb >= self.len {
2671 self.len = limb + 1;
2672 }
2673 self.mag[limb] |= 1u64 << bit_idx;
2674 if self.sign == 0 {
2675 self.sign = 1;
2676 }
2677 Ok(())
2678 }
2679
2680 pub fn clrbit(&mut self, bit: u32) {
2682 let limb = (bit / 64) as usize;
2683 let bit_idx = bit % 64;
2684 if limb >= self.len {
2685 return;
2686 }
2687 self.mag[limb] &= !(1u64 << bit_idx);
2688 self.trim();
2689 }
2690
2691 pub fn try_combit(&mut self, bit: u32) -> Result<(), CapacityError> {
2693 let limb = (bit / 64) as usize;
2694 let bit_idx = bit % 64;
2695 if limb >= self.len && limb >= MPZ_MAX_LIMBS {
2696 return Err(CapacityError);
2697 }
2698 if limb >= self.len {
2699 self.len = limb + 1;
2700 if self.sign == 0 {
2701 self.sign = 1;
2702 }
2703 }
2704 self.mag[limb] ^= 1u64 << bit_idx;
2705 self.trim();
2706 Ok(())
2707 }
2708
2709 pub fn from_decimal_str(s: &str) -> Result<Mpz, ParseError> {
2714 let s = s.trim();
2715 if s.is_empty() {
2716 return Err(ParseError::InvalidInput);
2717 }
2718 let (neg, digits) = match s.strip_prefix('-') {
2719 Some(d) => {
2720 if d.is_empty() {
2721 return Err(ParseError::InvalidInput);
2722 }
2723 (true, d)
2724 }
2725 None => match s.strip_prefix('+') {
2726 Some(d) => {
2727 if d.is_empty() {
2728 return Err(ParseError::InvalidInput);
2729 }
2730 (false, d)
2731 }
2732 None => (false, s),
2733 },
2734 };
2735 if !digits.bytes().all(|b| b.is_ascii_digit()) {
2736 return Err(ParseError::InvalidInput);
2737 }
2738 let bytes = digits.as_bytes();
2739 let mut r = Mpz::new();
2740 let mut i = 0;
2741 while i < bytes.len() {
2742 let end = (i + 18).min(bytes.len());
2743 let mut chunk: u64 = 0;
2744 for &b in &bytes[i..end] {
2745 chunk = chunk.wrapping_mul(10).wrapping_add((b - b'0') as u64);
2746 }
2747 let scale = 10u64.pow((end - i) as u32);
2748 r = r
2749 .try_mul_ui(scale)
2750 .map_err(|_| ParseError::CapacityOverflow)?;
2751 r = r
2752 .try_add_ui(chunk)
2753 .map_err(|_| ParseError::CapacityOverflow)?;
2754 i = end;
2755 }
2756 if neg && r.sign != 0 {
2757 r.sign = -1;
2758 }
2759 Ok(r)
2760 }
2761
2762 pub fn write_decimal_buf(&self, buf: &mut [u8]) -> usize {
2763 if self.sign == 0 {
2764 if !buf.is_empty() {
2765 buf[0] = b'0';
2766 return 1;
2767 }
2768 return 0;
2769 }
2770 let mut digits = [0u8; 160];
2771 let mut di = digits.len();
2772 let mut m = self.clone();
2773 loop {
2774 let mut qbuf = [0u64; MPZ_MAX_LIMBS];
2775 let (qlen, rem) =
2776 Self::mag_divmod_u64_len(&m.mag[..m.len], 1_000_000_000_000_000_000, &mut qbuf);
2777 let mut rem_d = rem;
2778 if qlen == 0 {
2779 if rem_d == 0 {
2780 di -= 1;
2781 digits[di] = b'0';
2782 } else {
2783 while rem_d != 0 {
2784 di -= 1;
2785 digits[di] = b'0' + (rem_d % 10) as u8;
2786 rem_d /= 10;
2787 }
2788 }
2789 break;
2790 } else {
2791 for _ in 0..18 {
2792 di -= 1;
2793 digits[di] = b'0' + (rem_d % 10) as u8;
2794 rem_d /= 10;
2795 }
2796 }
2797 m.mag[..qlen].copy_from_slice(&qbuf[..qlen]);
2798 m.len = qlen;
2799 }
2800 let mut pos = 0;
2801 if self.sign < 0 && !buf.is_empty() {
2802 buf[0] = b'-';
2803 pos = 1;
2804 }
2805 let src = &digits[di..];
2806 let avail = buf.len() - pos;
2807 let n = src.len().min(avail);
2808 buf[pos..pos + n].copy_from_slice(&src[..n]);
2809 pos + n
2810 }
2811
2812 pub fn getlimbn(&self, n: usize) -> Option<u64> {
2818 if n >= self.len {
2819 None
2820 } else {
2821 Some(self.mag[n])
2822 }
2823 }
2824
2825 pub fn cmp_d(&self, v: f64) -> Ordering {
2831 if v.is_nan() {
2832 return Ordering::Greater; }
2834 let other = match Mpz::from_d(v) {
2835 Ok(m) => m,
2836 Err(_) => {
2837 if v.is_infinite() {
2839 if v.is_sign_positive() {
2840 return Ordering::Less;
2841 } else {
2842 return Ordering::Greater;
2843 }
2844 }
2845 return self.cmp(&Mpz::new());
2846 }
2847 };
2848 self.cmp(&other)
2849 }
2850
2851 pub fn cmpabs_d(&self, v: f64) -> Ordering {
2853 if v.is_nan() {
2854 return Ordering::Greater;
2855 }
2856 let v_abs = v.abs();
2857 let other = match Mpz::from_d(v_abs) {
2858 Ok(m) => m,
2859 Err(_) => {
2860 if v.is_infinite() {
2861 return Ordering::Less;
2862 }
2863 return self.cmp(&Mpz::new());
2864 }
2865 };
2866 self.cmpabs(&other)
2867 }
2868
2869 pub fn try_import(
2882 count: usize,
2883 order: Endian,
2884 size: usize,
2885 endian: Endian,
2886 data: &[u8],
2887 ) -> Result<Mpz, CapacityError> {
2888 if count == 0 || size == 0 {
2889 return Ok(Mpz::new());
2890 }
2891 if data.len() < count * size {
2892 return Ok(Mpz::new());
2893 }
2894
2895 let max_limbs = (count * size).div_ceil(8);
2897 if max_limbs > MPZ_MAX_LIMBS {
2898 return Err(CapacityError);
2899 }
2900
2901 let mut limbs = [0u64; MPZ_MAX_LIMBS];
2903 let n_chunks = count;
2904 let chunk_size = size;
2905
2906 let read_chunk = |start: usize| -> u64 {
2908 let mut val = 0u64;
2909 let end = (start + chunk_size).min(data.len());
2910 match endian {
2911 Endian::Little | Endian::Native if native_is_little() => {
2912 for i in (start..end).rev() {
2913 val = (val << 8) | data[i] as u64;
2914 }
2915 }
2916 _ => {
2917 for i in start..end {
2919 val = (val << 8) | data[i] as u64;
2920 }
2921 }
2922 }
2923 val
2924 };
2925
2926 let mut limb_idx = 0;
2928 let mut bit_offset = 0;
2929
2930 match order {
2931 Endian::Little | Endian::Native if native_is_little() => {
2932 for ci in 0..n_chunks {
2934 let chunk_val = read_chunk(ci * chunk_size);
2935 limbs[limb_idx] |= chunk_val << bit_offset;
2936 bit_offset += chunk_size * 8;
2937 while bit_offset >= 64 {
2938 limb_idx += 1;
2939 bit_offset -= 64;
2940 if bit_offset > 0 {
2941 limbs[limb_idx] = chunk_val >> (chunk_size * 8 - bit_offset);
2942 }
2943 }
2944 }
2945 }
2946 _ => {
2947 for ci in (0..n_chunks).rev() {
2949 let chunk_val = read_chunk(ci * chunk_size);
2950 limbs[limb_idx] |= chunk_val << bit_offset;
2951 bit_offset += chunk_size * 8;
2952 while bit_offset >= 64 {
2953 limb_idx += 1;
2954 bit_offset -= 64;
2955 if bit_offset > 0 {
2956 limbs[limb_idx] = chunk_val >> (chunk_size * 8 - bit_offset);
2957 }
2958 }
2959 }
2960 }
2961 }
2962
2963 let mut r = Mpz::new();
2964 let _n_limbs = (count * size).div_ceil(8);
2965 let n_limbs_actual = if bit_offset > 0 {
2966 limb_idx + 1
2967 } else {
2968 limb_idx
2969 };
2970 let final_limbs = n_limbs_actual.min(MPZ_MAX_LIMBS);
2971 r.mag[..final_limbs].copy_from_slice(&limbs[..final_limbs]);
2972 r.len = final_limbs;
2973 r.sign = if r.len == 0 { 0 } else { 1 };
2974 r.trim();
2975 Ok(r)
2976 }
2977
2978 pub fn export_buf(
2987 &self,
2988 buf: &mut [u8],
2989 order: Endian,
2990 size: usize,
2991 endian: Endian,
2992 ) -> Option<usize> {
2993 if self.is_zero() || size == 0 {
2994 if !buf.is_empty() {
2995 buf[0] = 0;
2996 return Some(1);
2997 }
2998 return Some(0);
2999 }
3000
3001 let total_bits = self.sizeinbase2();
3003 let total_bytes = total_bits.div_ceil(8);
3004 let chunk_bytes = size;
3005 let n_chunks = total_bytes.div_ceil(chunk_bytes);
3006 let needed_bytes = n_chunks * chunk_bytes;
3007
3008 if buf.len() < needed_bytes {
3009 return None;
3010 }
3011
3012 for b in buf.iter_mut().take(needed_bytes) {
3014 *b = 0;
3015 }
3016
3017 let mut byte_pos = 0usize;
3019 for i in 0..self.len {
3020 let mut val = self.mag[i];
3021 for _ in 0..8 {
3022 if byte_pos < needed_bytes {
3023 buf[byte_pos] = (val & 0xFF) as u8;
3024 val >>= 8;
3025 byte_pos += 1;
3026 }
3027 }
3028 }
3029
3030 let is_native_little = native_is_little();
3035 let native_endian = if is_native_little {
3036 Endian::Little
3037 } else {
3038 Endian::Big
3039 };
3040
3041 if order == Endian::Little || (order == Endian::Native && native_endian == Endian::Little) {
3046 if (endian == Endian::Little
3047 || (endian == Endian::Native && native_endian == Endian::Little))
3048 && (size == 1 || size == 0)
3049 {
3050 return Some(needed_bytes);
3051 }
3052 }
3054
3055 let mut orig = [0u8; 8];
3058 let copy_len = needed_bytes.min(orig.len());
3059 orig[..copy_len].copy_from_slice(&buf[..copy_len]);
3060 let mut chunk_tmp = [0u8; 8];
3061 for ci in 0..n_chunks {
3062 let src_start = ci * chunk_bytes;
3064 let src_end = (src_start + chunk_bytes).min(needed_bytes);
3065 for j in src_start..src_end {
3066 let tmp_idx = j - src_start;
3067 chunk_tmp[tmp_idx] = orig[j];
3068 }
3069 for j in src_end - src_start..chunk_bytes {
3070 chunk_tmp[j] = 0;
3071 }
3072
3073 let chunk_val = match endian {
3075 Endian::Little | Endian::Native if is_native_little => {
3076 let mut v = 0u64;
3078 for j in 0..chunk_bytes {
3079 v |= (chunk_tmp[j] as u64) << (j * 8);
3080 }
3081 v
3082 }
3083 _ => {
3084 let mut v = 0u64;
3086 for j in 0..chunk_bytes {
3087 v = (v << 8) | chunk_tmp[j] as u64;
3088 }
3089 v
3090 }
3091 };
3092
3093 for j in 0..chunk_bytes {
3095 chunk_tmp[j] = ((chunk_val >> (j * 8)) & 0xFF) as u8;
3096 }
3097
3098 let dst_start = match order {
3100 Endian::Little | Endian::Native if is_native_little => ci * chunk_bytes,
3101 _ => (n_chunks - 1 - ci) * chunk_bytes,
3102 };
3103 for j in 0..chunk_bytes {
3104 if dst_start + j < buf.len() {
3105 buf[dst_start + j] = chunk_tmp[j];
3106 }
3107 }
3108 }
3109
3110 Some(needed_bytes)
3111 }
3112
3113 pub fn try_probab_prime_p(&self, reps: u32) -> Result<i32, CapacityError> {
3126 if self.sign < 0 {
3127 return Ok(0);
3128 }
3129 if self.len == 0 {
3130 return Ok(0);
3131 }
3132
3133 if self.len == 1 {
3135 let v = self.mag[0];
3136 if v < 2 {
3137 return Ok(0);
3138 }
3139 for &p in SMALL_PRIMES.iter() {
3141 if p * p > v {
3142 break;
3143 }
3144 if v.is_multiple_of(p) {
3145 return Ok(if v == p { 2 } else { 0 });
3146 }
3147 }
3148 if v <= SMALL_PRIMES[SMALL_PRIMES.len() - 1].pow(2) {
3149 return Ok(2); }
3151 }
3152
3153 for &p in SMALL_PRIMES.iter() {
3155 if self.tdiv_ui(p) == 0 {
3156 let _p_mpz = Mpz::from_u64(p);
3158 if self.len == 1 && self.mag[0] == p {
3159 return Ok(2);
3160 }
3161 return Ok(0);
3162 }
3163 }
3164
3165 let one = Mpz::from_u64(1);
3167 let nm1 = self.try_sub(&one)?;
3168 let s = nm1.mag[0].trailing_zeros(); let d = nm1.fdiv_q_2exp(s);
3170
3171 let reps = reps.min(64);
3172 for i in 0..reps {
3173 let a = Mpz::from_u64(SMALL_PRIMES[i as usize]);
3174 let mut x = a.try_powm(&d, self)?;
3176 if x.len == 0 || (x.len == 1 && x.mag[0] == 1) || x == nm1 {
3177 continue;
3178 }
3179 let mut composite = true;
3180 for _ in 0..s {
3181 x = x.try_powm(&Mpz::from_u64(2), self)?;
3182 if x == nm1 {
3183 composite = false;
3184 break;
3185 }
3186 if x.len == 1 && x.mag[0] == 1 {
3187 break;
3188 }
3189 }
3190 if composite {
3191 return Ok(0);
3192 }
3193 }
3194
3195 Ok(1)
3196 }
3197
3198 #[cfg(feature = "const_time")]
3203 pub fn ct_add(&self, other: &Mpz) -> Result<Mpz, CapacityError> {
3207 let mut result = Mpz::new();
3209 let mut carry = 0u128;
3210 for i in 0..MPZ_MAX_LIMBS {
3211 let va = if i < self.len { self.mag[i] as u128 } else { 0 };
3212 let vb = if i < other.len {
3213 other.mag[i] as u128
3214 } else {
3215 0
3216 };
3217 let s = va + vb + carry;
3218 result.mag[i] = s as u64;
3219 carry = s >> 64;
3220 }
3221 if carry != 0 {
3222 return Err(CapacityError);
3223 }
3224
3225 let mut result_len = MPZ_MAX_LIMBS;
3229 while result_len > 0 && result.mag[result_len - 1] == 0 {
3230 result_len -= 1;
3231 }
3232 result.len = result_len;
3233
3234 if self.sign == 0 {
3235 result.sign = other.sign;
3236 } else if other.sign == 0 {
3237 result.sign = self.sign;
3238 } else if self.sign == other.sign {
3239 result.sign = self.sign;
3240 } else {
3241 let mut neg_other_mag = [0u64; MPZ_MAX_LIMBS];
3245 for i in 0..MPZ_MAX_LIMBS {
3246 neg_other_mag[i] = other.mag[i];
3247 }
3248 let mut neg_other_len = other.len;
3249 let self_gt = Self::ct_cmp_mag(&self.mag, self.len, &neg_other_mag, neg_other_len);
3251 let mut borrow: i128 = 0;
3255 let (src_a, src_b, out_sign) = if self_gt == Ordering::Greater {
3256 (&self.mag, &neg_other_mag, self.sign)
3257 } else if self_gt == Ordering::Less {
3258 (&neg_other_mag, &self.mag, other.sign)
3259 } else {
3260 return Ok(Mpz::new());
3261 };
3262 let a_len = if self_gt == Ordering::Greater {
3263 self.len
3264 } else {
3265 other.len
3266 }
3267 .max(if self_gt == Ordering::Greater {
3268 other.len
3269 } else {
3270 self.len
3271 });
3272 for i in 0..a_len.max(1) {
3273 let ai = if i < src_a.len() { src_a[i] as i128 } else { 0 };
3274 let bi = if i < src_b.len() { src_b[i] as i128 } else { 0 };
3275 let mut cur = ai - bi - borrow;
3276 if cur < 0 {
3277 cur += 1i128 << 64;
3278 borrow = 1;
3279 } else {
3280 borrow = 0;
3281 }
3282 result.mag[i] = cur as u64;
3283 }
3284 let mut rl = a_len.max(1);
3285 while rl > 0 && result.mag[rl - 1] == 0 {
3286 rl -= 1;
3287 }
3288 result.len = rl;
3289 result.sign = if rl == 0 { 0 } else { out_sign };
3290 }
3291
3292 result.trim();
3293 Ok(result)
3294 }
3295
3296 #[cfg(feature = "const_time")]
3297 pub fn ct_sub(&self, other: &Mpz) -> Result<Mpz, CapacityError> {
3299 let neg = other.neg_to();
3300 self.ct_add(&neg)
3301 }
3302
3303 #[cfg(feature = "const_time")]
3304 pub fn ct_cmp_mag(
3308 a: &[u64; MPZ_MAX_LIMBS],
3309 a_len: usize,
3310 b: &[u64; MPZ_MAX_LIMBS],
3311 b_len: usize,
3312 ) -> Ordering {
3313 let mut gt = 0u64;
3316 let mut lt = 0u64;
3317 for i in (0..MPZ_MAX_LIMBS).rev() {
3318 let va = a[i];
3319 let vb = b[i];
3320 let diff = (va as i128) - (vb as i128);
3321 let is_gt = ((diff >> 127) as u64).wrapping_neg(); let is_lt = (((-diff) >> 127) as u64).wrapping_neg();
3326 let gt_bit = if diff > 0 { 1u64 } else { 0u64 };
3328 let lt_bit = if diff < 0 { 1u64 } else { 0u64 };
3329 }
3335 let mut result = 0i8; for i in (0..MPZ_MAX_LIMBS).rev() {
3338 let va = a[i];
3339 let vb = b[i];
3340 let gt_mask = (va as i128 > vb as i128) as u64;
3342 let lt_mask = ((va as i128) < (vb as i128)) as u64;
3343 let eq_mask = (va == vb) as u64;
3344 let decisive = gt_mask | lt_mask;
3347 let new_val = (gt_mask as i8) - (lt_mask as i8); let mask = 0u64.wrapping_sub(decisive);
3353 result ^= ((result ^ new_val) as u64 & mask) as i8;
3354 }
3355 match result {
3356 1 => Ordering::Greater,
3357 -1 => Ordering::Less,
3358 _ => Ordering::Equal,
3359 }
3360 }
3361
3362 #[cfg(feature = "const_time")]
3363 pub fn ct_cmp(&self, other: &Mpz) -> Ordering {
3365 let sign_diff = (self.sign != other.sign) as u64;
3367 let self_neg = (self.sign < 0) as u64;
3368 let other_neg = (other.sign < 0) as u64;
3369
3370 let sign_result: i8 = if self.sign > other.sign {
3374 1
3375 } else if self.sign < other.sign {
3376 -1
3377 } else {
3378 0
3379 };
3380
3381 let mag_cmp = Self::ct_cmp_mag(&self.mag, self.len, &other.mag, other.len);
3383 let mag_result: i8 = match mag_cmp {
3384 Ordering::Greater => 1,
3385 Ordering::Less => -1,
3386 Ordering::Equal => 0,
3387 };
3388
3389 let both_neg = (self.sign < 0 && other.sign < 0) as u64;
3392 let neg_mask = 0u64.wrapping_sub(both_neg);
3393 let adjusted_mag = mag_result ^ ((mag_result as u64 & 1) & neg_mask) as i8;
3395 let blend = (sign_diff != 0) as u64;
3405 let mut final_val = if blend != 0 { sign_result } else { mag_result };
3406 if blend == 0 && both_neg != 0 {
3407 final_val = match final_val {
3408 1 => -1,
3409 -1 => 1,
3410 _ => 0,
3411 };
3412 }
3413 match final_val {
3414 1 => Ordering::Greater,
3415 -1 => Ordering::Less,
3416 _ => Ordering::Equal,
3417 }
3418 }
3419
3420 #[cfg(feature = "const_time")]
3421 pub fn ct_select(&self, other: &Mpz, bit: u64) -> Mpz {
3424 let mask = 0u64.wrapping_sub(bit & 1);
3426 let mut result = Mpz::new();
3427 for i in 0..MPZ_MAX_LIMBS {
3428 result.mag[i] = (self.mag[i] & !mask) | (other.mag[i] & mask);
3429 }
3430 result.len = if (self.len & !mask) | (other.len & mask) != 0 {
3431 let blended_len = (self.len & !mask as usize) | (other.len & mask as usize);
3432 let mut l = MPZ_MAX_LIMBS;
3434 while l > 0 && result.mag[l - 1] == 0 {
3435 l -= 1;
3436 }
3437 l
3438 } else {
3439 0
3440 };
3441 result.sign = ((self.sign as i8 & !(mask as i8)) | (other.sign as i8 & mask as i8)) as i8;
3442 result.trim();
3443 result
3444 }
3445
3446 pub fn capability_map() -> &'static [(i32, &'static str, &'static str)] {
3458 CAPABILITY_TABLE
3459 }
3460
3461 #[cfg(feature = "const_time")]
3471 pub fn ct_add(&self, other: &Mpz) -> Result<Mpz, CapacityError> {
3472 let mut result = Mpz::new();
3475 let same_sign = ((self.sign as i8) ^ (other.sign as i8)).wrapping_add(1) as u64;
3478 let same_sign = (same_sign & 1).wrapping_sub(1); let mut add_mag = [0u64; MPZ_MAX_LIMBS];
3482 let mut carry = 0u128;
3483 for i in 0..MPZ_MAX_LIMBS {
3484 let va = if i < self.len { self.mag[i] as u128 } else { 0 };
3485 let vb = if i < other.len {
3486 other.mag[i] as u128
3487 } else {
3488 0
3489 };
3490 let s = va + vb + carry;
3491 add_mag[i] = s as u64;
3492 carry = s >> 64;
3493 }
3494 let add_overflow = carry != 0;
3495
3496 let mut a_bigger: i8 = 0;
3499 for i in (0..MPZ_MAX_LIMBS).rev() {
3500 let va = if i < self.len { self.mag[i] } else { 0 };
3501 let vb = if i < other.len { other.mag[i] } else { 0 };
3502 let mask: u8 = ((a_bigger as u8) ^ 1u8.wrapping_sub(1)) & 1;
3503 let not_yet_decided = ((a_bigger as u8).wrapping_sub(1) >> 7) & 1;
3505 let gt = (vb < va) as u8 & not_yet_decided;
3506 let lt = (va < vb) as u8 & not_yet_decided;
3507 a_bigger = (a_bigger as u8 | gt | lt.wrapping_neg()) as i8;
3508 }
3509 let use_self_a = ((a_bigger as u8) ^ 1) & 1; let mask_a = (use_self_a).wrapping_sub(1) as u64; let mask_b = (!use_self_a).wrapping_sub(1) as u64; let mut sub_mag = [0u64; MPZ_MAX_LIMBS];
3514 let mut borrow: i128 = 0;
3515 for i in 0..MPZ_MAX_LIMBS {
3516 let va = if i < self.len { self.mag[i] as i128 } else { 0 };
3517 let vb = if i < other.len {
3518 other.mag[i] as i128
3519 } else {
3520 0
3521 };
3522 let minuend = va.wrapping_add(((vb - va) as i128) & (mask_b as i128));
3524 let subtrahend = vb.wrapping_add(((va - vb) as i128) & (mask_a as i128));
3525 let mut cur = minuend - subtrahend - borrow;
3526 if cur < 0 {
3527 cur += 1i128 << 64;
3528 borrow = 1;
3529 } else {
3530 borrow = 0;
3531 }
3532 sub_mag[i] = cur as u64;
3533 }
3534
3535 let use_add = same_sign;
3537 let use_sub = same_sign ^ !0u64;
3538
3539 let mut can_overflow = add_overflow as u64;
3540 let mut sign = 0i8;
3541 for i in 0..MPZ_MAX_LIMBS {
3542 let add_val = add_mag[i] & use_add;
3543 let sub_val = sub_mag[i] & use_sub;
3544 result.mag[i] = add_val | sub_val;
3545 }
3546 let self_s = self.sign as i64;
3550 let other_s = other.sign as i64;
3551 let use_self_sign = use_self_a as i64;
3552 let use_other_sign = (!use_self_a) as i64;
3553 let sel_sign = self_s
3554 .wrapping_mul(use_self_sign)
3555 .wrapping_add(other_s.wrapping_mul(use_other_sign));
3556 let same_sign_path = same_sign as i64 & self_s;
3557 sign = (same_sign_path | (sel_sign & (use_sub as i64))) as i8;
3558 result.sign = sign;
3559 let mut new_len = 0usize;
3561 for i in (0..MPZ_MAX_LIMBS).rev() {
3562 let is_zero = (result.mag[i] == 0) as usize;
3563 let not_is_zero = 1usize ^ is_zero;
3564 let already_set = (new_len != 0) as usize;
3566 new_len =
3567 new_len | ((i + 1) & (not_is_zero.wrapping_sub(1)) & !already_set.wrapping_sub(1));
3568 }
3569 result.len = new_len;
3570 if result.len == 0 {
3571 result.sign = 0;
3572 }
3573
3574 if can_overflow != 0 {
3575 Err(CapacityError)
3576 } else {
3577 Ok(result)
3578 }
3579 }
3580
3581 #[cfg(feature = "const_time")]
3583 pub fn ct_sub(&self, other: &Mpz) -> Result<Mpz, CapacityError> {
3584 let mut neg_other = other.clone();
3585 neg_other.sign = -neg_other.sign;
3586 self.ct_add(&neg_other)
3587 }
3588
3589 #[cfg(feature = "const_time")]
3592 pub fn ct_cmp(&self, other: &Mpz) -> Ordering {
3593 let self_s = self.sign as i64;
3595 let other_s = other.sign as i64;
3596 let sign_diff = self_s - other_s;
3597 let sign_mask = ((sign_diff as u64).wrapping_sub(1)) >> 63;
3599 let sign_gt = (sign_diff > 0) as u64;
3600 let sign_lt = (sign_diff < 0) as u64;
3601
3602 let mut mag_gt = 0u64;
3604 let mut mag_lt = 0u64;
3605 for i in (0..MPZ_MAX_LIMBS).rev() {
3606 let va = if i < self.len { self.mag[i] } else { 0 };
3607 let vb = if i < other.len { other.mag[i] } else { 0 };
3608 let decided = (mag_gt | mag_lt).wrapping_sub(1) >> 63;
3610 let not_decided = decided ^ 1;
3611 mag_gt |= ((va > vb) as u64) & not_decided;
3612 mag_lt |= ((va < vb) as u64) & not_decided;
3613 }
3614 let both_neg = (self_s >> 63) & (other_s >> 63) & 1;
3617 let mag_result_gt = mag_gt ^ (both_neg); let mag_result_lt = mag_lt ^ (both_neg);
3619
3620 let final_gt = (sign_gt & sign_mask) | (mag_result_gt & (sign_mask ^ 1));
3621 let final_lt = (sign_lt & sign_mask) | (mag_result_lt & (sign_mask ^ 1));
3622
3623 let gt_bit = (final_gt).wrapping_sub(1) >> 63;
3624 let lt_bit = (final_lt).wrapping_sub(1) >> 63;
3625 let eq_bit = ((gt_bit | lt_bit) ^ 1) & 1;
3626
3627 let ord_val = gt_bit as i8 - lt_bit as i8;
3629 match ord_val {
3630 1 => Ordering::Greater,
3631 -1 => Ordering::Less,
3632 _ => Ordering::Equal,
3633 }
3634 }
3635
3636 #[cfg(feature = "const_time")]
3639 pub fn ct_select(&self, other: &Mpz, bit: u64) -> Mpz {
3640 let mask = (bit.wrapping_sub(1)) >> 63; let not_mask = !mask;
3642 let mut result = Mpz::new();
3643 for i in 0..MPZ_MAX_LIMBS {
3644 result.mag[i] = (self.mag[i] & not_mask) | (other.mag[i] & mask);
3645 }
3646 let self_s = self.sign as i64;
3648 let other_s = other.sign as i64;
3649 let sel_s = (self_s & not_mask as i64) | (other_s & mask as i64);
3650 let self_len = self.len;
3651 let other_len = other.len;
3652 result.len = (self_len & (not_mask as usize)) | (other_len & (mask as usize));
3653 result.sign = sel_s as i8;
3654 result
3655 }
3656} #[doc(hidden)]
3663pub static CAPABILITY_TABLE: &[(i32, &str, &str)] = &[
3664 (1, "mpz_init", "yes — Mpz::new()"),
3668 (0, "mpz_inits", "no (varargs — not expressible in Rust)"),
3669 (
3670 -1,
3671 "mpz_init2",
3672 "no (fixed array — no allocation hint needed)",
3673 ),
3674 (0, "mpz_clear", "no (Rust Drop handles this)"),
3675 (0, "mpz_clears", "no (varargs)"),
3676 (-1, "mpz_realloc2", "no (fixed array — no reallocation)"),
3677 (1, "mpz_set", "yes — Mpz::set()"),
3681 (1, "mpz_set_ui", "yes — Mpz::set_ui()"),
3682 (1, "mpz_set_si", "yes — Mpz::set_si()"),
3683 (1, "mpz_set_d", "yes — Mpz::from_d()"),
3684 (-1, "mpz_set_q", "no (mpq type does not exist)"),
3685 (-1, "mpz_set_f", "no (mpf type does not exist)"),
3686 (
3687 1,
3688 "mpz_set_str",
3689 "partial — base 10 only via from_decimal_str",
3690 ),
3691 (1, "mpz_swap", "yes — Mpz::swap()"),
3692 (1, "mpz_init_set", "yes — Clone::clone()"),
3696 (1, "mpz_init_set_ui", "yes — Mpz::from_u64()"),
3697 (1, "mpz_init_set_si", "yes — Mpz::from_i64()"),
3698 (1, "mpz_init_set_d", "yes — Mpz::from_d()"),
3699 (
3700 1,
3701 "mpz_init_set_str",
3702 "partial — base 10 only via from_decimal_str",
3703 ),
3704 (1, "mpz_get_ui", "yes — Mpz::get_ui()"),
3708 (1, "mpz_get_si", "yes — Mpz::get_si()"),
3709 (1, "mpz_get_d", "yes — Mpz::get_d()"),
3710 (1, "mpz_get_d_2exp", "yes — Mpz::get_d_2exp()"),
3711 (
3712 1,
3713 "mpz_get_str",
3714 "partial — base 10 only via write_decimal_buf",
3715 ),
3716 (1, "mpz_add", "yes — Mpz::try_add()"),
3720 (1, "mpz_add_ui", "yes — Mpz::try_add_ui()"),
3721 (1, "mpz_sub", "yes — Mpz::try_sub()"),
3722 (1, "mpz_sub_ui", "yes — Mpz::try_sub_ui()"),
3723 (1, "mpz_ui_sub", "yes — Mpz::try_ui_sub()"),
3724 (1, "mpz_mul", "yes — Mpz::try_mul()"),
3725 (1, "mpz_mul_si", "yes — Mpz::try_mul_si()"),
3726 (1, "mpz_mul_ui", "yes — Mpz::try_mul_ui()"),
3727 (1, "mpz_addmul", "yes — Mpz::try_addmul()"),
3728 (1, "mpz_addmul_ui", "yes — Mpz::try_addmul_ui()"),
3729 (1, "mpz_submul", "yes — Mpz::try_submul()"),
3730 (1, "mpz_submul_ui", "yes — Mpz::try_submul_ui()"),
3731 (1, "mpz_mul_2exp", "yes — Mpz::try_mul_2exp()"),
3732 (1, "mpz_neg", "yes — Mpz::neg() / neg_to()"),
3733 (1, "mpz_abs", "yes — Mpz::abs() / abs_to()"),
3734 (1, "mpz_tdiv_q", "yes — Mpz::tdiv_q()"),
3738 (1, "mpz_tdiv_r", "yes — Mpz::tdiv_r()"),
3739 (1, "mpz_tdiv_qr", "yes — Mpz::tdiv_qr()"),
3740 (1, "mpz_tdiv_q_ui", "yes — Mpz::tdiv_q_ui()"),
3741 (1, "mpz_tdiv_r_ui", "yes — Mpz::tdiv_r_ui()"),
3742 (1, "mpz_tdiv_qr_ui", "yes — Mpz::try_tdiv_qr_ui()"),
3743 (1, "mpz_tdiv_ui", "yes — Mpz::tdiv_ui()"),
3744 (1, "mpz_tdiv_q_2exp", "yes — Mpz::tdiv_q_2exp()"),
3745 (1, "mpz_tdiv_r_2exp", "yes — Mpz::tdiv_r_2exp()"),
3746 (1, "mpz_fdiv_q", "yes — Mpz::try_fdiv_q()"),
3750 (1, "mpz_fdiv_r", "yes — Mpz::try_fdiv_r()"),
3751 (1, "mpz_fdiv_qr", "yes — Mpz::try_fdiv_qr()"),
3752 (1, "mpz_fdiv_q_ui", "yes — Mpz::try_fdiv_q_ui()"),
3753 (1, "mpz_fdiv_r_ui", "yes — Mpz::try_fdiv_r_ui()"),
3754 (1, "mpz_fdiv_qr_ui", "yes — Mpz::try_fdiv_qr_ui()"),
3755 (1, "mpz_fdiv_ui", "yes — Mpz::fdiv_ui()"),
3756 (1, "mpz_fdiv_q_2exp", "yes — Mpz::fdiv_q_2exp()"),
3757 (1, "mpz_fdiv_r_2exp", "yes — Mpz::fdiv_r_2exp()"),
3758 (1, "mpz_cdiv_q", "yes — Mpz::try_cdiv_q()"),
3762 (1, "mpz_cdiv_r", "yes — Mpz::try_cdiv_r()"),
3763 (1, "mpz_cdiv_qr", "yes — Mpz::try_cdiv_qr()"),
3764 (1, "mpz_cdiv_q_ui", "yes — Mpz::try_cdiv_q_ui()"),
3765 (1, "mpz_cdiv_r_ui", "yes — Mpz::try_cdiv_r_ui()"),
3766 (1, "mpz_cdiv_qr_ui", "yes — Mpz::try_cdiv_qr_ui()"),
3767 (1, "mpz_cdiv_ui", "yes — Mpz::cdiv_ui()"),
3768 (1, "mpz_cdiv_q_2exp", "yes — Mpz::cdiv_q_2exp()"),
3769 (1, "mpz_cdiv_r_2exp", "yes — Mpz::cdiv_r_2exp()"),
3770 (1, "mpz_mod", "yes — Mpz::try_mod()"),
3774 (1, "mpz_mod_ui", "yes — Mpz::mod_ui()"),
3775 (1, "mpz_divexact", "yes — Mpz::try_divexact()"),
3779 (1, "mpz_divexact_ui", "yes — Mpz::try_divexact_ui()"),
3780 (1, "mpz_divisible_p", "yes — Mpz::divisible_p()"),
3784 (1, "mpz_divisible_ui_p", "yes — Mpz::divisible_ui()"),
3785 (1, "mpz_divisible_2exp_p", "yes — Mpz::divisible_2exp_p()"),
3786 (1, "mpz_congruent_p", "yes — Mpz::congruent_p()"),
3787 (1, "mpz_congruent_ui_p", "yes — Mpz::congruent_ui_p()"),
3788 (1, "mpz_congruent_2exp_p", "yes — Mpz::congruent_2exp_p()"),
3789 (1, "mpz_powm", "yes — Mpz::try_powm()"),
3793 (1, "mpz_powm_ui", "yes — Mpz::try_powm_ui()"),
3794 (
3795 -1,
3796 "mpz_powm_sec",
3797 "no (requires constant-time impl — see const_time feature)",
3798 ),
3799 (1, "mpz_pow_ui", "yes — Mpz::try_pow_ui()"),
3800 (1, "mpz_ui_pow_ui", "yes — Mpz::try_ui_pow_ui()"),
3801 (1, "mpz_root", "yes — Mpz::try_root()"),
3805 (1, "mpz_rootrem", "yes — Mpz::try_rootrem()"),
3806 (1, "mpz_sqrt", "yes — Mpz::isqrt()"),
3807 (1, "mpz_sqrtrem", "yes — Mpz::try_sqrtrem()"),
3808 (1, "mpz_perfect_power_p", "yes — Mpz::perfect_power_p()"),
3809 (1, "mpz_perfect_square_p", "yes — Mpz::perfect_square_p()"),
3810 (1, "mpz_probab_prime_p", "yes — Mpz::try_probab_prime_p()"),
3814 (-1, "mpz_nextprime", "no (requires alloc for sieve)"),
3815 (-1, "mpz_prevprime", "no (requires alloc for sieve)"),
3816 (1, "mpz_gcd", "yes — Mpz::try_gcd()"),
3817 (1, "mpz_gcd_ui", "yes — Mpz::gcd_ui()"),
3818 (1, "mpz_gcdext", "yes — Mpz::try_gcdext()"),
3819 (1, "mpz_lcm", "yes — Mpz::try_lcm()"),
3820 (1, "mpz_lcm_ui", "yes — Mpz::try_lcm_ui()"),
3821 (1, "mpz_invert", "yes — Mpz::try_invert()"),
3822 (1, "mpz_jacobi", "yes — Mpz::jacobi()"),
3823 (1, "mpz_legendre", "yes — Mpz::try_legendre()"),
3824 (1, "mpz_kronecker", "yes — Mpz::try_kronecker()"),
3825 (1, "mpz_kronecker_si", "yes — Mpz::try_kronecker_si()"),
3826 (1, "mpz_kronecker_ui", "yes — Mpz::try_kronecker_ui()"),
3827 (1, "mpz_si_kronecker", "yes — Mpz::try_si_kronecker()"),
3828 (1, "mpz_ui_kronecker", "yes — Mpz::try_ui_kronecker()"),
3829 (1, "mpz_remove", "yes — Mpz::try_remove()"),
3830 (1, "mpz_fac_ui", "yes — Mpz::try_fac_ui()"),
3831 (1, "mpz_2fac_ui", "yes — Mpz::try_2fac_ui()"),
3832 (-1, "mpz_mfac_uiui", "no (multi-factorial not implemented)"),
3833 (1, "mpz_primorial_ui", "yes — Mpz::try_primorial_ui()"),
3834 (1, "mpz_bin_ui", "yes — Mpz::try_bin_ui()"),
3835 (1, "mpz_bin_uiui", "yes — Mpz::try_bin_uiui()"),
3836 (1, "mpz_fib_ui", "yes — Mpz::try_fib_ui()"),
3837 (1, "mpz_fib2_ui", "yes — Mpz::try_fib2_ui()"),
3838 (1, "mpz_lucnum_ui", "yes — Mpz::try_lucnum_ui()"),
3839 (1, "mpz_lucnum2_ui", "yes — Mpz::try_lucnum2_ui()"),
3840 (1, "mpz_cmp", "yes — Mpz::cmp()"),
3844 (1, "mpz_cmp_d", "yes — Mpz::cmp_d()"),
3845 (1, "mpz_cmp_si", "yes — Mpz::cmp_si()"),
3846 (1, "mpz_cmp_ui", "yes — Mpz::cmp_ui()"),
3847 (1, "mpz_cmpabs", "yes — Mpz::cmpabs()"),
3848 (1, "mpz_cmpabs_d", "yes — Mpz::cmpabs_d()"),
3849 (1, "mpz_cmpabs_ui", "yes — Mpz::cmpabs_ui()"),
3850 (1, "mpz_sgn", "yes — Mpz::sgn()"),
3851 (1, "mpz_and", "yes — Mpz::try_and()"),
3855 (1, "mpz_ior", "yes — Mpz::try_ior()"),
3856 (1, "mpz_xor", "yes — Mpz::try_xor()"),
3857 (1, "mpz_com", "yes — Mpz::com()"),
3858 (1, "mpz_popcount", "yes — Mpz::popcount()"),
3859 (1, "mpz_hamdist", "yes — Mpz::hamdist()"),
3860 (1, "mpz_scan0", "yes — Mpz::scan0()"),
3861 (1, "mpz_scan1", "yes — Mpz::scan1()"),
3862 (1, "mpz_setbit", "yes — Mpz::try_setbit()"),
3863 (1, "mpz_clrbit", "yes — Mpz::clrbit()"),
3864 (1, "mpz_combit", "yes — Mpz::try_combit()"),
3865 (1, "mpz_tstbit", "yes — Mpz::tstbit()"),
3866 (-1, "mpz_out_str", "no (requires std — file I/O)"),
3870 (-1, "mpz_inp_str", "no (requires std — file I/O)"),
3871 (-1, "mpz_out_raw", "no (requires std — file I/O)"),
3872 (-1, "mpz_inp_raw", "no (requires std — file I/O)"),
3873 (-1, "mpz_urandomb", "no (requires external RNG)"),
3877 (-1, "mpz_urandomm", "no (requires external RNG)"),
3878 (-1, "mpz_rrandomb", "no (requires external RNG)"),
3879 (-1, "mpz_random", "no (obsolete — requires RNG)"),
3880 (-1, "mpz_random2", "no (obsolete — requires RNG)"),
3881 (1, "mpz_import", "yes — Mpz::try_import()"),
3885 (1, "mpz_export", "yes — Mpz::export_buf()"),
3886 (1, "mpz_fits_ulong_p", "yes — Mpz::fits_ulong()"),
3890 (1, "mpz_fits_slong_p", "yes — Mpz::fits_slong()"),
3891 (1, "mpz_fits_uint_p", "yes — Mpz::fits_uint()"),
3892 (1, "mpz_fits_sint_p", "yes — Mpz::fits_sint()"),
3893 (1, "mpz_fits_ushort_p", "yes — Mpz::fits_ushort()"),
3894 (1, "mpz_fits_sshort_p", "yes — Mpz::fits_sshort()"),
3895 (1, "mpz_odd_p", "yes — Mpz::odd_p()"),
3896 (1, "mpz_even_p", "yes — Mpz::even_p()"),
3897 (1, "mpz_sizeinbase", "partial — Mpz::try_sizeinbase()"),
3898 (1, "mpz_size", "yes — Mpz::size()"),
3902 (1, "mpz_getlimbn", "yes — Mpz::getlimbn()"),
3903 (-1, "mpz_limbs_read", "no (requires unsafe pointer access)"),
3904 (-1, "mpz_limbs_write", "no (requires unsafe pointer access)"),
3905 (
3906 -1,
3907 "mpz_limbs_modify",
3908 "no (requires unsafe pointer access)",
3909 ),
3910 (
3911 -1,
3912 "mpz_limbs_finish",
3913 "no (requires unsafe pointer access)",
3914 ),
3915 (-1, "mpz_roinit_n", "no (requires unsafe pointer tricks)"),
3916 (0, "MPZ_ROINIT_N", "no (C macro — not applicable)"),
3917 (0, "_mpz_realloc", "no (internal GMP function)"),
3918];
3919
3920#[inline(always)]
3921fn umul(a: u64, b: u64) -> (u64, u64) {
3922 let prod = a as u128 * b as u128;
3923 (prod as u64, (prod >> 64) as u64)
3924}
3925
3926#[cfg(test)]
3931mod tests {
3932 use super::*;
3933 extern crate alloc;
3934 use alloc::string::String;
3935
3936 fn s(m: &Mpz) -> String {
3937 let mut buf = [0u8; 192];
3938 let len = m.write_decimal_buf(&mut buf);
3939 core::str::from_utf8(&buf[..len]).unwrap().into()
3940 }
3941
3942 #[test]
3945 fn basic_arith() {
3946 let a = Mpz::from_decimal_str("123456789012345678901234567890").unwrap();
3947 let b = Mpz::from_decimal_str("987654321098765432109876543210").unwrap();
3948 assert_eq!(
3949 s(&a.try_add(&b).unwrap()),
3950 "1111111110111111111011111111100"
3951 );
3952 assert_eq!(s(&b.try_sub(&a).unwrap()), "864197532086419753208641975320");
3953 assert_eq!(
3954 s(&a.try_mul(&b).unwrap()),
3955 "121932631137021795226185032733622923332237463801111263526900"
3956 );
3957 assert_eq!(a.cmp(&b), Ordering::Less);
3958 assert_eq!(a.cmpabs(&b), Ordering::Less);
3959 }
3960
3961 #[test]
3962 fn signs_and_zero() {
3963 let a = Mpz::from_i64(-5);
3964 let b = Mpz::from_i64(5);
3965 assert_eq!(a.try_add(&b).unwrap(), Mpz::new());
3966 assert_eq!(a.sgn(), -1);
3967 assert_eq!(s(&a.try_mul(&b).unwrap()), "-25");
3968 assert_eq!(a.get_ui(), 5);
3969 assert_eq!(a.get_si(), -5);
3970 }
3971
3972 #[test]
3973 fn div_trunc() {
3974 let a = Mpz::from_decimal_str("-1000000000000000000000007").unwrap();
3975 let d = Mpz::from_u64(1000);
3976 let (q, r) = a.tdiv_qr(&d);
3977 assert_eq!(s(&q), "-1000000000000000000000");
3978 assert_eq!(s(&r), "-7");
3979 assert_eq!(a.tdiv_ui(1000), 7);
3980 }
3981
3982 #[test]
3983 fn shifts_and_remove() {
3984 let mut x = Mpz::from_decimal_str("123000").unwrap();
3985 assert_eq!(x.remove_pow10(), 3);
3986 assert_eq!(s(&x), "123");
3987 let y = Mpz::from_u64(1).try_mul_2exp(100).unwrap();
3988 assert_eq!(s(&y), "1267650600228229401496703205376");
3989 assert_eq!(y.fdiv_q_2exp(100), Mpz::from_u64(1));
3990 assert_eq!(Mpz::from_u64(0b1011).fdiv_r_2exp(2), Mpz::from_u64(0b11));
3991 }
3992
3993 #[test]
3994 fn zero_ops() {
3995 let z = Mpz::new();
3996 assert_eq!(s(&z), "0");
3997 assert_eq!(z.sgn(), 0);
3998 assert_eq!(z.size(), 0);
3999 assert!(z.fits_ulong());
4000 assert_eq!(z.get_ui(), 0);
4001 assert_eq!(z.try_add(&z).unwrap(), z);
4002 assert_eq!(z.try_sub(&z).unwrap(), z);
4003 assert_eq!(z.try_mul(&z).unwrap(), z);
4004 assert_eq!(z.isqrt(), z);
4005 assert_eq!(z.com(), Mpz::from_i64(-1));
4006 }
4007
4008 #[test]
4009 fn zero_ops_full() {
4010 let z = Mpz::new();
4011 assert_eq!(z.mpz_get_ull(), 0);
4012 assert_eq!(z.mpz_get_sll(), 0);
4013 assert_eq!(z.cmp(&z), Ordering::Equal);
4014 assert_eq!(z.cmpabs(&z), Ordering::Equal);
4015 assert_eq!(z.to_i128(), Some(0));
4016 assert_eq!(Mpz::from_u64(0).remove_pow10(), 0);
4017 assert!(z.divisible_ui(7));
4018 assert_eq!(z.tdiv_ui(7), 0);
4019 assert_eq!(z.tdiv_q_ui(7), z);
4020 assert_eq!(z.try_mul_2exp(100).unwrap(), z);
4021 assert_eq!(z.fdiv_q_2exp(100), z);
4022 assert_eq!(z.fdiv_r_2exp(100), z);
4023 assert_eq!(z.even_p(), true);
4024 assert_eq!(z.odd_p(), false);
4025 }
4026
4027 #[test]
4028 fn neg_abs() {
4029 let a = Mpz::from_i64(-123);
4030 let mut b = a.clone();
4031 b.abs();
4032 assert_eq!(s(&b), "123");
4033 b.neg();
4034 assert_eq!(s(&b), "-123");
4035 assert_eq!(s(&a.neg_to()), "123");
4036 assert_eq!(s(&a.abs_to()), "123");
4037 }
4038
4039 #[test]
4040 fn cmp_ext() {
4041 let a = Mpz::from_i64(-100);
4042 let b = Mpz::from_i64(0);
4043 assert_eq!(a.cmp_si(-100), Ordering::Equal);
4044 assert_eq!(b.cmp_ui(0), Ordering::Equal);
4045 assert_eq!(a.cmp_si(-99), Ordering::Less);
4046 assert_eq!(Mpz::from_u64(50).cmpabs_ui(100), Ordering::Less);
4047 }
4048
4049 #[test]
4050 fn fits_checks() {
4051 assert!(Mpz::from_u64(255).fits_uint());
4052 assert!(Mpz::from_u64(255).fits_sint());
4053 assert!(Mpz::from_i64(-1).fits_slong());
4054 assert!(!Mpz::from_u64(u64::MAX).fits_uint());
4055 assert!(!Mpz::from_i64(i64::MIN).fits_ulong());
4056 assert!(Mpz::from_u64(42).fits_ushort());
4057 assert!(Mpz::from_i64(-42).fits_sshort());
4058 }
4059
4060 #[test]
4061 fn odd_even() {
4062 assert!(Mpz::from_u64(1).odd_p());
4063 assert!(Mpz::from_u64(2).even_p());
4064 assert!(Mpz::from_i64(-3).odd_p());
4065 assert!(Mpz::new().even_p());
4066 }
4067
4068 #[test]
4069 fn div_floor() {
4070 let a = Mpz::from_i64(-100);
4071 let d = Mpz::from_i64(30);
4072 let (q, r) = a.try_fdiv_qr(&d).unwrap();
4073 assert_eq!(s(&q), "-4");
4074 assert_eq!(s(&r), "20");
4075 let a2 = Mpz::from_i64(100);
4076 let (q2, r2) = a2.try_fdiv_qr(&d).unwrap();
4077 assert_eq!(s(&q2), "3");
4078 assert_eq!(s(&r2), "10");
4079 }
4080
4081 #[test]
4082 fn div_floor_ui() {
4083 let a = Mpz::from_i64(-100);
4084 let r = a.fdiv_ui(30);
4085 assert_eq!(r, 20);
4086 }
4087
4088 #[test]
4089 fn div_mod() {
4090 let a = Mpz::from_i64(-100);
4091 let d = Mpz::from_i64(30);
4092 let r = a.try_mod(&d).unwrap();
4093 assert_eq!(s(&r), "20");
4094 }
4095
4096 #[test]
4097 fn divisible_tests() {
4098 let a = Mpz::from_u64(100);
4099 assert!(a.divisible_ui(5));
4100 assert!(!a.divisible_ui(3));
4101 assert!(a.divisible_p(&Mpz::from_u64(20)));
4102 assert!(!a.divisible_p(&Mpz::from_u64(30)));
4103 assert!(Mpz::from_u64(64).divisible_2exp_p(6));
4104 assert!(!Mpz::from_u64(65).divisible_2exp_p(6));
4105 }
4106
4107 #[test]
4108 fn congruent_tests() {
4109 let a = Mpz::from_i64(17);
4110 assert!(a.congruent_ui_p(5, 12));
4111 assert!(!a.congruent_ui_p(6, 12));
4112 }
4113
4114 #[test]
4115 fn gcd_lcm() {
4116 let a = Mpz::from_u64(12);
4117 let b = Mpz::from_u64(18);
4118 assert_eq!(s(&a.try_gcd(&b).unwrap()), "6");
4119 assert_eq!(s(&a.try_lcm(&b).unwrap()), "36");
4120 assert_eq!(a.gcd_ui(18), 6);
4121 }
4122
4123 #[test]
4124 fn gcdext() {
4125 let a = Mpz::from_u64(120);
4126 let b = Mpz::from_u64(23);
4127 let (g, s_coeff, t) = a.try_gcdext(&b).unwrap();
4128 let check = s_coeff
4129 .try_mul(&a)
4130 .unwrap()
4131 .try_add(&t.try_mul(&b).unwrap())
4132 .unwrap();
4133 assert_eq!(check, g);
4134 assert_eq!(s(&g), "1");
4135 }
4136
4137 #[test]
4138 fn invert() {
4139 let a = Mpz::from_u64(3);
4140 let m = Mpz::from_u64(13);
4141 let inv = a.try_invert(&m).unwrap();
4142 let prod = a.try_mul(&inv).unwrap().try_mod(&m).unwrap();
4143 assert_eq!(prod, Mpz::from_u64(1));
4144 }
4145
4146 #[test]
4147 fn jacobi_symbol() {
4148 assert_eq!(Mpz::from_u64(1).jacobi(&Mpz::from_u64(3)), 1);
4149 assert_eq!(Mpz::from_u64(2).jacobi(&Mpz::from_u64(3)), -1);
4150 assert_eq!(Mpz::from_u64(0).jacobi(&Mpz::from_u64(3)), 0);
4151 }
4152
4153 #[test]
4154 fn factorial() {
4155 assert_eq!(s(&Mpz::try_fac_ui(5).unwrap()), "120");
4156 assert_eq!(s(&Mpz::try_fac_ui(0).unwrap()), "1");
4157 }
4158
4159 #[test]
4160 fn binomial() {
4161 assert_eq!(s(&Mpz::try_bin_uiui(10, 5).unwrap()), "252");
4162 assert_eq!(s(&Mpz::try_bin_uiui(10, 0).unwrap()), "1");
4163 assert_eq!(s(&Mpz::try_bin_uiui(10, 10).unwrap()), "1");
4164 }
4165
4166 #[test]
4167 fn fibonacci() {
4168 assert_eq!(s(&Mpz::try_fib_ui(0).unwrap()), "0");
4169 assert_eq!(s(&Mpz::try_fib_ui(1).unwrap()), "1");
4170 assert_eq!(s(&Mpz::try_fib_ui(10).unwrap()), "55");
4171 }
4172
4173 #[test]
4174 fn bitwise_ops() {
4175 let a = Mpz::from_u64(0b1100);
4176 let b = Mpz::from_u64(0b1010);
4177 assert_eq!(a.try_and(&b).unwrap(), Mpz::from_u64(0b1000));
4178 assert_eq!(a.try_ior(&b).unwrap(), Mpz::from_u64(0b1110));
4179 assert_eq!(a.try_xor(&b).unwrap(), Mpz::from_u64(0b0110));
4180 let neg = Mpz::from_i64(-1);
4181 assert_eq!(a.try_and(&neg).unwrap(), a);
4182 assert_eq!(a.try_ior(&neg).unwrap(), neg);
4183 }
4184
4185 #[test]
4186 fn popcount_hamdist() {
4187 assert_eq!(Mpz::from_u64(0b1010).popcount(), Some(2));
4188 assert_eq!(Mpz::new().popcount(), Some(0));
4189 assert_eq!(Mpz::from_i64(-1).popcount(), None);
4190 assert_eq!(
4191 Mpz::from_u64(0b1100).hamdist(&Mpz::from_u64(0b1010)),
4192 Some(2)
4193 );
4194 }
4195
4196 #[test]
4197 fn scan_tstbit() {
4198 let a = Mpz::from_u64(0b1010_0000);
4199 assert_eq!(a.scan1(0), Some(5));
4200 assert_eq!(a.scan0(0), 0);
4201 assert!(a.tstbit(5));
4202 assert!(!a.tstbit(4));
4203 let mut b = Mpz::new();
4204 b.try_setbit(7).unwrap();
4205 assert_eq!(s(&b), "128");
4206 b.clrbit(7);
4207 assert_eq!(b, Mpz::new());
4208 }
4209
4210 #[test]
4211 fn power_root_tests() {
4212 assert_eq!(
4213 s(&Mpz::try_ui_pow_ui(2, 100).unwrap()),
4214 "1267650600228229401496703205376"
4215 );
4216 assert_eq!(Mpz::from_u64(100).isqrt(), Mpz::from_u64(10));
4217 let (root, rem) = Mpz::from_u64(10).try_sqrtrem().unwrap();
4218 assert_eq!(root, Mpz::from_u64(3));
4219 assert_eq!(rem, Mpz::from_u64(1));
4220 assert!(Mpz::from_u64(144).perfect_square_p());
4221 assert!(!Mpz::from_u64(2).perfect_square_p());
4222 assert!(Mpz::from_u64(8).perfect_power_p());
4223 assert!(!Mpz::from_u64(2).perfect_power_p());
4224 }
4225
4226 #[test]
4227 fn powm_test() {
4228 let base = Mpz::from_u64(3);
4229 let exp = Mpz::from_u64(5);
4230 let m = Mpz::from_u64(7);
4231 let r = base.try_powm(&exp, &m).unwrap();
4232 assert_eq!(r, Mpz::from_u64(5));
4233 }
4234
4235 #[test]
4236 fn root_test() {
4237 let r = Mpz::from_u64(1000).try_root(3).unwrap();
4238 assert_eq!(r, Mpz::from_u64(10));
4239 let r2 = Mpz::from_u64(100).try_root(3).unwrap();
4240 assert_eq!(r2, Mpz::from_u64(4));
4241 }
4242
4243 #[test]
4244 fn remove_test() {
4245 let a = Mpz::from_u64(2700);
4246 let (rem, count) = a.try_remove(&Mpz::from_u64(2)).unwrap();
4247 assert_eq!(count, 2);
4248 assert_eq!(rem, Mpz::from_u64(675));
4249 }
4250
4251 #[test]
4252 fn add_sub_mul_assign() {
4253 let mut a = Mpz::from_u64(5);
4254 let b = Mpz::from_u64(3);
4255 a += &b;
4256 assert_eq!(s(&a), "8");
4257 a -= &b;
4258 assert_eq!(s(&a), "5");
4259 a *= &b;
4260 assert_eq!(s(&a), "15");
4261 }
4262
4263 #[test]
4264 fn addmul_submul() {
4265 let mut a = Mpz::from_u64(10);
4266 a.try_addmul(&Mpz::from_u64(3), &Mpz::from_u64(5)).unwrap();
4267 assert_eq!(a, Mpz::from_u64(25));
4268 a.try_submul(&Mpz::from_u64(2), &Mpz::from_u64(5)).unwrap();
4269 assert_eq!(a, Mpz::from_u64(15));
4270 }
4271
4272 #[test]
4273 fn ui_sub() {
4274 let r = Mpz::try_ui_sub(100, &Mpz::from_u64(1)).unwrap();
4275 assert_eq!(r, Mpz::from_u64(99));
4276 let r2 = Mpz::try_ui_sub(0, &Mpz::from_u64(5)).unwrap();
4277 assert_eq!(r2, Mpz::from_i64(-5));
4278 }
4279
4280 #[test]
4281 fn neg_to_abs_to() {
4282 let a = Mpz::from_i64(-5);
4283 assert_eq!(a.neg_to(), Mpz::from_u64(5));
4284 assert_eq!(a.abs_to(), Mpz::from_u64(5));
4285 let b = Mpz::from_u64(5);
4286 assert_eq!(b.neg_to(), Mpz::from_i64(-5));
4287 assert_eq!(b.abs_to(), Mpz::from_u64(5));
4288 }
4289
4290 #[test]
4291 fn swap_test() {
4292 let mut a = Mpz::from_u64(42);
4293 let mut b = Mpz::from_u64(100);
4294 a.swap(&mut b);
4295 assert_eq!(a, Mpz::from_u64(100));
4296 assert_eq!(b, Mpz::from_u64(42));
4297 }
4298
4299 #[test]
4300 fn set_test() {
4301 let mut a = Mpz::new();
4302 a.set(&Mpz::from_u64(123));
4303 assert_eq!(a, Mpz::from_u64(123));
4304 }
4305
4306 #[test]
4307 fn sizeinbase_test() {
4308 assert_eq!(Mpz::from_u64(255).try_sizeinbase(10), Some(3));
4309 assert_eq!(Mpz::from_u64(255).try_sizeinbase(16), Some(2));
4310 assert_eq!(Mpz::from_u64(255).try_sizeinbase(2), Some(8));
4311 assert_eq!(Mpz::new().try_sizeinbase(10), Some(1));
4312 assert_eq!(Mpz::from_i64(-5).try_sizeinbase(10), Some(2));
4313 assert_eq!(Mpz::from_u64(255).try_sizeinbase(1), None);
4314 }
4315
4316 #[test]
4317 fn get_d_test() {
4318 assert!((Mpz::from_u64(123).get_d() - 123.0).abs() < 1e-10);
4319 assert!((Mpz::from_i64(-42).get_d() - (-42.0)).abs() < 1e-10);
4320 assert_eq!(Mpz::new().get_d(), 0.0);
4321 }
4322
4323 #[test]
4324 fn get_d_2exp_test() {
4325 let v = Mpz::from_u64(42);
4326 let (m, e) = v.get_d_2exp().unwrap();
4327 assert!((m * 2.0f64.powi(e as i32) - 42.0).abs() < 1e-10);
4328 assert!(m.abs() >= 0.5 && m.abs() < 1.0);
4329 assert_eq!(Mpz::new().get_d_2exp(), None);
4330 }
4331
4332 #[test]
4333 fn parse_errors() {
4334 assert_eq!(Mpz::from_decimal_str(""), Err(ParseError::InvalidInput));
4335 assert_eq!(Mpz::from_decimal_str("-"), Err(ParseError::InvalidInput));
4336 assert_eq!(Mpz::from_decimal_str("+"), Err(ParseError::InvalidInput));
4337 assert_eq!(
4338 Mpz::from_decimal_str("12a34"),
4339 Err(ParseError::InvalidInput)
4340 );
4341 assert_eq!(
4342 Mpz::from_decimal_str("12O34"),
4343 Err(ParseError::InvalidInput)
4344 );
4345 }
4346
4347 #[test]
4348 fn roundtrip_extreme() {
4349 let vals = [
4350 "0",
4351 "1",
4352 "-1",
4353 "9",
4354 "10",
4355 "-10",
4356 "999999999999999999",
4357 "-999999999999999999",
4358 "1000000000000000000",
4359 "123456789012345678901234567890123456789012345678901234567890",
4360 ];
4361 for v in &vals {
4362 let m = Mpz::from_decimal_str(v).unwrap();
4363 assert_eq!(&s(&m), v, "round-trip failed for {v}");
4364 }
4365 }
4366
4367 #[test]
4368 fn max_limb_capacity() {
4369 let mut mpz = Mpz::new();
4370 for i in 0..8 {
4371 mpz.mag[i] = u64::MAX;
4372 }
4373 mpz.len = 8;
4374 mpz.sign = 1;
4375 assert_eq!(mpz.try_add(&Mpz::from_u64(1)), Err(CapacityError));
4376 assert_eq!(Mpz::try_ui_pow_ui(2, 512), Err(CapacityError));
4377 }
4378
4379 #[test]
4380 fn cdiv_test() {
4381 let a = Mpz::from_i64(-100);
4382 let d = Mpz::from_i64(30);
4383 let (q, r) = a.try_cdiv_qr(&d).unwrap();
4384 assert_eq!(q.try_mul(&d).unwrap().try_add(&r).unwrap(), a);
4385 }
4386
4387 #[test]
4388 fn mul_si_test() {
4389 let a = Mpz::from_u64(10);
4390 assert_eq!(a.try_mul_si(5).unwrap(), Mpz::from_u64(50));
4391 assert_eq!(a.try_mul_si(-3).unwrap(), Mpz::from_i64(-30));
4392 }
4393
4394 #[test]
4395 fn addmul_ui_submul_ui() {
4396 let mut a = Mpz::from_u64(10);
4397 a.try_addmul_ui(&Mpz::from_u64(3), 5).unwrap();
4398 assert_eq!(a, Mpz::from_u64(25));
4399 a.try_submul_ui(&Mpz::from_u64(2), 5).unwrap();
4400 assert_eq!(a, Mpz::from_u64(15));
4401 }
4402
4403 #[test]
4404 fn tdiv_r_ui_test() {
4405 let a = Mpz::from_i64(-100);
4406 let r = a.tdiv_r_ui(30);
4407 assert_eq!(r, Mpz::from_u64(10));
4408 }
4409
4410 #[test]
4411 fn tdiv_2exp_test() {
4412 let a = Mpz::from_u64(0b1101);
4413 assert_eq!(a.tdiv_q_2exp(2), Mpz::from_u64(0b11));
4414 assert_eq!(a.tdiv_r_2exp(2), Mpz::from_u64(0b01));
4415 }
4416
4417 #[test]
4418 fn setbit_clrbit_combit() {
4419 let mut a = Mpz::new();
4420 a.try_setbit(0).unwrap();
4421 assert_eq!(a, Mpz::from_u64(1));
4422 a.try_setbit(2).unwrap();
4423 assert_eq!(a, Mpz::from_u64(5));
4424 a.clrbit(2);
4425 assert_eq!(a, Mpz::from_u64(1));
4426 a.try_combit(1).unwrap();
4427 assert_eq!(a, Mpz::from_u64(3));
4428 }
4429
4430 #[test]
4431 fn scan_test() {
4432 let a = Mpz::from_u64(0b1010_0000);
4433 assert_eq!(a.scan1(0), Some(5));
4434 assert_eq!(a.scan0(5), 6);
4435 assert_eq!(a.scan1(8), None);
4436 assert_eq!(Mpz::from_u64(0).scan1(0), None);
4437 }
4438
4439 #[test]
4440 fn perfect_power_test() {
4441 assert!(Mpz::from_u64(27).perfect_power_p());
4442 assert!(Mpz::from_u64(16).perfect_power_p());
4443 assert!(!Mpz::from_u64(2).perfect_power_p());
4444 assert!(!Mpz::new().perfect_power_p());
4445 }
4446
4447 #[test]
4448 fn congruent_2exp_test() {
4449 assert!(Mpz::from_u64(17).congruent_2exp_p(&Mpz::from_u64(1), 4));
4450 assert!(Mpz::from_u64(18).congruent_2exp_p(&Mpz::from_u64(2), 4));
4451 }
4452
4453 #[test]
4454 fn remove_general_test() {
4455 let a = Mpz::try_ui_pow_ui(2, 5)
4456 .unwrap()
4457 .try_mul(&Mpz::try_ui_pow_ui(3, 2).unwrap())
4458 .unwrap();
4459 let (rem, cnt) = a.try_remove(&Mpz::from_u64(2)).unwrap();
4460 assert_eq!(cnt, 5);
4461 assert_eq!(rem, Mpz::from_u64(9));
4462 }
4463
4464 #[test]
4465 fn try_divexact_test() {
4466 let a = Mpz::from_u64(100);
4467 assert_eq!(
4468 a.try_divexact(&Mpz::from_u64(5)).unwrap(),
4469 Mpz::from_u64(20)
4470 );
4471 assert_eq!(a.try_divexact_ui(4).unwrap(), Mpz::from_u64(25));
4472 }
4473
4474 #[test]
4477 fn tstbit_negative_bug() {
4478 let neg = Mpz::from_i64(-5);
4480
4481 assert!(
4483 neg.tstbit(100),
4484 "tstbit(-5, 100) should be true (sign extension)"
4485 );
4486
4487 let pos = Mpz::from_u64(5);
4489 assert!(!pos.tstbit(100), "tstbit(5, 100) should be false");
4490
4491 let zero = Mpz::new();
4493 assert!(!zero.tstbit(100), "tstbit(0, 100) should be false");
4494
4495 let neg_one = Mpz::from_i64(-1);
4497 assert!(neg_one.tstbit(0), "tstbit(-1, 0)");
4499 assert!(neg_one.tstbit(64), "tstbit(-1, 64) - sign extension");
4501 assert!(neg_one.tstbit(200), "tstbit(-1, 200) - sign extension");
4502 }
4503
4504 #[test]
4505 fn bitwise_negative_bug() {
4506 let n2 = Mpz::from_i64(-2);
4513 let n3 = Mpz::from_i64(-3);
4514 assert_eq!(n2.try_and(&n3).unwrap(), Mpz::from_i64(-4));
4515
4516 let n5 = Mpz::from_i64(-5);
4521 let p3 = Mpz::from_u64(3);
4522 assert_eq!(n5.try_and(&p3).unwrap(), Mpz::from_u64(3));
4523
4524 assert_eq!(n5.try_ior(&p3).unwrap(), Mpz::from_i64(-5));
4529
4530 assert_eq!(n5.try_xor(&p3).unwrap(), Mpz::from_i64(-8));
4535 }
4536
4537 #[test]
4538 fn congruent_2exp_negative_bug() {
4539 assert!(Mpz::from_i64(-3).congruent_2exp_p(&Mpz::from_u64(13), 4));
4543 assert!(Mpz::from_i64(-3).congruent_2exp_p(&Mpz::from_i64(-3), 4));
4546 assert!(!Mpz::from_i64(-3).congruent_2exp_p(&Mpz::from_u64(3), 4));
4548 }
4549
4550 #[test]
4551 fn from_d_tests() {
4552 assert_eq!(Mpz::from_d(0.0).unwrap(), Mpz::new());
4554 assert_eq!(Mpz::from_d(1.0).unwrap(), Mpz::from_u64(1));
4555 assert_eq!(Mpz::from_d(-1.0).unwrap(), Mpz::from_i64(-1));
4556 assert_eq!(Mpz::from_d(255.0).unwrap(), Mpz::from_u64(255));
4557 assert_eq!(
4558 Mpz::from_d(1e18).unwrap(),
4559 Mpz::from_u64(1_000_000_000_000_000_000)
4560 );
4561 assert_eq!(
4562 Mpz::from_d(-1e18).unwrap(),
4563 Mpz::from_i64(-1_000_000_000_000_000_000)
4564 );
4565
4566 assert_eq!(Mpz::from_d(3.999).unwrap(), Mpz::from_u64(3));
4568 assert_eq!(Mpz::from_d(-3.999).unwrap(), Mpz::from_i64(-3));
4569 assert_eq!(Mpz::from_d(0.999).unwrap(), Mpz::new());
4570
4571 assert_eq!(Mpz::from_d(1e-300).unwrap(), Mpz::new());
4573
4574 assert_eq!(Mpz::from_d(f64::INFINITY), Err(CapacityError));
4576 assert_eq!(Mpz::from_d(f64::NEG_INFINITY), Err(CapacityError));
4577 assert_eq!(Mpz::from_d(f64::NAN), Err(CapacityError));
4578 }
4579
4580 #[test]
4581 fn sizeinbase_rigorous() {
4582 let val = Mpz::from_u64(12345);
4584 let sz = val.try_sizeinbase(10).unwrap();
4585 assert!(sz >= "12345".len());
4586
4587 let large = Mpz::try_ui_pow_ui(2, 200).unwrap();
4588 let sz10 = large.try_sizeinbase(10).unwrap();
4589 assert!(sz10 >= s(&large).len());
4590 }
4591
4592 #[test]
4593 fn knuth_division_tests() {
4594 let a = Mpz::from_u64(1).try_mul_2exp(130).unwrap(); let b = Mpz::from_u64(1).try_mul_2exp(65).unwrap();
4597 let (q, r) = a.tdiv_qr(&b);
4598 assert_eq!(q, Mpz::from_u64(1).try_mul_2exp(65).unwrap());
4599 assert!(r.is_zero());
4600
4601 let x = Mpz::from_decimal_str("123456789012345678901234567890").unwrap();
4603 let y = Mpz::from_decimal_str("9876543210").unwrap();
4604 let (q2, r2) = x.tdiv_qr(&y);
4605 let check = q2.try_mul(&y).unwrap().try_add(&r2).unwrap();
4607 assert_eq!(check, x);
4608 assert!(r2.cmpabs(&y) == Ordering::Less);
4609 }
4610
4611 #[test]
4612 fn sealed_fields() {
4613 let a = Mpz::from_u64(42);
4614 assert_eq!(a.limbs(), &[42u64]);
4615 assert!(!a.is_zero());
4616 let b = Mpz::new();
4617 assert!(b.is_zero());
4618 assert!(b.limbs().is_empty());
4619 }
4620
4621 #[test]
4622 fn new_division_functions() {
4623 let a = Mpz::from_i64(-100);
4625 let (q, r) = a.try_tdiv_qr_ui(30).unwrap();
4626 assert_eq!(q, Mpz::from_i64(-3));
4627 assert_eq!(r, 10);
4628
4629 let r = a.try_fdiv_r_ui(30).unwrap();
4631 assert_eq!(r, Mpz::from_u64(20));
4632
4633 let (q, r_u64) = a.try_cdiv_qr_ui(30).unwrap();
4635 assert_eq!(q, Mpz::from_i64(-3));
4636 assert_eq!(r_u64, 10);
4637
4638 let r = a.cdiv_ui(30);
4640 assert_eq!(r, 10);
4642
4643 let pos = Mpz::from_u64(100);
4645 let q = pos.cdiv_q_2exp(3); assert_eq!(q, Mpz::from_u64(13));
4647 let r = pos.cdiv_r_2exp(3); assert_eq!(r, Mpz::from_i64(-4));
4651 }
4652
4653 #[test]
4654 fn number_theory_functions() {
4655 assert_eq!(Mpz::from_u64(1).try_legendre(&Mpz::from_u64(7)), 1);
4657 assert_eq!(Mpz::from_u64(2).try_legendre(&Mpz::from_u64(7)), 1);
4658 assert_eq!(Mpz::from_u64(3).try_legendre(&Mpz::from_u64(7)), -1);
4659
4660 assert_eq!(Mpz::from_u64(0).try_kronecker(&Mpz::from_u64(1)), 1);
4662 assert_eq!(Mpz::from_u64(2).try_kronecker(&Mpz::from_u64(5)), -1);
4663
4664 assert_eq!(Mpz::from_u64(5).try_kronecker_si(7), -1);
4667 assert_eq!(Mpz::from_u64(5).try_kronecker_ui(7), -1);
4668 assert_eq!(Mpz::try_si_kronecker(5, &Mpz::from_u64(7)), -1);
4669 assert_eq!(Mpz::try_ui_kronecker(5, &Mpz::from_u64(7)), -1);
4670 }
4671
4672 #[test]
4673 fn fib2_lucnum() {
4674 let (f_n, f_nm1) = Mpz::try_fib2_ui(10).unwrap();
4676 assert_eq!(f_n, Mpz::from_u64(55));
4677 assert_eq!(f_nm1, Mpz::from_u64(34));
4678
4679 assert_eq!(Mpz::try_lucnum_ui(10).unwrap(), Mpz::from_u64(123));
4681
4682 let (l_n, l_nm1) = Mpz::try_lucnum2_ui(10).unwrap();
4684 assert_eq!(l_n, Mpz::from_u64(123));
4685 assert_eq!(l_nm1, Mpz::from_u64(76));
4686 }
4687
4688 #[test]
4689 fn double_factorial() {
4690 assert_eq!(Mpz::try_2fac_ui(5).unwrap(), Mpz::from_u64(15));
4692 assert_eq!(Mpz::try_2fac_ui(6).unwrap(), Mpz::from_u64(48));
4694 assert_eq!(Mpz::try_2fac_ui(0).unwrap(), Mpz::from_u64(1));
4696 assert_eq!(Mpz::try_2fac_ui(1).unwrap(), Mpz::from_u64(1));
4697 }
4698
4699 #[test]
4700 fn primorial() {
4701 assert_eq!(Mpz::try_primorial_ui(10).unwrap(), Mpz::from_u64(210));
4703 assert_eq!(Mpz::try_primorial_ui(0).unwrap(), Mpz::from_u64(1));
4705 assert_eq!(Mpz::try_primorial_ui(1).unwrap(), Mpz::from_u64(1));
4706 }
4707
4708 #[test]
4709 fn bin_ui() {
4710 let n = Mpz::from_u64(10);
4712 assert_eq!(n.try_bin_ui(3).unwrap(), Mpz::from_u64(120));
4713 assert_eq!(n.try_bin_ui(0).unwrap(), Mpz::from_u64(1));
4715 let zero = Mpz::new();
4717 assert_eq!(zero.try_bin_ui(0).unwrap(), Mpz::from_u64(1));
4718 }
4719
4720 #[test]
4721 fn cmp_d_tests() {
4722 assert_eq!(Mpz::from_u64(5).cmp_d(3.0), Ordering::Greater);
4724 assert_eq!(Mpz::from_u64(3).cmp_d(5.0), Ordering::Less);
4725 assert_eq!(Mpz::from_u64(3).cmp_d(3.0), Ordering::Equal);
4726 assert_eq!(Mpz::from_i64(-5).cmp_d(-3.0), Ordering::Less);
4728 assert_eq!(Mpz::from_i64(-3).cmp_d(-5.0), Ordering::Greater);
4729 assert_eq!(Mpz::from_i64(-5).cmp_d(3.0), Ordering::Less);
4731 assert_eq!(Mpz::from_u64(5).cmp_d(-3.0), Ordering::Greater);
4732 assert_eq!(Mpz::from_i64(-5).cmpabs_d(3.0), Ordering::Greater);
4734 assert_eq!(Mpz::from_i64(-3).cmpabs_d(5.0), Ordering::Less);
4735 }
4736
4737 #[test]
4738 fn getlimbn_test() {
4739 let a = Mpz::from_u128(0x1234567890ABCDEF);
4740 assert_eq!(a.getlimbn(0), Some(0x1234567890ABCDEF)); assert_eq!(a.getlimbn(1), None);
4743 assert_eq!(a.getlimbn(0), Some(0x1234567890ABCDEF));
4744
4745 let b = Mpz::new();
4746 assert_eq!(b.getlimbn(0), None);
4747 }
4748
4749 #[test]
4750 fn probab_prime_tests() {
4751 assert_eq!(Mpz::from_u64(2).try_probab_prime_p(5).unwrap(), 2);
4753 assert_eq!(Mpz::from_u64(3).try_probab_prime_p(5).unwrap(), 2);
4755 assert_eq!(Mpz::from_u64(4).try_probab_prime_p(5).unwrap(), 0);
4757 assert_eq!(Mpz::from_u64(17).try_probab_prime_p(5).unwrap(), 2);
4759 assert_eq!(Mpz::from_u64(1).try_probab_prime_p(5).unwrap(), 0);
4761 assert_eq!(Mpz::new().try_probab_prime_p(5).unwrap(), 0);
4763 assert_eq!(Mpz::from_i64(-5).try_probab_prime_p(5).unwrap(), 0);
4765 assert_eq!(Mpz::from_u64(7919).try_probab_prime_p(10).unwrap(), 2);
4767 }
4768
4769 #[test]
4770 fn import_export_tests() {
4771 let val = Mpz::from_u64(0x1234567890ABCDEF);
4773 let mut buf = [0u8; 8];
4774 let n = val
4775 .export_buf(&mut buf, Endian::Little, 1, Endian::Little)
4776 .unwrap();
4777 assert_eq!(n, 8);
4778
4779 let imported = Mpz::try_import(8, Endian::Little, 1, Endian::Little, &buf).unwrap();
4780 assert_eq!(imported, val);
4781
4782 let mut buf2 = [0u8; 8];
4784 let n2 = val
4785 .export_buf(&mut buf2, Endian::Big, 1, Endian::Big)
4786 .unwrap();
4787 assert_eq!(n2, 8);
4788 assert_eq!(buf2[0], 0x12);
4790 assert_eq!(buf2[7], 0xEF);
4791
4792 let imported2 = Mpz::try_import(8, Endian::Big, 1, Endian::Big, &buf2).unwrap();
4793 assert_eq!(imported2, val);
4794 }
4795
4796 #[test]
4797 fn knuth_multi_limb_division() {
4798 let a = Mpz::try_ui_pow_ui(2, 200).unwrap();
4800 let b = Mpz::try_ui_pow_ui(2, 100).unwrap();
4801 let (q, r) = a.tdiv_qr(&b);
4802 assert_eq!(q, Mpz::try_ui_pow_ui(2, 100).unwrap());
4803 assert!(r.is_zero());
4804
4805 let x = Mpz::from_decimal_str("1234567890123456789012345678901234567890").unwrap();
4807 let y = Mpz::from_decimal_str("98765432109876543210").unwrap();
4808 let (q2, r2) = x.tdiv_qr(&y);
4809 let check = q2.try_mul(&y).unwrap().try_add(&r2).unwrap();
4810 assert_eq!(check, x);
4811 assert!(r2.cmpabs(&y) == Ordering::Less || r2.is_zero());
4812 }
4813}