feanor_math/rings/mpir/
mod.rs

1use std::fmt::Debug;
2use std::marker::PhantomData;
3
4use feanor_serde::newtype_struct::*;
5use libc;
6use serde::de::DeserializeSeed;
7use serde::ser::SerializeTuple;
8use serde::{Deserialize, Deserializer, Serialize, Serializer};
9
10use crate::algorithms::bigint_ops::deserialize_bigint_from_bytes;
11use crate::divisibility::*;
12use crate::homomorphism::*;
13use crate::integer::*;
14use crate::ordered::*;
15use crate::pid::*;
16use crate::primitive_int::*;
17use crate::ring::*;
18use crate::rings::rust_bigint::*;
19use crate::specialization::*;
20use crate::{
21    algorithms, impl_eval_poly_locally_for_ZZ, impl_interpolation_base_ring_char_zero, impl_poly_gcd_locally_for_ZZ,
22};
23
24mod mpir_bindings;
25
26/// An `mpir` integer.
27pub struct MPZEl {
28    integer: mpir_bindings::__mpz_struct,
29}
30
31impl MPZEl {
32    fn new() -> Self {
33        unsafe {
34            let mut result = mpir_bindings::UNINIT_MPZ;
35            mpir_bindings::__gmpz_init(&mut result as mpir_bindings::mpz_ptr);
36            return MPZEl { integer: result };
37        }
38    }
39
40    pub fn assign(&mut self, rhs: &MPZEl) {
41        unsafe {
42            mpir_bindings::__gmpz_set(
43                &mut self.integer as mpir_bindings::mpz_ptr,
44                &rhs.integer as mpir_bindings::mpz_srcptr,
45            );
46        }
47    }
48}
49
50impl Clone for MPZEl {
51    fn clone(&self) -> Self { MPZ::RING.clone_el(self) }
52}
53
54/// Except for random number generation (which we do in Rust), GMP/MPIR
55/// is thread-safe (Section 3.7 of the manual)
56unsafe impl Send for MPZEl {}
57/// Except for random number generation (which we do in Rust), GMP/MPIR
58/// is thread-safe (Section 3.7 of the manual)
59unsafe impl Sync for MPZEl {}
60
61impl Drop for MPZEl {
62    fn drop(&mut self) { unsafe { mpir_bindings::__gmpz_clear(&mut self.integer as mpir_bindings::mpz_ptr) } }
63}
64
65impl std::fmt::Debug for MPZEl {
66    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result { MPZ::RING.get_ring().dbg(self, f) }
67}
68
69/// Arbitrary-precision integer ring, implemented by binding to the well-known
70/// and heavily optimized library mpir (fork of gmp).
71///
72/// TODO: Remove `Copy` at next breaking release.
73#[derive(Clone, Copy, PartialEq, Eq)]
74pub struct MPZBase;
75
76/// [`RingStore`] corresponding to [`MPZBase`].
77pub type MPZ = RingValue<MPZBase>;
78
79impl MPZ {
80    pub const RING: MPZ = RingValue::from(MPZBase);
81}
82
83impl MPZBase {
84    /// Interprets the bytes in `input` as little endian bytes and returns the
85    /// nonnegative integer represented by them.
86    pub fn from_le_bytes(&self, dst: &mut MPZEl, input: &[u8]) {
87        unsafe {
88            assert_eq!(
89                std::mem::size_of::<mpir_bindings::mpir_ui>(),
90                std::mem::size_of::<u64>()
91            );
92            if input.len() == 0 {
93                mpir_bindings::__gmpz_set_ui(&mut dst.integer as mpir_bindings::mpz_ptr, 0);
94                return;
95            }
96            assert!(input.len() > 0);
97            mpir_bindings::__gmpz_import(
98                &mut dst.integer as mpir_bindings::mpz_ptr,
99                input.len(),
100                -1i32, // least significant digit first
101                1 as libc::size_t,
102                -1, // little endian
103                0,
104                input.as_ptr() as *const libc::c_void,
105            );
106        }
107    }
108
109    /// Interprets the `u64` as digits w.r.t. base `2^64` (with least-significant digit first)
110    /// and returns the nonnegative integer represented by them.
111    pub fn from_base_u64_repr(&self, dst: &mut MPZEl, input: &[u64]) {
112        unsafe {
113            assert_eq!(
114                std::mem::size_of::<mpir_bindings::mpir_ui>(),
115                std::mem::size_of::<u64>()
116            );
117            if input.len() == 0 {
118                mpir_bindings::__gmpz_set_ui(&mut dst.integer as mpir_bindings::mpz_ptr, 0);
119                return;
120            }
121            assert!(input.len() > 0);
122            mpir_bindings::__gmpz_import(
123                &mut dst.integer as mpir_bindings::mpz_ptr,
124                input.len(),
125                -1i32, // least significant digit first
126                (u64::BITS / 8) as libc::size_t,
127                0, // native endianess
128                0,
129                input.as_ptr() as *const libc::c_void,
130            );
131        }
132    }
133
134    pub fn abs_base_u64_repr_len(&self, src: &MPZEl) -> usize {
135        self.abs_highest_set_bit(src)
136            .map(|n| (n / u64::BITS as usize) + 1)
137            .unwrap_or(0)
138    }
139
140    /// Inverse to [`MPZBase::from_base_u64_repr()`].
141    pub fn abs_base_u64_repr(&self, src: &MPZEl, out: &mut [u64]) {
142        unsafe {
143            if self.abs_base_u64_repr_len(src) > 0 {
144                assert!(out.len() >= self.abs_base_u64_repr_len(src));
145                let mut size = 0;
146
147                let result_ptr = mpir_bindings::__gmpz_export(
148                    out.as_mut_ptr() as *mut libc::c_void,
149                    &mut size,
150                    -1, // least significant digit first
151                    (u64::BITS / 8) as libc::size_t,
152                    0, // native endianess
153                    0,
154                    &src.integer as mpir_bindings::mpz_srcptr,
155                );
156                assert_eq!(result_ptr as *const libc::c_void, out.as_ptr() as *const libc::c_void);
157                for i in size..out.len() {
158                    out[i] = 0;
159                }
160            } else {
161                for i in 0..out.len() {
162                    out[i] = 0;
163                }
164            }
165        }
166    }
167
168    pub fn to_le_bytes_len(&self, src: &MPZEl) -> usize {
169        self.abs_highest_set_bit(src)
170            .map(|n| (n / u8::BITS as usize) + 1)
171            .unwrap_or(0)
172    }
173
174    /// Inverse to [`MPZBase::from_le_bytes()`].
175    pub fn to_le_bytes(&self, src: &MPZEl, out: &mut [u8]) {
176        unsafe {
177            if self.to_le_bytes_len(src) > 0 {
178                assert!(out.len() >= self.to_le_bytes_len(src));
179                let mut size = 0;
180
181                let result_ptr = mpir_bindings::__gmpz_export(
182                    out.as_mut_ptr() as *mut libc::c_void,
183                    &mut size,
184                    -1, // least significant digit first
185                    1 as libc::size_t,
186                    -1, // little endian
187                    0,
188                    &src.integer as mpir_bindings::mpz_srcptr,
189                );
190                assert_eq!(result_ptr as *const libc::c_void, out.as_ptr() as *const libc::c_void);
191                for i in size..out.len() {
192                    out[i] = 0;
193                }
194            } else {
195                for i in 0..out.len() {
196                    out[i] = 0;
197                }
198            }
199        }
200    }
201}
202
203impl Debug for MPZBase {
204    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { write!(f, "Z") }
205}
206
207impl RingBase for MPZBase {
208    type Element = MPZEl;
209
210    fn clone_el(&self, val: &Self::Element) -> Self::Element {
211        unsafe {
212            let mut result = MPZEl::new();
213            mpir_bindings::__gmpz_set(
214                &mut result.integer as mpir_bindings::mpz_ptr,
215                &val.integer as mpir_bindings::mpz_srcptr,
216            );
217            return result;
218        }
219    }
220
221    fn mul_ref(&self, lhs: &Self::Element, rhs: &Self::Element) -> Self::Element {
222        unsafe {
223            let mut result = MPZEl::new();
224            mpir_bindings::__gmpz_mul(
225                &mut result.integer as mpir_bindings::mpz_ptr,
226                &lhs.integer as mpir_bindings::mpz_srcptr,
227                &rhs.integer as mpir_bindings::mpz_srcptr,
228            );
229            return result;
230        }
231    }
232
233    fn negate_inplace(&self, lhs: &mut Self::Element) {
234        unsafe {
235            mpir_bindings::__gmpz_neg(
236                &mut lhs.integer as mpir_bindings::mpz_ptr,
237                &lhs.integer as mpir_bindings::mpz_srcptr,
238            )
239        }
240    }
241
242    fn zero(&self) -> Self::Element { MPZEl::new() }
243
244    fn one(&self) -> Self::Element { self.from_int(1) }
245
246    fn sub_ref_fst(&self, lhs: &Self::Element, mut rhs: Self::Element) -> Self::Element {
247        unsafe {
248            mpir_bindings::__gmpz_sub(
249                &mut rhs.integer as mpir_bindings::mpz_ptr,
250                &lhs.integer as mpir_bindings::mpz_srcptr,
251                &rhs.integer as mpir_bindings::mpz_srcptr,
252            );
253            return rhs;
254        }
255    }
256
257    fn sub_ref_snd(&self, mut lhs: Self::Element, rhs: &Self::Element) -> Self::Element {
258        unsafe {
259            mpir_bindings::__gmpz_sub(
260                &mut lhs.integer as mpir_bindings::mpz_ptr,
261                &lhs.integer as mpir_bindings::mpz_srcptr,
262                &rhs.integer as mpir_bindings::mpz_srcptr,
263            );
264            return lhs;
265        }
266    }
267
268    fn add_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) { self.add_assign_ref(lhs, &rhs); }
269
270    fn add_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) {
271        unsafe {
272            mpir_bindings::__gmpz_add(
273                &mut lhs.integer as mpir_bindings::mpz_ptr,
274                &lhs.integer as mpir_bindings::mpz_srcptr,
275                &rhs.integer as mpir_bindings::mpz_srcptr,
276            );
277        }
278    }
279
280    fn mul_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) { self.mul_assign_ref(lhs, &rhs) }
281
282    fn mul_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) {
283        unsafe {
284            mpir_bindings::__gmpz_mul(
285                &mut lhs.integer as mpir_bindings::mpz_ptr,
286                &lhs.integer as mpir_bindings::mpz_srcptr,
287                &rhs.integer as mpir_bindings::mpz_srcptr,
288            );
289        }
290    }
291
292    fn mul_assign_int(&self, lhs: &mut Self::Element, rhs: i32) {
293        unsafe {
294            mpir_bindings::__gmpz_mul_ui(
295                &mut lhs.integer as mpir_bindings::mpz_ptr,
296                &lhs.integer as mpir_bindings::mpz_srcptr,
297                rhs.abs() as u64,
298            );
299            if rhs < 0 {
300                mpir_bindings::__gmpz_neg(
301                    &mut lhs.integer as mpir_bindings::mpz_ptr,
302                    &lhs.integer as mpir_bindings::mpz_srcptr,
303                )
304            }
305        }
306    }
307
308    fn sub(&self, lhs: Self::Element, rhs: Self::Element) -> Self::Element { self.sub_ref_snd(lhs, &rhs) }
309
310    fn from_int(&self, value: i32) -> Self::Element {
311        unsafe {
312            let mut result = MPZEl::new();
313            mpir_bindings::__gmpz_set_ui(&mut result.integer as mpir_bindings::mpz_ptr, value.abs() as u64);
314            if value < 0 {
315                return self.negate(result);
316            } else {
317                return result;
318            }
319        }
320    }
321
322    fn eq_el(&self, lhs: &Self::Element, rhs: &Self::Element) -> bool {
323        unsafe {
324            mpir_bindings::__gmpz_cmp(
325                &lhs.integer as mpir_bindings::mpz_srcptr,
326                &rhs.integer as mpir_bindings::mpz_srcptr,
327            ) == 0
328        }
329    }
330
331    fn is_zero(&self, val: &Self::Element) -> bool {
332        unsafe { mpir_bindings::__gmpz_cmp_si(&val.integer as mpir_bindings::mpz_srcptr, 0) == 0 }
333    }
334
335    fn is_one(&self, val: &Self::Element) -> bool {
336        unsafe { mpir_bindings::__gmpz_cmp_si(&val.integer as mpir_bindings::mpz_srcptr, 1) == 0 }
337    }
338
339    fn is_neg_one(&self, val: &Self::Element) -> bool {
340        unsafe { mpir_bindings::__gmpz_cmp_si(&val.integer as mpir_bindings::mpz_srcptr, -1) == 0 }
341    }
342
343    fn is_noetherian(&self) -> bool { true }
344
345    fn is_commutative(&self) -> bool { true }
346
347    fn is_approximate(&self) -> bool { false }
348
349    fn dbg_within<'a>(
350        &self,
351        value: &Self::Element,
352        out: &mut std::fmt::Formatter<'a>,
353        _env: EnvBindingStrength,
354    ) -> std::fmt::Result {
355        RustBigintRing::RING.get_ring().dbg(
356            &self.map_out(RustBigintRing::RING.get_ring(), self.clone_el(value), &()),
357            out,
358        )
359    }
360
361    fn characteristic<I: IntegerRingStore + Copy>(&self, other_ZZ: I) -> Option<El<I>>
362    where
363        I::Type: IntegerRing,
364    {
365        Some(other_ZZ.zero())
366    }
367}
368
369impl OrderedRing for MPZBase {
370    fn cmp(&self, lhs: &Self::Element, rhs: &Self::Element) -> std::cmp::Ordering {
371        unsafe {
372            let res = mpir_bindings::__gmpz_cmp(
373                &lhs.integer as mpir_bindings::mpz_srcptr,
374                &rhs.integer as mpir_bindings::mpz_srcptr,
375            );
376            if res < 0 {
377                return std::cmp::Ordering::Less;
378            } else if res > 0 {
379                return std::cmp::Ordering::Greater;
380            } else {
381                return std::cmp::Ordering::Equal;
382            }
383        }
384    }
385
386    fn is_neg(&self, value: &Self::Element) -> bool {
387        unsafe { mpir_bindings::mpz_is_neg(&value.integer as mpir_bindings::mpz_srcptr) }
388    }
389}
390
391impl Serialize for MPZBase {
392    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
393    where
394        S: Serializer,
395    {
396        SerializableNewtypeStruct::new("IntegerRing(MPZ)", ()).serialize(serializer)
397    }
398}
399
400impl<'de> Deserialize<'de> for MPZBase {
401    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
402    where
403        D: Deserializer<'de>,
404    {
405        DeserializeSeedNewtypeStruct::new("IntegerRing(MPZ)", PhantomData::<()>)
406            .deserialize(deserializer)
407            .map(|()| MPZ::RING.into())
408    }
409}
410
411impl SerializableElementRing for MPZBase {
412    fn deserialize<'de, D>(&self, deserializer: D) -> Result<Self::Element, D::Error>
413    where
414        D: Deserializer<'de>,
415    {
416        if deserializer.is_human_readable() {
417            return DeserializeWithRing::new(RustBigintRing::RING)
418                .deserialize(deserializer)
419                .map(|n| int_cast(n, RingRef::new(self), RustBigintRing::RING));
420        } else {
421            let (negative, mut result) = deserialize_bigint_from_bytes(deserializer, |data| {
422                let mut result = self.zero();
423                self.from_le_bytes(&mut result, data);
424                return result;
425            })?;
426            if negative {
427                self.negate_inplace(&mut result);
428            }
429            return Ok(result);
430        }
431    }
432
433    fn serialize<S>(&self, el: &Self::Element, serializer: S) -> Result<S::Ok, S::Error>
434    where
435        S: Serializer,
436    {
437        if serializer.is_human_readable() {
438            SerializableNewtypeStruct::new("BigInt", format!("{}", RingRef::new(self).format(el)).as_str())
439                .serialize(serializer)
440        } else {
441            let len = self.to_le_bytes_len(el);
442            let mut data = Vec::with_capacity(len);
443            data.resize(len, 0u8);
444            self.to_le_bytes(el, &mut data);
445            let mut seq = serializer.serialize_tuple(2)?;
446            seq.serialize_element(&self.is_neg(el))?;
447            seq.serialize_element(serde_bytes::Bytes::new(&data[..]))?;
448            return seq.end();
449        }
450    }
451}
452
453impl DivisibilityRing for MPZBase {
454    fn checked_left_div(&self, lhs: &Self::Element, rhs: &Self::Element) -> Option<Self::Element> {
455        if self.is_zero(rhs) {
456            if self.is_zero(lhs) {
457                return Some(self.zero());
458            } else {
459                return None;
460            }
461        }
462        let (quo, rem) = self.euclidean_div_rem(self.clone_el(lhs), rhs);
463        if self.is_zero(&rem) {
464            return Some(quo);
465        } else {
466            return None;
467        }
468    }
469
470    fn balance_factor<'a, I>(&self, elements: I) -> Option<Self::Element>
471    where
472        I: Iterator<Item = &'a Self::Element>,
473        Self: 'a,
474    {
475        Some(elements.fold(self.zero(), |a, b| self.ideal_gen(&a, b)))
476    }
477}
478
479impl PrincipalIdealRing for MPZBase {
480    fn extended_ideal_gen(
481        &self,
482        lhs: &Self::Element,
483        rhs: &Self::Element,
484    ) -> (Self::Element, Self::Element, Self::Element) {
485        algorithms::eea::eea(self.clone_el(lhs), self.clone_el(rhs), MPZ::RING)
486    }
487
488    fn checked_div_min(&self, lhs: &Self::Element, rhs: &Self::Element) -> Option<Self::Element> {
489        if self.is_zero(lhs) && self.is_zero(rhs) {
490            return Some(self.one());
491        }
492        self.checked_left_div(lhs, rhs)
493    }
494}
495
496impl EuclideanRing for MPZBase {
497    fn euclidean_div_rem(&self, mut lhs: Self::Element, rhs: &Self::Element) -> (Self::Element, Self::Element) {
498        unsafe {
499            assert!(!self.is_zero(rhs));
500            let mut quo = MPZEl::new();
501            mpir_bindings::__gmpz_tdiv_qr(
502                &mut quo.integer as mpir_bindings::mpz_ptr,
503                &mut lhs.integer as mpir_bindings::mpz_ptr,
504                &lhs.integer as mpir_bindings::mpz_srcptr,
505                &rhs.integer as mpir_bindings::mpz_srcptr,
506            );
507            return (quo, lhs);
508        }
509    }
510
511    fn euclidean_rem(&self, lhs: Self::Element, rhs: &Self::Element) -> Self::Element {
512        unsafe {
513            assert!(!self.is_zero(rhs));
514            let mut rem = MPZEl::new();
515            mpir_bindings::__gmpz_tdiv_r(
516                &mut rem.integer as mpir_bindings::mpz_ptr,
517                &lhs.integer as mpir_bindings::mpz_srcptr,
518                &rhs.integer as mpir_bindings::mpz_srcptr,
519            );
520            return rem;
521        }
522    }
523
524    fn euclidean_div(&self, lhs: Self::Element, rhs: &Self::Element) -> Self::Element {
525        unsafe {
526            assert!(!self.is_zero(rhs));
527            let mut rem = MPZEl::new();
528            mpir_bindings::__gmpz_tdiv_q(
529                &mut rem.integer as mpir_bindings::mpz_ptr,
530                &lhs.integer as mpir_bindings::mpz_srcptr,
531                &rhs.integer as mpir_bindings::mpz_srcptr,
532            );
533            return rem;
534        }
535    }
536
537    fn euclidean_deg(&self, val: &Self::Element) -> Option<usize> {
538        if self.abs_highest_set_bit(val).unwrap_or(0) < usize::BITS as usize {
539            unsafe {
540                mpir_bindings::__gmpz_get_ui(&val.integer as mpir_bindings::mpz_srcptr)
541                    .try_into()
542                    .ok()
543            }
544        } else {
545            None
546        }
547    }
548}
549
550impl Default for MPZBase {
551    fn default() -> Self { MPZ::RING.into() }
552}
553
554impl Domain for MPZBase {}
555
556impl IntegerRing for MPZBase {
557    fn to_float_approx(&self, el: &Self::Element) -> f64 {
558        unsafe { mpir_bindings::__gmpz_get_d(&el.integer as mpir_bindings::mpz_srcptr) }
559    }
560
561    fn from_float_approx(&self, el: f64) -> Option<Self::Element> {
562        unsafe {
563            let mut result = MPZEl::new();
564            mpir_bindings::__gmpz_set_d(&mut result.integer as mpir_bindings::mpz_ptr, el);
565            return Some(result);
566        }
567    }
568
569    fn mul_pow_2(&self, el: &mut Self::Element, power: usize) {
570        unsafe {
571            mpir_bindings::__gmpz_mul_2exp(
572                &mut el.integer as mpir_bindings::mpz_ptr,
573                &el.integer as mpir_bindings::mpz_srcptr,
574                power as u64,
575            )
576        }
577    }
578
579    fn euclidean_div_pow_2(&self, el: &mut Self::Element, power: usize) {
580        unsafe {
581            mpir_bindings::__gmpz_tdiv_q_2exp(
582                &mut el.integer as mpir_bindings::mpz_ptr,
583                &el.integer as mpir_bindings::mpz_srcptr,
584                power as u64,
585            )
586        }
587    }
588
589    fn abs_is_bit_set(&self, el: &Self::Element, bit: usize) -> bool {
590        unsafe {
591            if mpir_bindings::mpz_is_neg(&el.integer as mpir_bindings::mpz_srcptr) {
592                let value = mpir_bindings::__gmpz_tstbit(&el.integer as mpir_bindings::mpz_srcptr, bit as u64) == 1;
593                let least_significant_zero = mpir_bindings::__gmpz_scan1(&el.integer as mpir_bindings::mpz_srcptr, 0);
594                if bit <= least_significant_zero as usize {
595                    value
596                } else {
597                    !value
598                }
599            } else {
600                mpir_bindings::__gmpz_tstbit(&el.integer as mpir_bindings::mpz_srcptr, bit as u64) == 1
601            }
602        }
603    }
604
605    fn abs_highest_set_bit(&self, value: &Self::Element) -> Option<usize> {
606        unsafe {
607            if self.is_zero(value) {
608                return None;
609            }
610            Some(mpir_bindings::__gmpz_sizeinbase(&value.integer as mpir_bindings::mpz_srcptr, 2) - 1)
611        }
612    }
613
614    fn abs_lowest_set_bit(&self, value: &Self::Element) -> Option<usize> {
615        unsafe {
616            let result = mpir_bindings::__gmpz_scan1(&value.integer as mpir_bindings::mpz_srcptr, 0);
617            if result == mpir_bindings::mpir_ui::MAX {
618                return None;
619            } else {
620                return Some(result as usize);
621            }
622        }
623    }
624
625    fn rounded_div(&self, lhs: Self::Element, rhs: &Self::Element) -> Self::Element {
626        let mut rhs_half = self.abs(self.clone_el(rhs));
627        self.euclidean_div_pow_2(&mut rhs_half, 1);
628        if self.is_neg(&lhs) {
629            return self.euclidean_div(self.sub(lhs, rhs_half), rhs);
630        } else {
631            return self.euclidean_div(self.add(lhs, rhs_half), rhs);
632        }
633    }
634
635    fn get_uniformly_random_bits<G: FnMut() -> u64>(&self, log2_bound_exclusive: usize, rng: G) -> Self::Element {
636        unsafe {
637            let mut result = MPZEl::new();
638            let len = (log2_bound_exclusive - 1) / u64::BITS as usize + 1;
639            let mut data = Vec::new();
640            data.resize_with(len, rng);
641
642            mpir_bindings::__gmpz_import(
643                &mut result.integer as mpir_bindings::mpz_ptr,
644                data.len(),
645                -1i32,
646                (u64::BITS / 8) as libc::size_t,
647                0,
648                0,
649                (data.as_ptr() as *const mpir_bindings::mpir_ui) as *const libc::c_void,
650            );
651
652            self.euclidean_div_pow_2(&mut result, len * u64::BITS as usize - log2_bound_exclusive);
653            return result;
654        }
655    }
656
657    fn representable_bits(&self) -> Option<usize> { None }
658}
659
660impl_interpolation_base_ring_char_zero! { InterpolationBaseRing for MPZBase }
661
662impl_poly_gcd_locally_for_ZZ! { IntegerPolyGCDRing for MPZBase }
663
664impl_eval_poly_locally_for_ZZ! { EvalPolyLocallyRing for MPZBase }
665
666impl FiniteRingSpecializable for MPZBase {
667    fn specialize<O: FiniteRingOperation<Self>>(op: O) -> O::Output { op.fallback() }
668}
669
670impl HashableElRing for MPZBase {
671    fn hash<H: std::hash::Hasher>(&self, el: &Self::Element, h: &mut H) {
672        unsafe {
673            <_ as std::hash::Hash>::hash(
674                &(
675                    self.is_neg(&el),
676                    self.abs_highest_set_bit(&el),
677                    mpir_bindings::__gmpz_get_ui(&el.integer as mpir_bindings::mpz_srcptr),
678                ),
679                h,
680            )
681        }
682    }
683}
684
685impl IntCast<RustBigintRingBase> for MPZBase {
686    fn cast(&self, _: &RustBigintRingBase, el: RustBigint) -> Self::Element {
687        let mut result = MPZEl::new();
688        self.from_base_u64_repr(
689            &mut result,
690            &RustBigintRing::RING
691                .get_ring()
692                .abs_base_u64_repr(&el)
693                .collect::<Vec<_>>()[..],
694        );
695        if RustBigintRing::RING.is_neg(&el) {
696            self.negate_inplace(&mut result);
697        }
698        return result;
699    }
700}
701
702impl IntCast<MPZBase> for RustBigintRingBase {
703    fn cast(&self, from: &MPZBase, el: MPZEl) -> RustBigint {
704        let mut result = (0..from.abs_base_u64_repr_len(&el)).map(|_| 0u64).collect::<Vec<_>>();
705        from.abs_base_u64_repr(&el, &mut result[..]);
706        let result = RustBigintRing::RING.get_ring().from_base_u64_repr(result.into_iter());
707        if from.is_neg(&el) {
708            return RustBigintRing::RING.negate(result);
709        } else {
710            return result;
711        }
712    }
713}
714
715impl IntCast<MPZBase> for MPZBase {
716    fn cast(&self, _from: &MPZBase, el: MPZEl) -> MPZEl { el }
717}
718
719impl IntCast<StaticRingBase<i64>> for MPZBase {
720    fn cast(&self, _: &StaticRingBase<i64>, el: i64) -> Self::Element {
721        unsafe {
722            let mut result = MPZEl::new();
723            mpir_bindings::__gmpz_set_si(&mut result.integer as *mut _, el);
724            return result;
725        }
726    }
727}
728
729impl IntCast<MPZBase> for StaticRingBase<i64> {
730    fn cast(&self, from: &MPZBase, el: MPZEl) -> i64 {
731        assert!(from.abs_highest_set_bit(&el).unwrap_or(0) < u64::BITS as usize);
732        let negative = from.is_neg(&el);
733        unsafe {
734            let result = mpir_bindings::__gmpz_get_ui(&el.integer as mpir_bindings::mpz_srcptr);
735            if !negative {
736                result.try_into().unwrap()
737            } else if result == i64::MAX as u64 + 1 {
738                i64::MIN
739            } else {
740                -i64::try_from(result).unwrap()
741            }
742        }
743    }
744}
745
746impl IntCast<StaticRingBase<i128>> for MPZBase {
747    fn cast(&self, _: &StaticRingBase<i128>, el: i128) -> MPZEl {
748        let el_abs = el.unsigned_abs();
749        let data = [(el_abs & u64::MAX as u128) as u64, (el_abs >> u64::BITS) as u64];
750        let mut result = MPZEl::new();
751        self.from_base_u64_repr(&mut result, &data[..]);
752        if el < 0 {
753            self.negate_inplace(&mut result);
754        }
755        return result;
756    }
757}
758
759impl IntCast<MPZBase> for StaticRingBase<i128> {
760    fn cast(&self, from: &MPZBase, el: MPZEl) -> i128 {
761        assert!(from.abs_base_u64_repr_len(&el) <= 2);
762        let mut data = [0u64; 2];
763        from.abs_base_u64_repr(&el, &mut data);
764        let result = data[0] as u128 + ((data[1] as u128) << u64::BITS);
765        if from.is_neg(&el) {
766            if result == i128::MIN.unsigned_abs() {
767                return i128::MIN;
768            } else {
769                return -i128::try_from(result).unwrap();
770            }
771        } else {
772            return result.try_into().unwrap();
773        }
774    }
775}
776
777macro_rules! specialize_int_cast {
778    ($($from:ty),*) => {
779        $(
780            impl IntCast<StaticRingBase<$from>> for MPZBase {
781
782                fn cast(&self, _: &StaticRingBase<$from>, el: $from) -> MPZEl {
783                    int_cast(el.try_into().unwrap(), &RingRef::new(self), StaticRing::<i64>::RING)
784                }
785            }
786
787            impl IntCast<MPZBase> for StaticRingBase<$from> {
788
789                fn cast(&self, _: &MPZBase, el: MPZEl) -> $from {
790                    int_cast(el, &StaticRing::<i64>::RING, &MPZ::RING) as $from
791                }
792            }
793        )*
794    }
795}
796
797specialize_int_cast! { i8, i16, i32 }
798
799#[cfg(test)]
800use crate::pid::EuclideanRingStore;
801use crate::serialization::{DeserializeWithRing, SerializableElementRing};
802
803#[cfg(test)]
804fn edge_case_elements_bigint() -> impl Iterator<Item = RustBigint> {
805    [
806        RustBigintRing::RING.int_hom().map(0),
807        RustBigintRing::RING.int_hom().map(1),
808        RustBigintRing::RING.int_hom().map(-1),
809        RustBigintRing::RING.int_hom().map(7),
810        RustBigintRing::RING.int_hom().map(-7),
811        RustBigintRing::RING.int_hom().map(i32::MAX),
812        RustBigintRing::RING.int_hom().map(i32::MIN),
813        RustBigintRing::RING.power_of_two(64),
814        RustBigintRing::RING.negate(RustBigintRing::RING.power_of_two(64)),
815        RustBigintRing::RING.sub(RustBigintRing::RING.power_of_two(64), RustBigintRing::RING.one()),
816        RustBigintRing::RING.power_of_two(128),
817        RustBigintRing::RING.negate(RustBigintRing::RING.power_of_two(128)),
818        RustBigintRing::RING.sub(RustBigintRing::RING.power_of_two(128), RustBigintRing::RING.one()),
819        RustBigintRing::RING.power_of_two(192),
820        RustBigintRing::RING.negate(RustBigintRing::RING.power_of_two(192)),
821        RustBigintRing::RING.sub(RustBigintRing::RING.power_of_two(192), RustBigintRing::RING.one()),
822    ]
823    .into_iter()
824}
825
826#[cfg(test)]
827fn edge_case_elements() -> impl Iterator<Item = MPZEl> {
828    edge_case_elements_bigint().map(|n| MPZ::RING.coerce(&RustBigintRing::RING, n))
829}
830
831#[test]
832fn test_negate_inplace() {
833    let mut a = MPZ::RING.power_of_two(64);
834    MPZ::RING.negate_inplace(&mut a);
835    assert!(MPZ::RING.is_neg(&a));
836
837    for a in edge_case_elements() {
838        let mut b = MPZ::RING.clone_el(&a);
839        MPZ::RING.negate_inplace(&mut b);
840        assert!(MPZ::RING.is_zero(&a) || (MPZ::RING.is_neg(&a) ^ MPZ::RING.is_neg(&b)));
841    }
842}
843
844#[test]
845fn test_ring_axioms() { crate::ring::generic_tests::test_ring_axioms(MPZ::RING, edge_case_elements()) }
846
847#[test]
848fn test_hash_axioms() { crate::ring::generic_tests::test_hash_axioms(MPZ::RING, edge_case_elements()); }
849
850#[test]
851fn test_divisibility_ring_axioms() {
852    crate::divisibility::generic_tests::test_divisibility_axioms(MPZ::RING, edge_case_elements())
853}
854
855#[test]
856fn test_euclidean_ring_axioms() {
857    crate::pid::generic_tests::test_euclidean_ring_axioms(MPZ::RING, edge_case_elements())
858}
859
860#[test]
861fn test_integer_ring_axioms() { crate::integer::generic_tests::test_integer_axioms(MPZ::RING, edge_case_elements()) }
862
863#[test]
864fn test_canonical_iso_axioms_i32() {
865    crate::ring::generic_tests::test_hom_axioms(
866        StaticRing::<i32>::RING,
867        MPZ::RING,
868        [0, -1, 1, i16::MAX as i32, i16::MIN as i32].into_iter(),
869    );
870    crate::ring::generic_tests::test_iso_axioms(
871        StaticRing::<i32>::RING,
872        MPZ::RING,
873        [0, -1, 1, i16::MIN as i32, i16::MAX as i32].into_iter(),
874    );
875}
876
877#[test]
878fn test_canonical_iso_axioms_i64() {
879    crate::ring::generic_tests::test_hom_axioms(
880        StaticRing::<i64>::RING,
881        MPZ::RING,
882        [0, -1, 1, i32::MAX as i64, i32::MIN as i64].into_iter(),
883    );
884    crate::ring::generic_tests::test_iso_axioms(
885        StaticRing::<i64>::RING,
886        MPZ::RING,
887        [0, -1, 1, i32::MIN as i64, i32::MAX as i64].into_iter(),
888    );
889
890    assert_el_eq!(
891        MPZ::RING,
892        MPZ::RING.sub(MPZ::RING.power_of_two(63), MPZ::RING.one()),
893        &MPZ::RING.coerce(&StaticRing::<i64>::RING, i64::MAX)
894    );
895    assert_el_eq!(
896        MPZ::RING,
897        MPZ::RING.negate(MPZ::RING.power_of_two(63)),
898        MPZ::RING.coerce(&StaticRing::<i64>::RING, i64::MIN)
899    );
900    assert_eq!(
901        i64::MAX,
902        int_cast(
903            MPZ::RING.sub(MPZ::RING.power_of_two(63), MPZ::RING.one()),
904            &StaticRing::<i64>::RING,
905            MPZ::RING
906        )
907    );
908    assert_eq!(
909        i64::MIN,
910        int_cast(
911            MPZ::RING.negate(MPZ::RING.power_of_two(63)),
912            &StaticRing::<i64>::RING,
913            MPZ::RING
914        )
915    );
916}
917
918#[test]
919fn test_canonical_iso_axioms_i128() {
920    crate::ring::generic_tests::test_hom_axioms(
921        StaticRing::<i128>::RING,
922        MPZ::RING,
923        [0, -1, 1, i64::MAX as i128, i64::MIN as i128].into_iter(),
924    );
925    crate::ring::generic_tests::test_iso_axioms(
926        StaticRing::<i128>::RING,
927        MPZ::RING,
928        [0, -1, 1, i64::MIN as i128, i64::MAX as i128].into_iter(),
929    );
930
931    assert_el_eq!(
932        MPZ::RING,
933        MPZ::RING.sub(MPZ::RING.power_of_two(127), MPZ::RING.one()),
934        &MPZ::RING.coerce(&StaticRing::<i128>::RING, i128::MAX)
935    );
936    assert_el_eq!(
937        MPZ::RING,
938        MPZ::RING.negate(MPZ::RING.power_of_two(127)),
939        MPZ::RING.coerce(&StaticRing::<i128>::RING, i128::MIN)
940    );
941    assert_eq!(
942        i128::MAX,
943        int_cast(
944            MPZ::RING.sub(MPZ::RING.power_of_two(127), MPZ::RING.one()),
945            &StaticRing::<i128>::RING,
946            MPZ::RING
947        )
948    );
949    assert_eq!(
950        i128::MIN,
951        int_cast(
952            MPZ::RING.negate(MPZ::RING.power_of_two(127)),
953            &StaticRing::<i128>::RING,
954            MPZ::RING
955        )
956    );
957}
958
959#[test]
960fn test_canonical_iso_axioms_bigint() {
961    crate::ring::generic_tests::test_hom_axioms(RustBigintRing::RING, MPZ::RING, edge_case_elements_bigint());
962    crate::ring::generic_tests::test_iso_axioms(RustBigintRing::RING, MPZ::RING, edge_case_elements_bigint());
963}
964
965#[test]
966fn test_abs_is_bit_set() {
967    let a = MPZ::RING.int_hom().map(1 << 15);
968    assert_eq!(true, MPZ::RING.abs_is_bit_set(&a, 15));
969    assert_eq!(false, MPZ::RING.abs_is_bit_set(&a, 16));
970    assert_eq!(false, MPZ::RING.abs_is_bit_set(&a, 14));
971
972    let a = MPZ::RING.int_hom().map(-7);
973    assert_eq!(true, MPZ::RING.abs_is_bit_set(&a, 0));
974    assert_eq!(true, MPZ::RING.abs_is_bit_set(&a, 1));
975    assert_eq!(true, MPZ::RING.abs_is_bit_set(&a, 2));
976    assert_eq!(false, MPZ::RING.abs_is_bit_set(&a, 3));
977
978    let a = MPZ::RING.int_hom().map(-1 << 15);
979    assert_eq!(true, MPZ::RING.abs_is_bit_set(&a, 15));
980    assert_eq!(false, MPZ::RING.abs_is_bit_set(&a, 16));
981    assert_eq!(false, MPZ::RING.abs_is_bit_set(&a, 14));
982}
983
984#[test]
985fn test_highest_set_bit() {
986    assert_eq!(None, MPZ::RING.abs_highest_set_bit(&MPZ::RING.int_hom().map(0)));
987    assert_eq!(Some(0), MPZ::RING.abs_highest_set_bit(&MPZ::RING.int_hom().map(1)));
988    assert_eq!(Some(0), MPZ::RING.abs_highest_set_bit(&MPZ::RING.int_hom().map(-1)));
989    assert_eq!(Some(1), MPZ::RING.abs_highest_set_bit(&MPZ::RING.int_hom().map(2)));
990    assert_eq!(Some(1), MPZ::RING.abs_highest_set_bit(&MPZ::RING.int_hom().map(-2)));
991    assert_eq!(Some(1), MPZ::RING.abs_highest_set_bit(&MPZ::RING.int_hom().map(3)));
992    assert_eq!(Some(1), MPZ::RING.abs_highest_set_bit(&MPZ::RING.int_hom().map(-3)));
993    assert_eq!(Some(2), MPZ::RING.abs_highest_set_bit(&MPZ::RING.int_hom().map(4)));
994    assert_eq!(Some(2), MPZ::RING.abs_highest_set_bit(&MPZ::RING.int_hom().map(-4)));
995}
996
997#[test]
998fn test_lowest_set_bit() {
999    assert_eq!(None, MPZ::RING.abs_highest_set_bit(&MPZ::RING.int_hom().map(0)));
1000    assert_eq!(Some(0), MPZ::RING.abs_lowest_set_bit(&MPZ::RING.int_hom().map(1)));
1001    assert_eq!(Some(0), MPZ::RING.abs_lowest_set_bit(&MPZ::RING.int_hom().map(-1)));
1002    assert_eq!(Some(1), MPZ::RING.abs_lowest_set_bit(&MPZ::RING.int_hom().map(2)));
1003    assert_eq!(Some(1), MPZ::RING.abs_lowest_set_bit(&MPZ::RING.int_hom().map(-2)));
1004    assert_eq!(Some(0), MPZ::RING.abs_lowest_set_bit(&MPZ::RING.int_hom().map(3)));
1005    assert_eq!(Some(0), MPZ::RING.abs_lowest_set_bit(&MPZ::RING.int_hom().map(-3)));
1006    assert_eq!(Some(2), MPZ::RING.abs_lowest_set_bit(&MPZ::RING.int_hom().map(4)));
1007    assert_eq!(Some(2), MPZ::RING.abs_lowest_set_bit(&MPZ::RING.int_hom().map(-4)));
1008}
1009
1010#[test]
1011fn from_to_float_approx() {
1012    let x: f64 = 83465209236517892563478156042389675783219532497861237985328563.0;
1013    let y = MPZ::RING.to_float_approx(&MPZ::RING.from_float_approx(x).unwrap());
1014    assert!(x * 0.99 < y);
1015    assert!(y < x * 1.01);
1016}
1017
1018#[bench]
1019fn bench_mul_300_bits(bencher: &mut test::Bencher) {
1020    let x = MPZ::RING.coerce(
1021        &RustBigintRing::RING,
1022        RustBigintRing::RING
1023            .get_ring()
1024            .parse(
1025                "2382385687561872365981723456981723456987134659834659813491964132897159283746918732563498628754",
1026                10,
1027            )
1028            .unwrap(),
1029    );
1030    let y = MPZ::RING.coerce(
1031        &RustBigintRing::RING,
1032        RustBigintRing::RING
1033            .get_ring()
1034            .parse("48937502893645789234569182735646324895723409587234", 10)
1035            .unwrap(),
1036    );
1037    let z = MPZ::RING.coerce(&RustBigintRing::RING, RustBigintRing::RING.get_ring().parse("116588006478839442056346504147013274749794691549803163727888681858469844569693215953808606899770104590589390919543097259495176008551856143726436", 10).unwrap());
1038    bencher.iter(|| {
1039        let p = MPZ::RING.mul_ref(&x, &y);
1040        assert_el_eq!(MPZ::RING, z, p);
1041    })
1042}
1043
1044#[bench]
1045fn bench_div_300_bits(bencher: &mut test::Bencher) {
1046    let x = MPZ::RING.coerce(
1047        &RustBigintRing::RING,
1048        RustBigintRing::RING
1049            .get_ring()
1050            .parse(
1051                "2382385687561872365981723456981723456987134659834659813491964132897159283746918732563498628754",
1052                10,
1053            )
1054            .unwrap(),
1055    );
1056    let y = MPZ::RING.coerce(
1057        &RustBigintRing::RING,
1058        RustBigintRing::RING
1059            .get_ring()
1060            .parse("48937502893645789234569182735646324895723409587234", 10)
1061            .unwrap(),
1062    );
1063    let z = MPZ::RING.coerce(&RustBigintRing::RING, RustBigintRing::RING.get_ring().parse("116588006478839442056346504147013274749794691549803163727888681858469844569693215953808606899770104590589390919543097259495176008551856143726436", 10).unwrap());
1064    bencher.iter(|| {
1065        let q = MPZ::RING.euclidean_div(MPZ::RING.clone_el(&z), &y);
1066        assert_el_eq!(MPZ::RING, x, q);
1067    })
1068}
1069
1070#[test]
1071fn test_serialization() { crate::serialization::generic_tests::test_serialization(MPZ::RING, edge_case_elements()); }
feanor_math/rings/mpir/mod.rs

feanor_math/rings/mpir/
mod.rs
