feanor_math/rings/mpir/
mod.rs

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

feanor_math/rings/mpir/
mod.rs
