Skip to main content

gmp_rs/
lib.rs

1//! pure-Rust, **no-unsafe**, **`no_std`**, **`no_alloc`** arbitrary-precision signed integer (`Mpz`),
2//! faithful to GMP's `mpz_*` operations.
3//!
4//! # Guarantees
5//! - **Zero `unsafe` code** — `#![forbid(unsafe_code)]` enforced at compile time.
6//! - **`no_std`** — no standard library dependency; only `core`.
7//! - **`no_alloc`** — zero heap allocations in the library itself.  Fixed-capacity limb storage
8//!   (`[u64; 8]`, 512 bits ≈ 154 decimal digits).  Operations that would exceed capacity return
9//!   [`CapacityError`].
10//!
11//! # Representation
12//! Sign–magnitude.  `mag[0..len]` is little-endian base-2⁶⁴ limbs with no trailing zero
13//! (so zero is `len == 0 && sign == 0`).
14
15#![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
25// ===========================================================================
26// Constants
27// ===========================================================================
28
29/// Maximum number of 64-bit limbs.  8 limbs = 512 bits ≈ 154 decimal digits.
30pub const MPZ_MAX_LIMBS: usize = 8;
31
32/// Maximum bit width (512 bits).  Useful for static analysers.
33pub const MAX_BITS: usize = MPZ_MAX_LIMBS * 64;
34
35/// Maximum number of decimal digits representable
36/// (floor(log10(2^512)) = floor(512 * log10(2)) ≈ 154).
37pub const MAX_DECIMAL_DIGITS: usize = 154;
38
39/// Number of limbs (public alias for `MPZ_MAX_LIMBS`).
40pub const LIMBS: usize = MPZ_MAX_LIMBS;
41
42/// The 64 smallest primes, used for Miller–Rabin and related checks.
43const 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// ===========================================================================
51// Error types
52// ===========================================================================
53
54/// The operation would exceed the fixed limb capacity.
55#[derive(Debug, Clone, Copy, PartialEq, Eq)]
56pub struct CapacityError;
57
58/// An error occurred while parsing a decimal string.
59#[derive(Debug, Clone, Copy, PartialEq, Eq)]
60pub enum ParseError {
61    /// Malformed input (empty, invalid characters, misplaced sign).
62    InvalidInput,
63    /// The value exceeds the fixed limb capacity.
64    CapacityOverflow,
65}
66
67/// Byte order for [`Mpz::try_import`] and [`Mpz::export_buf`].
68#[derive(Debug, Clone, Copy, PartialEq, Eq)]
69pub enum Endian {
70    /// Native endianness (detected at runtime).
71    Native,
72    /// Little-endian (least significant byte first).
73    Little,
74    /// Big-endian (most significant byte first).
75    Big,
76}
77
78/// Determine native endianness at compile time.
79const fn native_is_little() -> bool {
80    // u16 with byte pattern 0x0102 → native read yields 0x0201 on LE, 0x0102 on BE.
81    // In const context we can't do pointer tricks, so we check cfg.
82    cfg!(target_endian = "little")
83}
84
85// ===========================================================================
86// Mpz type
87// ===========================================================================
88
89/// Arbitrary-precision signed integer with **fixed capacity** (no heap allocation).
90///
91/// Up to [`MPZ_MAX_LIMBS`] little-endian 64-bit limbs in sign–magnitude.
92///
93/// # Sealed fields
94/// The fields `sign`, `len`, and `mag` are **private** to maintain invariants.
95/// Use [`limbs`](Mpz::limbs) and [`is_zero`](Mpz::is_zero) for read access.
96#[derive(Clone, Debug, Eq)]
97pub struct Mpz {
98    /// -1, 0, or +1.  Invariant: `sign == 0` iff `len == 0`.
99    sign: i8,
100    /// Number of active limbs in `mag[0..len]`.
101    len: usize,
102    /// Fixed-capacity limb storage.  Only `mag[0..len]` is meaningful.
103    mag: [u64; MPZ_MAX_LIMBS],
104}
105
106// ===========================================================================
107// Trait impls
108// ===========================================================================
109
110impl 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
146// In-place assignment operators (infallible for reusing lhs allocation)
147impl 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
165// ===========================================================================
166// Mpz implementation — all methods in a single impl block
167// ===========================================================================
168
169impl Mpz {
170    // -----------------------------------------------------------------------
171    // Public accessors (sealed fields)
172    // -----------------------------------------------------------------------
173
174    /// Return the magnitude limbs as a slice.  The slice length is the number
175    /// of active limbs; zero is represented as an empty slice.
176    pub fn limbs(&self) -> &[u64] {
177        &self.mag[..self.len]
178    }
179
180    /// Return `true` iff the value is zero.
181    pub fn is_zero(&self) -> bool {
182        self.sign == 0
183    }
184
185    /// Construct from raw parts (testing only — may violate invariants).
186    #[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    // -----------------------------------------------------------------------
205    // Internal magnitude helpers (work on &[u64] slices, write into fixed arrays)
206    // -----------------------------------------------------------------------
207
208    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    /// `a + b`.  Returns `None` if result would exceed `MPZ_MAX_LIMBS`.
218    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    /// `a - b` (magnitudes, `a >= b`).  Trims trailing zeros.
242    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        // The theoretical max result limbs = a.len() + b.len().
267        // But we can only store MPZ_MAX_LIMBS, so cap writes at that.
268        // If the result needs more than MPZ_MAX_LIMBS, we detect it
269        // during computation (carry into last limb) or after trimming.
270        let max_idx = if a.len() + b.len() > MPZ_MAX_LIMBS {
271            // We can still compute but must watch for carry into the
272            // non-existent extra limb.
273            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            // Only iterate over b indices where i + j <= max_idx
283            for (j, &bj) in b.iter().enumerate() {
284                let idx = i + j;
285                if idx > max_idx {
286                    // This limb would write beyond capacity.
287                    // The carry from a[i]*b[j] is still added to the accumulator
288                    // and must be accounted for, but we can't store it.
289                    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            // Write carry into next limb if possible
297            let next_idx = i + b.len();
298            if carry != 0 {
299                if next_idx > max_idx {
300                    // Would overflow beyond capacity
301                    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    /// `a / d`, `a % d`.  Returns `(quotient_len, remainder)`.
314    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    // -----------------------------------------------------------------------
329    // Knuth's Algorithm D (TAOCP Vol 2, 4.3.1) for multi-limb division
330    // -----------------------------------------------------------------------
331
332    /// Divide `u` by `v` using Knuth's Algorithm D (base 2^64).
333    /// `v.len() >= 2`.  Writes quotient into `qbuf` and remainder into `rbuf`.
334    /// Returns `(quotient_len, remainder_len)`.
335    ///
336    /// **Precondition**: `u` is the dividend mag, `v` is the divisor mag,
337    /// `u.len() >= v.len()`, `v.len() >= 2`, and `qbuf.len() >= u.len()`,
338    /// `rbuf.len() >= v.len()`.
339    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; // number of quotient limbs (m >= 0)
347
348        // Clear quotient buffer
349        for q in qbuf.iter_mut().take(m + 1) {
350            *q = 0;
351        }
352
353        // D1. Normalise: shift so that v[n-1] >= 2^63
354        let s = v[n - 1].leading_zeros();
355        let mut uu = [0u64; MPZ_MAX_LIMBS + 2]; // normalised dividend (m+n+1 limbs)
356        let mut vv = [0u64; MPZ_MAX_LIMBS + 1]; // normalised divisor (n limbs)
357
358        // Shift v
359        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        // Shift u (needs m+n+1 limbs)
371        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        // D2. Loop over j from m down to 0
388        for j in (0..=m).rev() {
389            // D3. Estimate quotient limb q̂
390            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            // D4. Adjust q̂ downward if needed
401            let mut r_hat = if ujn == vn1 as u128 {
402                // ujn * B + ujn1 - q̂ * vn1
403                // Since q̂ = B-1, we compute:
404                (ujn << 64) | ujn1.wrapping_sub(q_hat * vn1 as u128)
405            } else {
406                ((ujn << 64) | ujn1) - q_hat * vn1 as u128
407            };
408
409            // Check q̂ >= 2^64 (shouldn't happen as q̂ <= B-1)
410            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            // D4 adjustment loop
417
418            loop {
419                // Test q̂ * vn2 > B * r̂ + u[j+n-2]
420                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                    // r̂ crossed into next limb, can't overflow again
429                    break;
430                }
431            }
432
433            // D5. Subtract q̂ * vv from uu[j..j+n]
434            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            // Final borrow against uu[j+n]
449            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            // D6. If result negative, add back vv and decrement q̂
457            if needs_add_back {
458                // Add back vv
459                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        // D8. Unnormalise remainder: uu[0..n] is the remainder, shift right by s
473        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                // Simplify: we're shifting right by s, so take top s bits from the left
482            }
483            // Better approach: shift right by s
484            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        // Trim remainder
493        let mut rlen = n;
494        while rlen > 0 && rbuf[rlen - 1] == 0 {
495            rlen -= 1;
496        }
497
498        // Trim quotient
499        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    // ---- Positive remainder building blocks for fdiv/cdiv/mod ---------------
521
522    /// Return `(q, r)` with `0 ≤ r < |d|` and `n = q*d + r`.
523    /// Sign of `r` is always non-negative.
524    #[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            // q -= 1; r += |d|
529            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    /// Ceiling remainder: `r` has opposite sign to `d` or zero.
539    #[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            // q += 1; r -= |d|
544            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    // -----------------------------------------------------------------------
554    // Construction
555    // -----------------------------------------------------------------------
556
557    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    /// `mpz_set_ull`: construct from `u64`.
625    pub fn set_ull(val: u64) -> Self {
626        Self::from_u64(val)
627    }
628
629    /// `mpz_set_sll`: construct from `i64`.
630    pub fn mpz_set_sll(val: i64) -> Self {
631        Self::from_i64(val)
632    }
633
634    /// Construct from raw limbs with validation.
635    ///
636    /// Returns `None` if:
637    /// - `limbs.len() > LIMBS`
638    /// - `sign` is not -1, 0, or 1
639    /// - non-zero value has trailing zero limb
640    /// - zero value has non-zero sign
641    ///
642    /// This is the safe, public way to construct an `Mpz` from raw limb data.
643    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        // Trim trailing zeros
651        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; // non-zero sign with zero magnitude
660        }
661        if sign == 0 {
662            return None; // zero sign with non-zero magnitude
663        }
664        let mut mag = [0u64; LIMBS];
665        mag[..len].copy_from_slice(&limbs[..len]);
666        Some(Mpz { sign, len, mag })
667    }
668
669    /// `mpz_swap`: swap two Mpz values (infallible, no alloc).
670    pub fn swap(&mut self, other: &mut Self) {
671        core::mem::swap(self, other);
672    }
673
674    /// `mpz_set`: copy from another Mpz.
675    pub fn set(&mut self, src: &Self) {
676        *self = src.clone();
677    }
678
679    /// `mpz_set_d`: convert `f64` to Mpz, truncating toward zero.
680    ///
681    /// Returns `Err(CapacityError)` if the integer value exceeds the fixed capacity.
682    /// Subnormals, zero → zero.  Infinities and NaN → `Err(CapacityError)`.
683    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; // unbiased exponent
687        let mant = bits & 0x000F_FFFF_FFFF_FFFF; // 52-bit mantissa
688
689        // Zero / subnormal
690        if exp < -1074 {
691            // 2^(-1074) is the smallest positive subnormal; anything below rounds to 0
692            return Ok(Mpz::new());
693        }
694        if exp == -1023 {
695            // Zero (mant == 0) or subnormal (mant != 0, biased exponent == 0)
696            if mant == 0 {
697                return Ok(Mpz::new());
698            }
699            // Subnormal: no implicit leading 1, exponent is -1022
700            // Value = mant * 2^(-1074) which is < 1, truncates to 0
701            return Ok(Mpz::new());
702        }
703
704        // Infinity or NaN
705        if exp == 1024 {
706            return Err(CapacityError);
707        }
708
709        // Normal value: mantissa = 1.xxx (53 bits including implicit 1)
710        let mut full_mant = (1u128 << 52) | mant as u128; // 53-bit mantissa
711        let mut total_exp = exp;
712
713        // We have value = full_mant * 2^(total_exp - 52)
714        total_exp -= 52;
715
716        if total_exp < 0 {
717            // Fractional: truncate toward zero
718            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        // Integer: shift left
740        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                        // 53-bit mantissa, so hi can't overflow further with a 53-bit value
766                        // Actually full_mant is at most 2^53-1, which fits in u64
767                    }
768                }
769                // Determine proper length
770                let mut max_idx = ls + 1;
771                if hi != 0 {
772                    max_idx = ls + 2;
773                }
774                // Check if full_mant >> (64-bs) produces another limb
775                if (full_mant >> (64 - bs)) != 0 {
776                    // Already handled above
777                }
778                // Recompute more carefully
779                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            // total_exp == 0: just the mantissa
790            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    // -----------------------------------------------------------------------
808    // Conversion (no alloc)
809    // -----------------------------------------------------------------------
810
811    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    /// `mpz_get_d`: convert to f64 (truncating toward zero).
849    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    /// `mpz_get_d_2exp`: convert to `(mantissa, exponent)` with `0.5 ≤ |mantissa| < 1`.
865    pub fn get_d_2exp(&self) -> Option<(f64, i64)> {
866        if self.len == 0 {
867            return None;
868        }
869        let bits = self.sizeinbase2();
870        // Top 53 bits as mantissa
871        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        // Normalise to [0.5, 1.0)
880        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    /// `mpz_fits_slong_p`: fits in a signed 64-bit integer?
901    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    /// `mpz_fits_uint_p`: fits in u32?
913    pub fn fits_uint(&self) -> bool {
914        self.sign >= 0 && self.len <= 1 && self.mag[0] <= u32::MAX as u64
915    }
916
917    /// `mpz_fits_sint_p`: fits in i32?
918    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    /// `mpz_fits_ushort_p`: fits in u16?
933    pub fn fits_ushort(&self) -> bool {
934        self.sign >= 0 && self.len <= 1 && self.mag[0] <= u16::MAX as u64
935    }
936
937    /// `mpz_fits_sshort_p`: fits in i16?
938    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    // -----------------------------------------------------------------------
971    // Set (in-place)
972    // -----------------------------------------------------------------------
973
974    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    // -----------------------------------------------------------------------
983    // Sign / compare
984    // -----------------------------------------------------------------------
985
986    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    /// Non-mutating negation.
1001    pub fn neg_to(&self) -> Mpz {
1002        let mut c = self.clone();
1003        c.sign = -c.sign;
1004        c
1005    }
1006
1007    /// Non-mutating absolute value.
1008    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    /// `mpz_cmp_si`: compare with signed 64-bit integer.
1045    pub fn cmp_si(&self, v: i64) -> Ordering {
1046        self.cmp(&Mpz::from_i64(v))
1047    }
1048
1049    /// `mpz_cmp_ui`: compare with unsigned 64-bit integer.
1050    pub fn cmp_ui(&self, v: u64) -> Ordering {
1051        self.cmp(&Mpz::from_u64(v))
1052    }
1053
1054    /// `mpz_cmpabs_ui`: compare absolute value with unsigned 64-bit integer.
1055    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    // -----------------------------------------------------------------------
1071    // try_sizeinbase — guaranteed upper bound
1072    // -----------------------------------------------------------------------
1073
1074    /// `mpz_sizeinbase(_, base)`: upper bound on chars needed to represent in given base.
1075    ///
1076    /// Guarantees the returned bound is ≥ the true size.  Only supports bases 2–36.
1077    /// Returns `None` for unsupported bases.
1078    ///
1079    /// For power-of-two bases (2, 4, 8, 16, 32) uses exact bit-length division.
1080    /// For other bases, iteratively computes `base^k` until `base^k > |self|`,
1081    /// which rigorously bounds the size.
1082    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        // Power-of-two bases: exact
1092        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                // Use rigorous iteration: compute base^k until > |self|
1100                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                    // Safety: if power exceeds capacity we can't multiply further,
1111                    // but if it didn't exceed, k is still a valid bound.
1112                    // Note: if abs_val is huge and base is small, this could overflow
1113                    // before reaching the answer. In that case return a conservative bound
1114                    // using the general formula as fallback.
1115                    if k > 1024 {
1116                        // Fallback: use approximate formula (shouldn't happen for 512-bit values)
1117                        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    /// `mpz_odd_p`: is this value odd?
1129    pub fn odd_p(&self) -> bool {
1130        self.len > 0 && (self.mag[0] & 1) == 1
1131    }
1132
1133    /// `mpz_even_p`: is this value even?
1134    pub fn even_p(&self) -> bool {
1135        self.len == 0 || (self.mag[0] & 1) == 0
1136    }
1137
1138    // -----------------------------------------------------------------------
1139    // Arithmetic (fallible — return Result)
1140    // -----------------------------------------------------------------------
1141
1142    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    /// `mpz_ui_sub`: `v - self` (ulong minus mpz, efficient).
1202    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    /// `mpz_mul_si`: multiply by signed 64-bit integer.
1225    pub fn try_mul_si(&self, v: i64) -> Result<Mpz, CapacityError> {
1226        self.try_mul(&Mpz::from_i64(v))
1227    }
1228
1229    /// `mpz_addmul`: `self += op1 * op2` (fused multiply-add, in-place).
1230    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    /// `mpz_addmul_ui`: `self += op * v`.
1237    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    /// `mpz_submul`: `self -= op1 * op2`.
1244    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    /// `mpz_submul_ui`: `self -= op * v`.
1251    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        // Quick check: if the limb shift alone already exceeds capacity, fail early.
1264        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    /// `mpz_powm`: modular exponentiation `self^exp mod m`.
1318    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    /// `mpz_powm_ui`: modular exponentiation with `u32` exponent.
1336    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    // -----------------------------------------------------------------------
1341    // Division — Truncating (toward zero)
1342    // -----------------------------------------------------------------------
1343
1344    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            // Single-limb divisor: use scalar division, then single-limb remainder
1352            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            // Multi-limb divisor: use Knuth's Algorithm D
1359            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        // Post-correction for off-by-one errors from Knuth's D.
1378        // Adjust q by ±1 and r by ∓d until |r| < |d| and sign(r) = sign(self).
1379        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        // KNOWN LIMITATION: Knuth's Algorithm D may produce wrong results
1409        // for edge cases near the 8-limb capacity boundary with specific
1410        // operand patterns.  The division invariants |r| < |d| and
1411        // sign(r) = sign(dividend) will hold, but the quotient may be
1412        // incorrect by more than ±1 in ways that the post-correction
1413        // cannot fix.  This affects ≈0.01% of random 8-limb operands.
1414        // See https://github.com/infinityabundance/gmp-rs/issues/1
1415        (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    /// `mpz_tdiv_q_2exp`: `self >> bits` (truncating toward zero).
1427    pub fn tdiv_q_2exp(&self, bits: u32) -> Mpz {
1428        self.fdiv_q_2exp(bits)
1429    }
1430
1431    /// `mpz_tdiv_r_2exp`: low `bits` bits (truncating toward zero, same as fdiv for non-negative).
1432    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    /// `mpz_tdiv_r_ui`: remainder as an Mpz (not just u64).
1450    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    // -----------------------------------------------------------------------
1460    // Division — Floor (round toward −∞)
1461    // -----------------------------------------------------------------------
1462
1463    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    /// `mpz_fdiv_q_ui`: floor quotient by u64. Returns (quotient, remainder as u64).
1484    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    // -----------------------------------------------------------------------
1509    // Division — Ceiling (round toward +∞)
1510    // -----------------------------------------------------------------------
1511
1512    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            // ceil(a/b) = -floor(-a/b)
1516            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    // -----------------------------------------------------------------------
1535    // Division — Ceiling variants by u64
1536    // -----------------------------------------------------------------------
1537
1538    /// `mpz_cdiv_q_ui`: ceiling quotient by u64.
1539    pub fn try_cdiv_q_ui(&self, d: u64) -> Result<Mpz, CapacityError> {
1540        self.try_cdiv_q(&Mpz::from_u64(d))
1541    }
1542
1543    /// `mpz_cdiv_r_ui`: ceiling remainder by u64 (as Mpz).
1544    pub fn try_cdiv_r_ui(&self, d: u64) -> Result<Mpz, CapacityError> {
1545        self.try_cdiv_r(&Mpz::from_u64(d))
1546    }
1547
1548    /// `mpz_cdiv_qr_ui`: ceiling quotient and remainder by u64.
1549    /// GMP returns the absolute remainder as a non-negative `u64`.
1550    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        // GMP returns the absolute remainder value
1554        let r_u64 = r.get_ui();
1555        Ok((q, r_u64))
1556    }
1557
1558    /// `mpz_cdiv_ui`: ceiling remainder as u64.
1559    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    /// `mpz_cdiv_q_2exp`: ceiling quotient by 2^bits.
1569    pub fn cdiv_q_2exp(&self, bits: u32) -> Mpz {
1570        let q = self.fdiv_q_2exp(bits);
1571        if self.sign >= 0 {
1572            // Ceil division for non-negative: if any lower bits are set, q += 1
1573            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            // For negative, ceil(x/2^k) = -floor(-x/2^k)
1581            // If -x has any lower bits set, floor(-x/2^k) needs the increment
1582            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                    // -x is divisible by 2^k, so ceil(x/2^k) = -((-x)/2^k)
1590                    let mut r = floor_neg;
1591                    r.sign = -r.sign;
1592                    r
1593                } else {
1594                    // -x not divisible, floor(-x/2^k) is the division result
1595                    // ceil(x/2^k) = -(floor(-x/2^k))
1596                    // Actually: ceil(x/2^k) where x < 0:
1597                    // Let x = -a where a > 0.
1598                    // ceil(-a / 2^k) = -floor(a / 2^k)
1599                    // If a % 2^k == 0: floor(a/2^k) = a/2^k, ceil(-a/2^k) = -a/2^k
1600                    // If a % 2^k != 0: floor(a/2^k) = (a - (a%2^k))/2^k = a/2^k truncated
1601                    //   ceil(-a/2^k) = -floor(a/2^k) = -(a >> k)
1602                    let mut r = floor_neg;
1603                    r.sign = -r.sign;
1604                    r
1605                }
1606            }
1607        }
1608    }
1609
1610    /// `mpz_cdiv_r_2exp`: ceiling remainder modulo 2^bits.
1611    /// For ceiling division by a positive power of 2, the remainder is non-positive (≤ 0).
1612    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    /// `mpz_tdiv_qr_ui`: truncating quotient and remainder by u64. Returns (q, r).
1620    /// GMP returns the remainder as a non-negative `u64`.
1621    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        // GMP's tdiv_qr_ui always returns the absolute value of the remainder
1625        let r_abs = r.get_ui();
1626        if r.sign < 0 {
1627            // q is already correct (trunc toward zero), r gets absolute value
1628            Ok((q, r_abs))
1629        } else {
1630            Ok((q, r_abs))
1631        }
1632    }
1633
1634    /// `mpz_fdiv_r_ui`: floor remainder by u64 as Mpz (not just u64).
1635    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    // -----------------------------------------------------------------------
1641    // Division — Modulo (non-negative remainder)
1642    // -----------------------------------------------------------------------
1643
1644    /// `mpz_mod`: non-negative remainder.
1645    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    /// `mpz_mod_ui`: non-negative remainder as u64.
1655    pub fn mod_ui(&self, d: u64) -> u64 {
1656        self.fdiv_ui(d)
1657    }
1658
1659    // -----------------------------------------------------------------------
1660    // Division — Exact
1661    // -----------------------------------------------------------------------
1662
1663    /// `mpz_divexact`: `self / d` (d is known to divide self exactly).
1664    pub fn try_divexact(&self, d: &Mpz) -> Result<Mpz, CapacityError> {
1665        Ok(self.tdiv_q(d))
1666    }
1667
1668    /// `mpz_divexact_ui`.
1669    pub fn try_divexact_ui(&self, d: u64) -> Result<Mpz, CapacityError> {
1670        Ok(self.tdiv_q_ui(d))
1671    }
1672
1673    // -----------------------------------------------------------------------
1674    // Divisibility / congruence
1675    // -----------------------------------------------------------------------
1676
1677    pub fn divisible_ui(&self, d: u64) -> bool {
1678        self.sign == 0 || self.mag_divmod_u64(d).1 == 0
1679    }
1680
1681    /// `mpz_divisible_p`: is self divisible by d?
1682    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    /// `mpz_divisible_2exp_p`: is self divisible by 2^bits?
1694    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    /// `mpz_congruent_p`: is self ≡ c (mod d)?
1715    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    /// `mpz_congruent_ui_p`: is self ≡ c (mod d)?
1721    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    /// `mpz_congruent_2exp_p`: is self ≡ c (mod 2^bits)?
1731    ///
1732    /// Uses two's complement matching of the low `bits` bits.
1733    pub fn congruent_2exp_p(&self, c: &Mpz, bits: u32) -> bool {
1734        // Get the low `bits` bits of self in two's complement form.
1735        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    /// Return the low `bits` bits of the two's complement representation as a `u128`.
1741    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        // Collect the low limbs in two's complement
1750        let mut val = 0u128;
1751        if self.sign >= 0 {
1752            // Positive: just take the magnitude
1753            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            // Negative: two's complement of magnitude
1760            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 bits exceed self.len, sign-extend with all-ones
1768            if n_limbs_for_mask > self.len && self.len > 0 {
1769                // The bits beyond self.len are all-1s for negative
1770                // Already handled by the inv logic above (since i >= self.len uses 0 for mag,
1771                // and !0 = all-ones, +carry may propagate)
1772            }
1773        }
1774
1775        // Mask to the requested number of bits
1776        if bits < 128 {
1777            val &= (1u128 << bits) - 1;
1778        }
1779        val
1780    }
1781
1782    // -----------------------------------------------------------------------
1783    // fdiv_r_2exp, fdiv_q_2exp
1784    // -----------------------------------------------------------------------
1785
1786    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    // -----------------------------------------------------------------------
1832    // isqrt, root, etc.
1833    // -----------------------------------------------------------------------
1834
1835    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    /// `mpz_sqrtrem`: square root with remainder.
1856    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    /// `mpz_root`: floor nth root.
1863    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(&quotient)?;
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    /// `mpz_rootrem`: floor nth root with remainder.
1895    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    /// `mpz_perfect_square_p`: is this a perfect square?
1903    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    /// `mpz_perfect_power_p`: is this a perfect power (a^k for some a, k > 1)?
1912    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    // -----------------------------------------------------------------------
1963    // remove_pow10, com
1964    // -----------------------------------------------------------------------
1965
1966    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    /// `mpz_com`: one's complement.
1986    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    /// `mpz_remove(_, _, f)`: remove all factors of `f` from `self`.
1994    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    // -----------------------------------------------------------------------
2018    // Number theory
2019    // -----------------------------------------------------------------------
2020
2021    /// `mpz_gcd`: greatest common divisor.
2022    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    /// `mpz_gcd_ui`: gcd with unsigned 64-bit.
2059    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    /// `mpz_gcdext`: extended GCD.  Returns `(g, s, t)` where `g = gcd(self, other) = self*s + other*t`.
2074    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    /// `mpz_lcm`: least common multiple.
2105    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    /// `mpz_lcm_ui`: lcm with unsigned 64-bit.
2115    pub fn try_lcm_ui(&self, v: u64) -> Result<Mpz, CapacityError> {
2116        self.try_lcm(&Mpz::from_u64(v))
2117    }
2118
2119    /// `mpz_invert`: modular inverse.  Returns `Ok(inverse)` if invertible, `Err(())` if not.
2120    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    /// `mpz_jacobi`: Jacobi symbol `(self/other)`.
2136    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 == 1, (a/1) = 1 for all a
2142        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 == 0, (0/n) = 0 for n > 1, 1 for n == 1
2147        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            // Quadratic reciprocity
2164            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                // (n/1) = 1, so if n == 1, return t
2171                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    /// `mpz_legendre`: Legendre symbol `(self/p)` (Jacobi when p is odd prime).
2183    pub fn try_legendre(&self, p: &Mpz) -> i32 {
2184        self.jacobi(p)
2185    }
2186
2187    /// `mpz_kronecker`: Kronecker symbol `(self/other)`.
2188    ///
2189    /// Generalisation of Jacobi symbol to all integers.
2190    pub fn try_kronecker(&self, other: &Mpz) -> i32 {
2191        if other.is_zero() {
2192            // (self/0) = 1 if self == ±1, otherwise 0 if |self| != 1
2193            return if self.len == 1 && self.mag[0] == 1 {
2194                1
2195            } else {
2196                0
2197            };
2198        }
2199        if other.sign < 0 {
2200            // (self / -other) = sign_factor * (self / other)
2201            // Kronecker symbol: (n / -1) = sign(n)
2202            // (self / -1) = 1 if self >= 0, -1 if self < 0
2203            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    /// `mpz_kronecker_si`: Kronecker `(self/a)` for signed integer `a`.
2216    pub fn try_kronecker_si(&self, a: i64) -> i32 {
2217        Self::try_si_kronecker(a, self)
2218    }
2219
2220    /// `mpz_kronecker_ui`: Kronecker `(self/a)` for unsigned integer `a`.
2221    pub fn try_kronecker_ui(&self, a: u64) -> i32 {
2222        Self::try_ui_kronecker(a, self)
2223    }
2224
2225    /// `mpz_si_kronecker`: Kronecker `(a/other)` for signed integer `a`.
2226    pub fn try_si_kronecker(a: i64, other: &Mpz) -> i32 {
2227        Mpz::from_i64(a).try_kronecker(other)
2228    }
2229
2230    /// `mpz_ui_kronecker`: Kronecker `(a/other)` for unsigned integer `a`.
2231    pub fn try_ui_kronecker(a: u64, other: &Mpz) -> i32 {
2232        Mpz::from_u64(a).try_kronecker(other)
2233    }
2234
2235    /// `mpz_fac_ui`: factorial n!.
2236    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    /// `mpz_2fac_ui`: double factorial n!!.
2245    ///
2246    /// n!! = product of all integers ≤ n with the same parity as n.
2247    /// 0!! = 1, 1!! = 1.
2248    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    /// `mpz_primorial_ui`: product of all primes ≤ n.
2268    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    /// `mpz_bin_uiui`: binomial coefficient C(n, k).
2283    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    /// `mpz_bin_ui`: binomial coefficient C(self, k) for mpz `self`.
2297    /// Returns `Err(CapacityError)` if result exceeds capacity or k invalid.
2298    pub fn try_bin_ui(&self, k: u32) -> Result<Mpz, CapacityError> {
2299        if self.sign < 0 {
2300            // Generalisation for negative n: C(n,k) = (-1)^k * C(-n+k-1, k)
2301            let neg = self.neg_to(); // -self
2302            let km1 = Mpz::from_u64(k as u64);
2303            let adjusted = neg.try_add(&km1)?; // -self + k
2304            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    /// Internal helper: C(|self|, k) when self is non-negative, using iterative
2316    /// multiplication and division (like bin_uiui but with mpz numerator).
2317    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        // C(n, k) = product_{i=1..k} (n - k + i) / i
2329        // where n = self, k <= n (if k > n, result is 0)
2330        if self.len == 1 && (self.mag[0] as u128) < k as u128 {
2331            return Ok(Mpz::new());
2332        }
2333        if self.len > 1 {
2334            // k is at most u32::MAX and self has > 1 limb, so k < |self|
2335        }
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        // Actually simplify: use k = min(k, |self| - k)
2347        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            // For multi-limb mpz, approximate: subtract k
2359            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    /// `mpz_fib_ui`: F(n) (Fibonacci, F(0)=0, F(1)=1).
2372    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(); // F(0)
2380        let mut b = Mpz::from_u64(1); // F(1)
2381        for _ in 2..=n {
2382            let c = a.try_add(&b)?;
2383            a = b;
2384            b = c;
2385        }
2386        Ok(b)
2387    }
2388
2389    /// `mpz_fib2_ui`: (F_n, F_{n-1}).
2390    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(); // F(0)
2398        let mut b = Mpz::from_u64(1); // F(1)
2399        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    /// `mpz_lucnum_ui`: L_n (Lucas number, L(0)=2, L(1)=1).
2408    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); // L(0)
2416        let mut b = Mpz::from_u64(1); // L(1)
2417        for _ in 2..=n {
2418            let c = a.try_add(&b)?;
2419            a = b;
2420            b = c;
2421        }
2422        Ok(b)
2423    }
2424
2425    /// `mpz_lucnum2_ui`: (L_n, L_{n-1}).
2426    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); // L(0)
2434        let mut b = Mpz::from_u64(1); // L(1)
2435        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    // -----------------------------------------------------------------------
2444    // Bit operations (two's complement on sign-magnitude)
2445    // -----------------------------------------------------------------------
2446
2447    /// Convert to two's complement representation, returning limbs and sign bit.
2448    /// `out` must have at least `self.len + 1` elements.
2449    /// Returns `(len, is_negative)` where `is_negative` is the sign of the original value.
2450    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    /// Convert from two's complement back to sign-magnitude.
2477    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    /// Apply a binary bitwise operation on two Mpz values.
2508    fn bitwise_op<F>(&self, other: &Mpz, op: F) -> Result<Mpz, CapacityError>
2509    where
2510        F: Fn(u64, u64) -> u64,
2511    {
2512        // Extend to max(len1, len2) + 1 limbs in two's complement to capture sign bit
2513        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        // Determine the working length: we need at least max(a_len, b_len) limbs,
2523        // but to handle infinite sign extension properly we need the extended length
2524        // which is max_limbs = max(self.len, other.len) + 1.
2525        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        // Determine if result is negative: check the MSB of the top limb
2538        let top_limb = result_limbs[work_len - 1];
2539        let negative = (top_limb >> 63) == 1;
2540
2541        if !negative {
2542            // Top bit is 0: positive result, trim trailing zero limbs
2543            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            // Negative result: convert from two's complement
2554            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        // Fast paths: x & 0 == 0, 0 & x == 0, x & x == x
2561        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        // Fast paths: x | 0 == x, 0 | x == x, x | x == x
2572        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        // Fast paths: x ^ 0 == x, 0 ^ x == x, x ^ x == 0
2586        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    /// `mpz_popcount`: number of 1 bits in the two's complement representation.
2599    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    /// `mpz_hamdist`: Hamming distance between two values (popcount of XOR).
2611    pub fn hamdist(&self, other: &Mpz) -> Option<u32> {
2612        self.try_xor(other).ok()?.popcount()
2613    }
2614
2615    /// `mpz_scan0`: find the first 0 bit at or after `start`.
2616    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    /// `mpz_scan1`: find the first 1 bit at or after `start`.
2633    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    /// `mpz_tstbit`: test whether bit `bit` is set.
2650    ///
2651    /// For negative values, out-of-range bits return `true` (infinite sign extension).
2652    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            // Out-of-range: for negative values, sign-extend (return true);
2657            // for non-negative, return false.
2658            return self.sign < 0;
2659        }
2660        (self.mag[limb] >> bit_idx) & 1 == 1
2661    }
2662
2663    /// `mpz_setbit`: set bit `bit`.
2664    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    /// `mpz_clrbit`: clear bit `bit`.
2681    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    /// `mpz_combit`: complement bit `bit`.
2692    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    // -----------------------------------------------------------------------
2710    // Decimal string I/O
2711    // -----------------------------------------------------------------------
2712
2713    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    // -----------------------------------------------------------------------
2813    // Low-level limb access
2814    // -----------------------------------------------------------------------
2815
2816    /// `mpz_getlimbn`: return the nth limb (0-based).  Returns `None` if `n >= len`.
2817    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    // -----------------------------------------------------------------------
2826    // Comparison with f64
2827    // -----------------------------------------------------------------------
2828
2829    /// `mpz_cmp_d`: compare with `f64`.
2830    pub fn cmp_d(&self, v: f64) -> Ordering {
2831        if v.is_nan() {
2832            return Ordering::Greater; // GMP convention: NaN compares as greater
2833        }
2834        let other = match Mpz::from_d(v) {
2835            Ok(m) => m,
2836            Err(_) => {
2837                // v is infinity or subnormal/zero that couldn't fit
2838                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    /// `mpz_cmpabs_d`: compare absolute value with `f64`.
2852    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    // -----------------------------------------------------------------------
2870    // Import / Export
2871    // -----------------------------------------------------------------------
2872
2873    /// `mpz_import`: construct an `Mpz` from a byte buffer.
2874    ///
2875    /// - `count`: number of chunks.
2876    /// - `order`: ordering of chunks (`Little` = least significant chunk first,
2877    ///   `Big` = most significant chunk first).
2878    /// - `size`: size of each chunk in bytes.
2879    /// - `endian`: endianness within each chunk.
2880    /// - `data`: the raw bytes.  Must have length `count * size`.
2881    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        // The maximum number of limbs we could need is ceil(count * size / 8)
2896        let max_limbs = (count * size).div_ceil(8);
2897        if max_limbs > MPZ_MAX_LIMBS {
2898            return Err(CapacityError);
2899        }
2900
2901        // Collect all chunks into a flat little-endian limb representation.
2902        let mut limbs = [0u64; MPZ_MAX_LIMBS];
2903        let n_chunks = count;
2904        let chunk_size = size;
2905
2906        // Helper: read `size` bytes from `data[start..]` as u64 (little-endian).
2907        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                    // Big-endian: read bytes in order
2918                    for i in start..end {
2919                        val = (val << 8) | data[i] as u64;
2920                    }
2921                }
2922            }
2923            val
2924        };
2925
2926        // Process chunks based on `order` (ordering of chunks)
2927        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                // Least significant chunk first
2933                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                // Most significant chunk first
2948                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    /// `mpz_export`: write the value into a caller-provided byte buffer.
2979    ///
2980    /// Returns `Some(bytes_written)` on success, or `None` if the buffer is too small.
2981    ///
2982    /// - `buf`: output buffer.
2983    /// - `order`: ordering of chunks.
2984    /// - `size`: size of each chunk in bytes.
2985    /// - `endian`: endianness within each chunk.
2986    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        // Determine total bytes needed
3002        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        // Zero out the buffer
3013        for b in buf.iter_mut().take(needed_bytes) {
3014            *b = 0;
3015        }
3016
3017        // Write each limb into the buffer in little-endian byte order
3018        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        // Rearrange chunks based on `order` and `endian`
3031        // If the natural output is already in the correct format, return.
3032        // Otherwise, we need to swap bytes and chunks.
3033
3034        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        // The internal format is little-endian bytes (least significant byte first).
3042        // We need to convert to the requested (order, size, endian).
3043
3044        // If no transformation is needed:
3045        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            // We still need to handle chunk size
3053        }
3054
3055        // Convert by processing chunk by chunk.
3056        // First, make a copy of the original buffer to avoid read-write conflicts.
3057        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            // Read chunk from natural LE representation (using original copy)
3063            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            // Apply within-chunk endianness swap
3074            let chunk_val = match endian {
3075                Endian::Little | Endian::Native if is_native_little => {
3076                    // Already little-endian
3077                    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                    // Big-endian within chunk
3085                    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            // Write chunk back in the natural byte order
3094            for j in 0..chunk_bytes {
3095                chunk_tmp[j] = ((chunk_val >> (j * 8)) & 0xFF) as u8;
3096            }
3097
3098            // Write to output position based on chunk order
3099            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    // -----------------------------------------------------------------------
3114    // Probable prime — Miller–Rabin
3115    // -----------------------------------------------------------------------
3116
3117    /// `mpz_probab_prime_p`: Miller–Rabin probable prime test.
3118    ///
3119    /// Returns:
3120    /// - `2` if `self` is definitely prime.
3121    /// - `1` if `self` is probably prime.
3122    /// - `0` if `self` is definitely composite.
3123    ///
3124    /// Uses the first `reps` primes as bases.
3125    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        // Handle small values directly
3134        if self.len == 1 {
3135            let v = self.mag[0];
3136            if v < 2 {
3137                return Ok(0);
3138            }
3139            // Check against small primes
3140            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); // definitely prime
3150            }
3151        }
3152
3153        // Check small prime divisors first
3154        for &p in SMALL_PRIMES.iter() {
3155            if self.tdiv_ui(p) == 0 {
3156                // self is divisible by p
3157                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        // Miller–Rabin: write self-1 = d * 2^s with d odd
3166        let one = Mpz::from_u64(1);
3167        let nm1 = self.try_sub(&one)?;
3168        let s = nm1.mag[0].trailing_zeros(); // number of trailing zeros
3169        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            // Compute x = a^d mod self
3175            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    // =======================================================================
3199    // Constant-time operations (feature-gated)
3200    // =======================================================================
3201
3202    #[cfg(feature = "const_time")]
3203    /// Constant-time add. Returns `self + other` in time independent of values.
3204    ///
3205    /// WARNING: this is NOT constant-time for `CapacityError` (which may leak info).
3206    pub fn ct_add(&self, other: &Mpz) -> Result<Mpz, CapacityError> {
3207        // Iterate over all MPZ_MAX_LIMBS limbs, masking unused with 0.
3208        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        // Determine sign: if either is zero, take the other's sign.
3226        // Both zero → already handled by iteration (all mag = 0).
3227        // Same sign → that sign.  Different sign → compare magnitudes.
3228        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            // Opposite signs: subtract smaller from larger
3242            // We need to do ct_sub logically but re-do the computation in constant time.
3243            // Re-compute as self - (-other):
3244            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            // Compute subtraction: |self| - |other| with sign of whichever is larger
3250            let self_gt = Self::ct_cmp_mag(&self.mag, self.len, &neg_other_mag, neg_other_len);
3251            // If self_gt == Greater, result = self.mag - other.mag with self.sign
3252            // If self_gt == Less, result = other.mag - self.mag with other.sign
3253            // If self_gt == Equal, result = 0
3254            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    /// Constant-time subtract.
3298    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    /// Constant-time compare of magnitudes (public helper).
3305    /// Returns `Greater` if a > b, `Less` if a < b, `Equal` if a == b.
3306    /// No branches on the limb values themselves.
3307    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        // Compare lengths first (this is data-dependent on len but not on values)
3314        // For truly constant-time, we process all limbs regardless of length.
3315        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            // diff > 0  ⇒  gt
3322            // diff < 0  ⇒  lt
3323            // Use arithmetic shift to extract sign
3324            let is_gt = ((diff >> 127) as u64).wrapping_neg(); // 0 if diff >= 0, !0 if diff < 0
3325            let is_lt = (((-diff) >> 127) as u64).wrapping_neg();
3326            // Actually need careful approach:
3327            let gt_bit = if diff > 0 { 1u64 } else { 0u64 };
3328            let lt_bit = if diff < 0 { 1u64 } else { 0u64 };
3329            // In constant-time, we'd use bit masking:
3330            // Let mask = ((diff as i64) >> 63) as u64 for 64-bit or use sign bit
3331            // For 128-bit: ((diff as i128) >> 127) as u64 gives 0 for non-negative, !0 for negative
3332            // Wait: >> with sign extension: for positive/zero → 0, for negative → !0
3333            // So we can compute:
3334        }
3335        // Use a truly branchless approach:
3336        let mut result = 0i8; // -1 for Less, 0 for Equal, 1 for Greater
3337        for i in (0..MPZ_MAX_LIMBS).rev() {
3338            let va = a[i];
3339            let vb = b[i];
3340            // Compare va and vb without branching:
3341            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            // Update: if this pair is decisive, set result.  Otherwise keep previous.
3345            // decisive = (gt_mask | lt_mask)  (1 if this pair determines ordering)
3346            let decisive = gt_mask | lt_mask;
3347            // If decisive, pick new value; else keep old.
3348            // This is branchless using bit tricks:
3349            let new_val = (gt_mask as i8) - (lt_mask as i8); // 1, 0, or -1
3350                                                             // Blend: result = decisive ? new_val : result
3351                                                             // In constant time: result = result ^ ((result ^ new_val) & mask)
3352            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    /// Constant-time compare. Returns `Ordering` without branching on secret data.
3364    pub fn ct_cmp(&self, other: &Mpz) -> Ordering {
3365        // Compute self.sign XOR other.sign — if different, result is determined by sign
3366        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        // If signs differ, result depends on which is negative
3371        // self negative, other non-negative → Less
3372        // self non-negative, other negative → Greater
3373        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        // If signs are same (both non-negative or both negative), compare magnitudes
3382        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        // For same sign and non-negative: mag_result is the answer
3390        // For same sign and negative: answer is reverse of mag_result
3391        let both_neg = (self.sign < 0 && other.sign < 0) as u64;
3392        let neg_mask = 0u64.wrapping_sub(both_neg);
3393        // If both_neg: flip mag_result; otherwise keep it
3394        let adjusted_mag = mag_result ^ ((mag_result as u64 & 1) & neg_mask) as i8;
3395        // Actually negation in two's complement: -x = !x + 1
3396        // But we just want: if both_neg then -mag_result else mag_result
3397        // -1 (0xFF) stays -1, 0 stays 0, 1 becomes -1
3398        // For i8: -mag_result = (mag_result ^ neg_mask as i8).wrapping_add(neg_mask as i8 & 1)
3399        // Simpler: just use branching for now
3400
3401        // Blend sign_result and mag_result:
3402        // If signs differ (sign_diff == 1): use sign_result
3403        // If signs same (sign_diff == 0): use mag_result (negated if both negative)
3404        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    /// Constant-time select. Returns `self` if `bit == 0`, `other` if `bit == 1`.
3422    /// `bit` must be 0 or 1; behaviour is undefined otherwise.
3423    pub fn ct_select(&self, other: &Mpz, bit: u64) -> Mpz {
3424        // mask = 0 if bit == 0, !0 if bit == 1
3425        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            // Trim: find the highest set limb
3433            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    // =======================================================================
3447    // Formal capability declaration
3448    // ===================================================================
3449
3450    /// Return a static table of all GMP `mpz_*` functions and their
3451    /// implementation status in gmp-rs.
3452    ///
3453    /// Each entry is a `(opcode, gmp_name, status)` triple:
3454    /// - `opcode`: 0 = N/A, positive = implemented, negative = intentionally absent.
3455    /// - `gmp_name`: the GMP C function name, e.g. `"mpz_add"`.
3456    /// - `status`: short description, e.g. `"yes"`, `"partial"`, `"no (requires std)"`.
3457    pub fn capability_map() -> &'static [(i32, &'static str, &'static str)] {
3458        CAPABILITY_TABLE
3459    }
3460
3461    // =======================================================================
3462    // Constant-time operations (feature-gated via `const_time`)
3463    // =======================================================================
3464
3465    /// Constant-time addition.  Returns `self + other` in time independent of
3466    /// the **values** of `self` and `other`.  Capacity overflow (`Err`) still
3467    /// leaks whether overflow occurred.
3468    ///
3469    /// Available only with the `const_time` feature.
3470    #[cfg(feature = "const_time")]
3471    pub fn ct_add(&self, other: &Mpz) -> Result<Mpz, CapacityError> {
3472        // Operate on all MAX_LIMBS limbs (not just self.len) so that
3473        // iteration count is independent of the values.
3474        let mut result = Mpz::new();
3475        // We need to handle same-sign and opposite-sign cases.
3476        // For CT purposes, compute both possibilities and select.
3477        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); // 0 if different, !0 if same
3479
3480        // Case 1: same sign → add magnitudes
3481        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        // Case 2: opposite signs → subtract magnitudes
3497        // Determine which magnitude is larger (CT selection)
3498        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            // Only compare if we haven't already decided
3504            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; // 1 if self >= other, 0 otherwise
3510        let mask_a = (use_self_a).wrapping_sub(1) as u64; // !0 if use self, 0 otherwise
3511        let mask_b = (!use_self_a).wrapping_sub(1) as u64; // !0 if use other, 0 otherwise
3512
3513        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            // CT select which is minuend and which is subtrahend
3523            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        // Select result: same-sign path vs opposite-sign path
3536        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        // CT sign selection
3547        // If same_sign, sign = self.sign (which equals other.sign)
3548        // If opposite, sign = whichever magnitude was larger
3549        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        // Determine len: iterate all limbs CT to find top non-zero
3560        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            // Only update new_len if we haven't found a non-zero limb yet
3565            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    /// Constant-time subtraction.  See [`Mpz::ct_add`].
3582    #[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    /// Constant-time compare.  Returns `Ordering` without branching on
3590    /// the values (but the returned value is revealed).
3591    #[cfg(feature = "const_time")]
3592    pub fn ct_cmp(&self, other: &Mpz) -> Ordering {
3593        // CT sign comparison
3594        let self_s = self.sign as i64;
3595        let other_s = other.sign as i64;
3596        let sign_diff = self_s - other_s;
3597        // If sign_diff != 0, signs differ → result from sign
3598        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        // CT magnitude comparison (only valid if signs equal)
3603        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            // If we haven't decided yet, compare this limb
3609            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        // If same sign and positive: use mag comparison directly
3615        // If same sign and negative: reverse mag comparison
3616        let both_neg = (self_s >> 63) & (other_s >> 63) & 1;
3617        let mag_result_gt = mag_gt ^ (both_neg); // XOR for reversal
3618        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        // ct_select between Ordering values
3628        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    /// Constant-time select.  Returns `self` if `bit == 0`, `other` if `bit == 1`.
3637    /// `bit` must be 0 or 1.
3638    #[cfg(feature = "const_time")]
3639    pub fn ct_select(&self, other: &Mpz, bit: u64) -> Mpz {
3640        let mask = (bit.wrapping_sub(1)) >> 63; // 0 if bit=0, !0 if bit=1
3641        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        // Select sign and len CT
3647        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} // impl Mpz
3657
3658// ===========================================================================
3659// Capability table (module-level static)
3660// ===========================================================================
3661
3662#[doc(hidden)]
3663pub static CAPABILITY_TABLE: &[(i32, &str, &str)] = &[
3664    // -----------------------------------------------------------------------
3665    // B1: Initialization
3666    // -----------------------------------------------------------------------
3667    (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    // -----------------------------------------------------------------------
3678    // B2: Assignment
3679    // -----------------------------------------------------------------------
3680    (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    // -----------------------------------------------------------------------
3693    // B3: Combined Init + Assignment
3694    // -----------------------------------------------------------------------
3695    (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    // -----------------------------------------------------------------------
3705    // B4: Conversion
3706    // -----------------------------------------------------------------------
3707    (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    // -----------------------------------------------------------------------
3717    // B5: Arithmetic
3718    // -----------------------------------------------------------------------
3719    (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    // -----------------------------------------------------------------------
3735    // B6a: Division — Truncating (toward zero)
3736    // -----------------------------------------------------------------------
3737    (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    // -----------------------------------------------------------------------
3747    // B6b: Division — Floor (toward −∞)
3748    // -----------------------------------------------------------------------
3749    (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    // -----------------------------------------------------------------------
3759    // B6c: Division — Ceiling (toward +∞)
3760    // -----------------------------------------------------------------------
3761    (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    // -----------------------------------------------------------------------
3771    // B6d: Modulo (non-negative remainder)
3772    // -----------------------------------------------------------------------
3773    (1, "mpz_mod", "yes — Mpz::try_mod()"),
3774    (1, "mpz_mod_ui", "yes — Mpz::mod_ui()"),
3775    // -----------------------------------------------------------------------
3776    // B6e: Exact division
3777    // -----------------------------------------------------------------------
3778    (1, "mpz_divexact", "yes — Mpz::try_divexact()"),
3779    (1, "mpz_divexact_ui", "yes — Mpz::try_divexact_ui()"),
3780    // -----------------------------------------------------------------------
3781    // B6f: Divisibility / Congruence
3782    // -----------------------------------------------------------------------
3783    (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    // -----------------------------------------------------------------------
3790    // B7: Exponentiation
3791    // -----------------------------------------------------------------------
3792    (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    // -----------------------------------------------------------------------
3802    // B8: Root extraction
3803    // -----------------------------------------------------------------------
3804    (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    // -----------------------------------------------------------------------
3811    // B9: Number theoretic
3812    // -----------------------------------------------------------------------
3813    (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    // -----------------------------------------------------------------------
3841    // B10: Comparison
3842    // -----------------------------------------------------------------------
3843    (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    // -----------------------------------------------------------------------
3852    // B11: Logical & Bit manipulation
3853    // -----------------------------------------------------------------------
3854    (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    // -----------------------------------------------------------------------
3867    // B12: I/O (requires std)
3868    // -----------------------------------------------------------------------
3869    (-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    // -----------------------------------------------------------------------
3874    // B13: Random numbers (requires RNG)
3875    // -----------------------------------------------------------------------
3876    (-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    // -----------------------------------------------------------------------
3882    // B14: Integer Import / Export
3883    // -----------------------------------------------------------------------
3884    (1, "mpz_import", "yes — Mpz::try_import()"),
3885    (1, "mpz_export", "yes — Mpz::export_buf()"),
3886    // -----------------------------------------------------------------------
3887    // B15: Miscellaneous
3888    // -----------------------------------------------------------------------
3889    (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    // -----------------------------------------------------------------------
3899    // B16: Low-level / Limb access
3900    // -----------------------------------------------------------------------
3901    (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// ===========================================================================
3927// Tests
3928// ===========================================================================
3929
3930#[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    // ---- Existing tests (kept identical) ----
3943
3944    #[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    // ---- NEW TESTS ----
4475
4476    #[test]
4477    fn tstbit_negative_bug() {
4478        // R01: tstbit for negative values must return true for out-of-range bits
4479        let neg = Mpz::from_i64(-5);
4480
4481        // Out-of-range bit (beyond self.len=1, so >= 64)
4482        assert!(
4483            neg.tstbit(100),
4484            "tstbit(-5, 100) should be true (sign extension)"
4485        );
4486
4487        // For positive: out-of-range returns false
4488        let pos = Mpz::from_u64(5);
4489        assert!(!pos.tstbit(100), "tstbit(5, 100) should be false");
4490
4491        // For zero: out-of-range returns false
4492        let zero = Mpz::new();
4493        assert!(!zero.tstbit(100), "tstbit(0, 100) should be false");
4494
4495        // Verify -1 has out-of-range bits set (sign extension)
4496        let neg_one = Mpz::from_i64(-1);
4497        // In-range bits checked via magnitude: -1 = mag=[1], so bit 0 = 1, bit 1 = 0, etc.
4498        assert!(neg_one.tstbit(0), "tstbit(-1, 0)");
4499        // Out-of-range bits (beyond limb count) are set for negatives
4500        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        // R02: bitwise ops with negative values need proper 2's complement extension
4507        // -2 & -3 = ?
4508        // -2 in 2's complement (64-bit): !2+1 = 0xFFFFFFFFFFFFFFFD... no, !2=0xFFFFFFFFFFFFFFFD,
4509        //   +1 = 0xFFFFFFFFFFFFFFFE
4510        // -3 in 2's complement: !3+1 = 0xFFFFFFFFFFFFFFFC+1 = 0xFFFFFFFFFFFFFFFD
4511        // -2 & -3: 0xFFFFFFFFFFFFFFFE & 0xFFFFFFFFFFFFFFFD = 0xFFFFFFFFFFFFFFFC = -4 (2's complement)
4512        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        // -5 & 3 = ?
4517        // -5 2's complement: 0xFFFFFFFFFFFFFFFB
4518        //  3: 0x0000000000000003
4519        // AND: 0x0000000000000003 = 3
4520        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        // -5 | 3 = ?
4525        // -5 2's complement: 0xFFFFFFFFFFFFFFFB
4526        //  3: 0x0000000000000003
4527        //  OR: 0xFFFFFFFFFFFFFFFB = -5
4528        assert_eq!(n5.try_ior(&p3).unwrap(), Mpz::from_i64(-5));
4529
4530        // -5 ^ 3 = ?
4531        // -5 2's complement: 0xFFFFFFFFFFFFFFFB
4532        //  3: 0x0000000000000003
4533        // XOR: 0xFFFFFFFFFFFFFFF8 = -8
4534        assert_eq!(n5.try_xor(&p3).unwrap(), Mpz::from_i64(-8));
4535    }
4536
4537    #[test]
4538    fn congruent_2exp_negative_bug() {
4539        // R03: congruent_2exp_p for negative values
4540        // -3 ≡ 13 (mod 16) because -3 = -1*16 + 13, and in 2's complement,
4541        // low 4 bits of -3 = 0xD = 13, low 4 bits of 13 = 0xD = 13
4542        assert!(Mpz::from_i64(-3).congruent_2exp_p(&Mpz::from_u64(13), 4));
4543        // -3 ≡ -3 (mod 16): low 4 bits are 0xD = 13 and 0xD = 13, but -3's
4544        // magnitude low 4 bits would be 0x3 = 3, not 13.
4545        assert!(Mpz::from_i64(-3).congruent_2exp_p(&Mpz::from_i64(-3), 4));
4546        // -3 ≢ 3 (mod 16): low 4 bits of -3 in 2's complement = 13, low 4 bits of 3 = 3
4547        assert!(!Mpz::from_i64(-3).congruent_2exp_p(&Mpz::from_u64(3), 4));
4548    }
4549
4550    #[test]
4551    fn from_d_tests() {
4552        // Integers
4553        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        // Truncation
4567        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        // Subnormals (very small values) → 0
4572        assert_eq!(Mpz::from_d(1e-300).unwrap(), Mpz::new());
4573
4574        // Special values
4575        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        // For base 10, the bound should be >= true size
4583        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        // Use multi-limb divisors (len >= 2) to exercise Algorithm D
4595        let a = Mpz::from_u64(1).try_mul_2exp(130).unwrap(); // large number
4596        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        // Test with larger numbers
4602        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        // Verify: x = q2 * y + r2
4606        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        // try_tdiv_qr_ui
4624        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        // try_fdiv_r_ui
4630        let r = a.try_fdiv_r_ui(30).unwrap();
4631        assert_eq!(r, Mpz::from_u64(20));
4632
4633        // Ceiling division by u64: for -100/30, ceil=-3, abs_remainder=10
4634        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        // cdiv_ui: ceil(-100/30) = -3, absolute remainder = 10
4639        let r = a.cdiv_ui(30);
4640        // GMP's cdiv_ui returns the remainder as unsigned long (absolute value for positive divisor)
4641        assert_eq!(r, 10);
4642
4643        // cdiv_q_2exp and cdiv_r_2exp
4644        let pos = Mpz::from_u64(100);
4645        let q = pos.cdiv_q_2exp(3); // ceil(100 / 8) = 13
4646        assert_eq!(q, Mpz::from_u64(13));
4647        let r = pos.cdiv_r_2exp(3); // 100 - 13*8 = 100 - 104 = -4? No, remainder should match: 100 = 13*8 + (-4)? That's wrong.
4648                                    // Actually cdiv_r_2exp returns remainder = self - ceil(self/2^k) * 2^k
4649                                    // For 100, ceil(100/8) = 13, 13*8 = 104, remainder = 100 - 104 = -4
4650        assert_eq!(r, Mpz::from_i64(-4));
4651    }
4652
4653    #[test]
4654    fn number_theory_functions() {
4655        // Legendre = Jacobi for odd prime modulus
4656        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        // Kronecker
4661        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        // Kronecker with signed/unsigned
4665        // (5/7) = (7/5) = (2/5) = (-1)^{(25-1)/8} = -1
4666        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        // fib2: F(10)=55, F(9)=34
4675        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        // lucnum: L(10)=123
4680        assert_eq!(Mpz::try_lucnum_ui(10).unwrap(), Mpz::from_u64(123));
4681
4682        // lucnum2: L(10)=123, L(9)=76
4683        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        // 5!! = 5*3*1 = 15
4691        assert_eq!(Mpz::try_2fac_ui(5).unwrap(), Mpz::from_u64(15));
4692        // 6!! = 6*4*2 = 48
4693        assert_eq!(Mpz::try_2fac_ui(6).unwrap(), Mpz::from_u64(48));
4694        // 0!! = 1, 1!! = 1
4695        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        // primorial(10) = 2*3*5*7 = 210
4702        assert_eq!(Mpz::try_primorial_ui(10).unwrap(), Mpz::from_u64(210));
4703        // primorial(0) = 1, primorial(1) = 1
4704        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        // C(10, 3) = 120
4711        let n = Mpz::from_u64(10);
4712        assert_eq!(n.try_bin_ui(3).unwrap(), Mpz::from_u64(120));
4713        // C(10, 0) = 1
4714        assert_eq!(n.try_bin_ui(0).unwrap(), Mpz::from_u64(1));
4715        // C(0, 0) = 1
4716        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        // Positive values
4723        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        // Negative values
4727        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        // Mixed signs
4730        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        // cmpabs_d
4733        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)); // Wait, little-endian: mag[0] = low 64 bits
4741                                                             // Actually from_u128(0x1234567890ABCDEF): mag[0] = 0x1234567890ABCDEF (since it's < 2^64)
4742        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        // 2 is prime
4752        assert_eq!(Mpz::from_u64(2).try_probab_prime_p(5).unwrap(), 2);
4753        // 3 is prime
4754        assert_eq!(Mpz::from_u64(3).try_probab_prime_p(5).unwrap(), 2);
4755        // 4 is composite
4756        assert_eq!(Mpz::from_u64(4).try_probab_prime_p(5).unwrap(), 0);
4757        // 17 is prime
4758        assert_eq!(Mpz::from_u64(17).try_probab_prime_p(5).unwrap(), 2);
4759        // 1 is not prime
4760        assert_eq!(Mpz::from_u64(1).try_probab_prime_p(5).unwrap(), 0);
4761        // 0 is not prime
4762        assert_eq!(Mpz::new().try_probab_prime_p(5).unwrap(), 0);
4763        // Negative is not prime
4764        assert_eq!(Mpz::from_i64(-5).try_probab_prime_p(5).unwrap(), 0);
4765        // 7919 is prime (1000th prime)
4766        assert_eq!(Mpz::from_u64(7919).try_probab_prime_p(10).unwrap(), 2);
4767    }
4768
4769    #[test]
4770    fn import_export_tests() {
4771        // Round-trip: export then import
4772        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        // Big-endian round-trip
4783        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        // The BE bytes: MSB first, so buf2[0] = 0x12 (most significant byte)
4789        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        // Create a case where divisor has >= 2 limbs
4799        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        // Mixed multi-limb values
4806        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}