feanor_math/rings/
rust_bigint.rs

1use feanor_serde::newtype_struct::{DeserializeSeedNewtypeStruct, SerializableNewtypeStruct};
2use serde::de::{self, DeserializeSeed};
3use serde::ser::SerializeTuple;
4use serde::{Deserializer, Serialize, Deserialize, Serializer}; 
5
6use crate::algorithms::bigint_ops::*;
7use crate::divisibility::{DivisibilityRing, Domain};
8use crate::pid::*;
9use crate::{impl_interpolation_base_ring_char_zero, impl_poly_gcd_locally_for_ZZ, impl_eval_poly_locally_for_ZZ};
10use crate::integer::*;
11use crate::ordered::*;
12use crate::primitive_int::*;
13use crate::ring::*;
14use crate::algorithms;
15use crate::serialization::*;
16use crate::specialization::*;
17
18use std::alloc::Allocator;
19use std::alloc::Global;
20use std::cmp::Ordering::*;
21use std::cmp::Ordering;
22use std::fmt::Debug;
23use std::marker::PhantomData;
24
25///
26/// An element of the integer ring implementation [`RustBigintRing`].
27/// 
28/// An object of this struct does represent an arbitrary-precision integer,
29/// but it follows the general approach of `feanor-math` to expose its actual
30/// behavior through the ring, and not through the elements. For example, to
31/// add integers, use
32/// ```rust
33/// # use feanor_math::ring::*;
34/// # use feanor_math::integer::*;
35/// # use feanor_math::rings::rust_bigint::*;
36/// const ZZ: RustBigintRing = RustBigintRing::RING;
37/// let a: RustBigint = ZZ.add(ZZ.power_of_two(50), ZZ.power_of_two(100));
38/// assert_eq!("1267650600228230527396610048000", format!("{}", ZZ.format(&a)));
39/// ```
40/// and not
41/// ```compile_fail
42/// assert_eq!("1267650600228230527396610048000", format!("{}", RustBigint::from(2).pow(100) + RustBigint::from(2).pow(50)));
43/// ```
44/// 
45#[derive(Clone, Debug)]
46pub struct RustBigint<A: Allocator = Global>(bool, Vec<u64, A>);
47
48///
49/// Arbitrary-precision integer implementation.
50/// 
51/// This is a not-too-well optimized implementation, written in pure Rust.
52/// If you need very high performance, consider using [`crate::rings::mpir::MPZ`]
53/// (requires an installation of mpir and activating the feature "mpir").
54/// 
55#[derive(Copy, Clone)]
56pub struct RustBigintRingBase<A: Allocator + Clone = Global> {
57    allocator: A
58}
59
60///
61/// [`RingStore`] corresponding to [`RustBigintRingBase`].
62/// 
63pub type RustBigintRing<A = Global> = RingValue<RustBigintRingBase<A>>;
64
65impl<A: Allocator + Clone> RustBigintRing<A> {
66    
67    #[stability::unstable(feature = "enable")]
68    pub fn new_with_alloc(allocator: A) -> RustBigintRing<A> {
69        Self::from(RustBigintRingBase { allocator })
70    }
71}
72
73impl RustBigintRing {
74    
75    ///
76    /// Default instance of [`RustBigintRing`], the ring of arbitrary-precision integers.
77    /// 
78    pub const RING: RustBigintRing = RingValue::from(RustBigintRingBase { allocator: Global });
79}
80
81impl<A: Allocator + Clone + Default> Default for RustBigintRingBase<A> {
82
83    fn default() -> Self {
84        RustBigintRingBase { allocator: A::default() }
85    }
86}
87
88impl<A: Allocator + Clone> RustBigintRingBase<A> {
89
90    ///
91    /// If the given big integer fits into a `i128`, this will be
92    /// returned. Otherwise, `None` is returned.
93    /// 
94    pub fn map_i128(&self, val: &RustBigint<A>) -> Option<i128> {
95        match highest_set_block(&val.1) {
96            None => Some(0),
97            Some(0) if val.0 => Some(-(val.1[0] as i128)),
98            Some(0) if !val.0 => Some(val.1[0] as i128),
99            Some(1) if val.0 => {
100                let value = val.1[0] as u128 + ((val.1[1] as u128) << u64::BITS);
101                if value == 1 << (u128::BITS - 1) {
102                    Some(i128::MIN)
103                } else {
104                    i128::try_from(value).ok().map(|x| -x)
105                }
106            },
107            Some(1) if !val.0 => i128::try_from(val.1[0] as u128 + ((val.1[1] as u128) << u64::BITS)).ok(),
108            Some(_) => None
109        }
110    }
111
112    ///
113    /// Returns an iterator over the digits of the `2^64`-adic digit
114    /// representation of the absolute value of the given element.
115    /// 
116    pub fn abs_base_u64_repr<'a>(&self, el: &'a RustBigint) -> impl 'a + Iterator<Item = u64> {
117        el.1.iter().copied()
118    }
119
120    ///
121    /// Interprets the elements of the iterator as digits in a `2^64`-adic
122    /// digit representation, and returns the big integer represented by it.
123    /// 
124    pub fn from_base_u64_repr<I>(&self, data: I) -> RustBigint
125        where I: Iterator<Item = u64>
126    {
127        RustBigint(false, data.collect())
128    }
129}
130
131impl<A: Allocator + Clone> Debug for RustBigintRingBase<A> {
132    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
133        write!(f, "Z")
134    }
135}
136
137impl<A: Allocator + Clone> PartialEq for RustBigintRingBase<A> {
138
139    fn eq(&self, _other: &Self) -> bool {
140        // it is perfectly valid to swap elements between two different `RustBigintRing`s,
141        // even if they have different allocators. Every element keeps track of their allocator 
142        // themselves
143        true
144    }
145}
146
147impl<A: Allocator + Clone> RingBase for RustBigintRingBase<A> {
148    
149    type Element = RustBigint<A>;
150
151    fn clone_el(&self, val: &Self::Element) -> Self::Element {
152        // allocate it with our allocator
153        let mut result_data = Vec::with_capacity_in(val.1.len(), self.allocator.clone());
154        result_data.extend(val.1.iter().copied());
155        RustBigint(val.0, result_data)
156    }
157
158    fn add_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) {
159        match (lhs, rhs) {
160            (RustBigint(false, lhs_val), RustBigint(false, rhs_val)) |
161            (RustBigint(true, lhs_val), RustBigint(true, rhs_val)) => {
162                bigint_add(lhs_val, rhs_val, 0);
163            },
164            (RustBigint(lhs_sgn, lhs_val), RustBigint(_, rhs_val)) => {
165                match bigint_cmp(lhs_val, rhs_val) {
166                    Less => {
167                        bigint_sub_self(lhs_val, rhs_val);
168                        *lhs_sgn = !*lhs_sgn;
169                    },
170                    Equal => {
171                        lhs_val.clear();
172                    },
173                    Greater => {
174                        bigint_sub(lhs_val, rhs_val, 0);
175                    }
176                }
177            }
178        }
179    }
180
181    fn add_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) {
182        self.add_assign_ref(lhs, &rhs);
183    }
184
185    fn sub_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) { 
186        self.negate_inplace(lhs);
187        self.add_assign_ref(lhs, rhs);
188        self.negate_inplace(lhs);
189    }
190
191    fn negate_inplace(&self, lhs: &mut Self::Element) {
192        lhs.0 = !lhs.0;
193    }
194
195    fn mul_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) {
196        self.mul_assign_ref(lhs, &rhs);
197    }
198
199    fn mul_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) {
200        let result = bigint_fma(&lhs.1, &rhs.1, Vec::new_in(self.allocator.clone()), &self.allocator);
201        *lhs = RustBigint(lhs.0 ^ rhs.0, result);
202    }
203
204    fn fma(&self, lhs: &Self::Element, rhs: &Self::Element, summand: Self::Element) -> Self::Element {
205        if lhs.0 ^ rhs.0 == summand.0 {
206            let result = bigint_fma(&lhs.1, &rhs.1, summand.1, &self.allocator);
207            RustBigint(summand.0, result)
208        } else {
209            self.add(summand, self.mul_ref(lhs, rhs))
210        }
211    }
212
213    fn mul_int(&self, mut lhs: Self::Element, rhs: i32) -> Self::Element {
214        lhs.0 ^= rhs < 0;
215        let rhs = rhs.unsigned_abs();
216        bigint_mul_small(&mut lhs.1, rhs.into());
217        return lhs;
218    }
219
220    fn zero(&self) -> Self::Element {
221        RustBigint(false, Vec::new_in(self.allocator.clone()))
222    }
223
224    fn from_int(&self, value: i32) -> Self::Element {
225        let mut data = Vec::with_capacity_in(1, self.allocator.clone());
226        data.push(value.unsigned_abs() as u64);
227        RustBigint(value < 0, data)
228    }
229
230    fn eq_el(&self, lhs: &Self::Element, rhs: &Self::Element) -> bool {
231        if lhs.0 == rhs.0 {
232            bigint_cmp(&lhs.1, &rhs.1) == Equal
233        } else {
234            self.is_zero(lhs) && self.is_zero(rhs)
235        }
236    }
237
238    fn is_zero(&self, value: &Self::Element) -> bool {
239        highest_set_block(&value.1).is_none()
240    }
241
242    fn is_one(&self, value: &Self::Element) -> bool {
243        value.0 == false && highest_set_block(&value.1) == Some(0) && value.1[0] == 1
244    }
245
246    fn is_neg_one(&self, value: &Self::Element) -> bool {
247        value.0 == true && highest_set_block(&value.1) == Some(0) && value.1[0] == 1
248    }
249
250    fn is_commutative(&self) -> bool { true }
251    fn is_noetherian(&self) -> bool { true }
252    
253    fn dbg_within<'a>(&self, value: &Self::Element, out: &mut std::fmt::Formatter<'a>, _: EnvBindingStrength) -> std::fmt::Result {
254        ///
255        /// 10 to this power fits still in a u64
256        /// 
257        const BIG_POWER_TEN_ZEROS: usize = 19;
258        const BIG_POWER_TEN: u64 = 10u64.pow(BIG_POWER_TEN_ZEROS as u32);
259
260        if value.0 {
261            write!(out, "-")?;
262        }
263        let mut copy = value.clone();
264        let mut remainders: Vec<u64> = Vec::with_capacity(
265            (highest_set_block(&value.1).unwrap_or(0) + 1) * u64::BITS as usize / 3
266        );
267        while !self.is_zero(&copy) {
268            let rem = bigint_div_small(&mut copy.1, BIG_POWER_TEN);
269            remainders.push(rem);
270        }
271        remainders.reverse();
272        let mut it = remainders.into_iter();
273        if let Some(fst) = it.next() {
274            write!(out, "{}", fst)?;
275            for rem in it {
276                write!(out, "{:0>width$}", rem, width = BIG_POWER_TEN_ZEROS)?;
277            }
278        } else {
279            write!(out, "0")?;
280        }
281        return Ok(());
282    }
283
284    fn characteristic<I: IntegerRingStore + Copy>(&self, other_ZZ: I) -> Option<El<I>>
285        where I::Type: IntegerRing
286    {
287        Some(other_ZZ.zero())
288    }
289    
290    fn is_approximate(&self) -> bool { false }
291}
292
293impl<A1: Allocator + Clone, A2: Allocator + Clone> IntCast<RustBigintRingBase<A2>> for RustBigintRingBase<A1> {
294    
295    fn cast(&self, _: &RustBigintRingBase<A2>, value: RustBigint<A2>) -> Self::Element {
296        // allocate it with our allocator
297        let mut result_data = Vec::with_capacity_in(value.1.len(), self.allocator.clone());
298        result_data.extend(value.1.iter().copied());
299        RustBigint(value.0, result_data)
300    }
301}
302
303macro_rules! specialize_int_cast {
304    ($($from:ty),*) => {
305        $(
306            impl<A: Allocator + Clone> IntCast<StaticRingBase<$from>> for RustBigintRingBase<A> {
307
308                fn cast(&self, _: &StaticRingBase<$from>, value: $from) -> RustBigint<A> {
309                    let negative = value < 0;
310                    let value = <_ as Into<i128>>::into(value).checked_abs().map(|x| x as u128).unwrap_or(1 << (u128::BITS - 1));
311                    let mut result = Vec::with_capacity_in(2, self.allocator.clone());
312                    result.extend([(value & ((1 << u64::BITS) - 1)) as u64, (value >> u64::BITS) as u64].into_iter());
313                    RustBigint(negative, result)
314                }
315            }
316
317            impl<A: Allocator + Clone> IntCast<RustBigintRingBase<A>> for StaticRingBase<$from> {
318
319                fn cast(&self, from: &RustBigintRingBase<A>, value: RustBigint<A>) -> $from {
320                    <$from>::try_from(from.map_i128(&value).expect(concat!("integer does not fit into a ", stringify!($from)))).ok().expect(concat!("integer does not fit into a ", stringify!($from)))
321                }
322            }
323        )*
324    };
325}
326
327specialize_int_cast!{ i8, i16, i32, i64, i128 }
328
329impl<A: Allocator + Clone> Domain for RustBigintRingBase<A> {}
330
331impl<A: Allocator + Clone> OrderedRing for RustBigintRingBase<A> {
332
333    fn cmp(&self, lhs: &Self::Element, rhs: &Self::Element) -> Ordering {
334        match (lhs.0, rhs.0) {
335            (true, true) => bigint_cmp(&rhs.1, &lhs.1),
336            (false, false) => bigint_cmp(&lhs.1, &rhs.1),
337            (_, _) if self.is_zero(lhs) && self.is_zero(rhs) => Equal,
338            (true, false) => Less,
339            (false, true) => Greater
340        }
341    }
342
343    fn abs_cmp(&self, lhs: &Self::Element, rhs: &Self::Element) -> Ordering {
344        bigint_cmp(&lhs.1, &rhs.1)
345    }
346}
347
348impl<A: Allocator + Clone> DivisibilityRing for RustBigintRingBase<A> {
349    
350    fn checked_left_div(&self, lhs: &Self::Element, rhs: &Self::Element) -> Option<Self::Element> {
351        if self.is_zero(rhs) && self.is_zero(lhs) {
352            return Some(self.zero());
353        } else if self.is_zero(rhs) {
354            return None;
355        }
356        let (quo, rem) = self.euclidean_div_rem(lhs.clone(), rhs);
357        if self.is_zero(&rem) {
358            Some(quo)
359        } else {
360            None
361        }
362    }
363
364    fn balance_factor<'a, I>(&self, elements: I) -> Option<Self::Element>
365        where I: Iterator<Item = &'a Self::Element>,
366            Self: 'a
367    {
368        Some(elements.fold(self.zero(), |a, b| self.ideal_gen(&a, b)))
369    }
370}
371
372impl<A: Allocator + Clone> PrincipalIdealRing for RustBigintRingBase<A> {
373
374    fn checked_div_min(&self, lhs: &Self::Element, rhs: &Self::Element) -> Option<Self::Element> {
375        if self.is_zero(lhs) && self.is_zero(rhs) {
376            return Some(self.one());
377        }
378        self.checked_left_div(lhs, rhs)
379    }
380    
381    fn extended_ideal_gen(&self, lhs: &Self::Element, rhs: &Self::Element) -> (Self::Element, Self::Element, Self::Element) {
382        algorithms::eea::eea(self.clone_el(lhs), self.clone_el(rhs), RingRef::new(self))
383    }
384}
385
386impl<A: Allocator + Clone> EuclideanRing for RustBigintRingBase<A> {
387
388    fn euclidean_div_rem(&self, mut lhs: Self::Element, rhs: &Self::Element) -> (Self::Element, Self::Element) {
389        assert!(!self.is_zero(rhs));
390        let mut quo = RustBigint(false, bigint_div(&mut lhs.1, &rhs.1, self.zero().1, &self.allocator));
391        if rhs.0 ^ lhs.0 {// if result of division is zero, `.is_neg(&lhs)` does not work as expected
392            self.negate_inplace(&mut quo);
393        }
394        return (quo, lhs);
395    }
396
397    fn euclidean_deg(&self, val: &Self::Element) -> Option<usize> {
398        self.map_i128(val).and_then(|x| x.checked_abs()).and_then(|x| usize::try_from(x).ok())
399    }
400}
401
402impl<A: Allocator + Clone> HashableElRing for RustBigintRingBase<A> {
403
404    fn hash<H: std::hash::Hasher>(&self, el: &Self::Element, h: &mut H) {
405        let block = highest_set_block(&el.1);
406        if let Some(b) = block {
407            for i in 0..=b {
408                h.write_u64(el.1[i])
409            }
410        }
411    }
412}
413
414impl Serialize for RustBigintRingBase<Global> {
415
416    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
417        where S: Serializer
418    {
419        SerializableNewtypeStruct::new("IntegerRing(RustBigInt)", ()).serialize(serializer)
420    }
421}
422
423impl<'de> Deserialize<'de> for RustBigintRingBase<Global> {
424
425    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
426        where D: Deserializer<'de>
427    {
428        DeserializeSeedNewtypeStruct::new("IntegerRing(RustBigInt)", PhantomData::<()>).deserialize(deserializer).map(|_| RustBigintRing::RING.into())
429    }
430}
431
432impl<A: Allocator + Clone> SerializableElementRing for RustBigintRingBase<A> {
433
434    fn deserialize<'de, D>(&self, deserializer: D) -> Result<Self::Element, D::Error>
435        where D: Deserializer<'de>
436    {
437        if deserializer.is_human_readable() {
438            // this makes an unnecessary temporary allocation, but then the cost is probably negligible compared
439            // to the parsing of a string as a number
440            let string = DeserializeSeedNewtypeStruct::new("BigInt", PhantomData::<String>).deserialize(deserializer)?;
441            return self.parse(string.as_str(), 10).map_err(|()| de::Error::custom(format!("cannot parse \"{}\" as number", string)));
442        } else {
443            let (negative, data) = deserialize_bigint_from_bytes(deserializer, |data| {
444                let mut result_data = Vec::with_capacity_in((data.len() - 1) / size_of::<u64>() + 1, self.allocator.clone());
445                let (chunks, last) = data.as_chunks();
446                for digit in chunks {
447                    result_data.push(u64::from_le_bytes(*digit));
448                }
449                result_data.push(u64::from_le_bytes(std::array::from_fn(|i| if i >= last.len() { 0 } else { last[i] })));
450                return result_data;
451            })?;
452            return Ok(RustBigint(negative, data));
453        }
454    }
455
456    fn serialize<S>(&self, el: &Self::Element, serializer: S) -> Result<S::Ok, S::Error>
457        where S: Serializer
458    {
459        if serializer.is_human_readable() {
460            SerializableNewtypeStruct::new("BigInt", format!("{}", RingRef::new(self).format(el)).as_str()).serialize(serializer)
461        } else {
462            let len = highest_set_block(&el.1).map(|n| n + 1).unwrap_or(0);
463            let mut data = Vec::with_capacity_in(len * size_of::<u64>(), &self.allocator);
464            for digit in &el.1 {
465                data.extend(digit.to_le_bytes().into_iter());
466            }
467            let mut seq = serializer.serialize_tuple(2)?;
468            seq.serialize_element(&self.is_neg(el))?;
469            seq.serialize_element(serde_bytes::Bytes::new(&data[..]))?;
470            return seq.end();
471        }
472    }
473}
474
475impl_interpolation_base_ring_char_zero!{ <{A}> InterpolationBaseRing for RustBigintRingBase<A> where A: Allocator + Clone }
476
477impl_poly_gcd_locally_for_ZZ!{ <{A}> IntegerPolyGCDRing for RustBigintRingBase<A> where A: Allocator + Clone }
478
479impl_eval_poly_locally_for_ZZ!{ <{A}> EvalPolyLocallyRing for RustBigintRingBase<A> where A: Allocator + Clone }
480
481impl<A> FiniteRingSpecializable for RustBigintRingBase<A>
482    where A: Allocator + Clone
483{
484    fn specialize<O: FiniteRingOperation<Self>>(op: O) -> O::Output {
485        op.fallback()
486    }
487}
488
489impl<A: Allocator + Clone> IntegerRing for RustBigintRingBase<A> {
490
491    fn to_float_approx(&self, value: &Self::Element) -> f64 {
492        let sign = if value.0 { -1. } else { 1. };
493        match highest_set_block(&value.1) {
494            None => 0.,
495            Some(0) => value.1[0] as f64 * sign,
496            Some(d) => (value.1[d] as f64 * 2f64.powi((d * u64::BITS as usize).try_into().unwrap()) + value.1[d - 1] as f64 * 2f64.powi(((d - 1) * u64::BITS as usize).try_into().unwrap())) * sign
497        }
498    }
499
500    fn from_float_approx(&self, mut value: f64) -> Option<Self::Element> {
501        if value.round() == 0. {
502            return Some(self.zero());
503        }
504        let sign = value < 0.;
505        value = value.abs();
506        let scale: i32 = (value.log2().ceil() as i64).try_into().unwrap();
507        let significant_digits = std::cmp::min(scale, u64::BITS.try_into().unwrap());
508        let most_significant_bits = (value / 2f64.powi(scale - significant_digits)) as u64;
509        let mut result = self.one();
510        result.1[0] = most_significant_bits;
511        result.0 = sign;
512        self.mul_pow_2(&mut result, (scale - significant_digits) as usize);
513        return Some(result);
514    }
515
516    fn abs_lowest_set_bit(&self, value: &Self::Element) -> Option<usize> {
517        if self.is_zero(value) {
518            return None;
519        }
520        for i in 0..value.1.len() {
521            if value.1[i] != 0 {
522                return Some(i * u64::BITS as usize + value.1[i].trailing_zeros() as usize)
523            }
524        }
525        unreachable!()
526    }
527
528    fn abs_is_bit_set(&self, value: &Self::Element, i: usize) -> bool {
529        if i / u64::BITS as usize >= value.1.len() {
530            false
531        } else {
532            (value.1[i / u64::BITS as usize] >> (i % u64::BITS as usize)) & 1 == 1
533        }
534    }
535
536    fn abs_highest_set_bit(&self, value: &Self::Element) -> Option<usize> {
537        let block = highest_set_block(&value.1)?;
538        Some(block * u64::BITS as usize + u64::BITS as usize - value.1[block].leading_zeros() as usize - 1)
539    }
540
541    fn euclidean_div_pow_2(&self, value: &mut Self::Element, power: usize) {
542        bigint_rshift(&mut value.1, power);
543    }
544
545    fn mul_pow_2(&self, value: &mut Self::Element, power: usize) {
546        bigint_lshift(&mut value.1, power)
547    }
548
549    fn get_uniformly_random_bits<G: FnMut() -> u64>(&self, log2_bound_exclusive: usize, mut rng: G) -> Self::Element {
550        let blocks = log2_bound_exclusive / u64::BITS as usize;
551        let in_block = log2_bound_exclusive % u64::BITS as usize;
552        let mut result = Vec::with_capacity_in(blocks + if in_block > 0 { 1 } else { 0 }, self.allocator.clone());
553        if in_block == 0 {
554            result.extend((0..blocks).map(|_| rng()));
555        } else {
556            let last = rng() & 1u64.overflowing_shl(in_block as u32).0.overflowing_sub(1).0;
557            result.extend((0..blocks).map(|_| rng()).chain(std::iter::once(last)));
558        }
559        return RustBigint(false, result);
560    }
561    
562    fn representable_bits(&self) -> Option<usize> {
563        None
564    }
565}
566
567#[cfg(test)]
568use crate::homomorphism::*;
569
570#[cfg(test)]
571const ZZ: RustBigintRing = RustBigintRing::RING;
572
573#[test]
574fn test_print_power_2() {
575    let x = RustBigint(false, vec![0, 0, 1]);
576    assert_eq!("340282366920938463463374607431768211456", format!("{}", RustBigintRing::RING.format(&x)));
577}
578
579#[test]
580fn test_from() {
581    assert!(ZZ.eq_el(&RustBigint(false, vec![]), &ZZ.int_hom().map(0)));
582    assert!(ZZ.eq_el(&RustBigint(false, vec![2138479]), &ZZ.int_hom().map(2138479)));
583    assert!(ZZ.eq_el(&RustBigint(true, vec![2138479]), &ZZ.int_hom().map(-2138479)));
584    // assert!(ZZ.eq(&RustBigint(false, vec![0x38691a350bf12fca, 0x1]), &ZZ.from_z_gen(0x138691a350bf12fca, &i128::RING)));
585}
586
587#[test]
588fn test_to_i128() {
589    let iso = ZZ.can_iso(&StaticRing::<i128>::RING).unwrap();
590    assert_eq!(0, iso.map(RustBigint(false, vec![])));
591    assert_eq!(2138479, iso.map(RustBigint(false, vec![2138479])));
592    assert_eq!(-2138479, iso.map(RustBigint(true, vec![2138479])));
593    assert_eq!(0x138691a350bf12fca, iso.map(RustBigint(false, vec![0x38691a350bf12fca, 0x1])));
594    assert_eq!(i128::MAX, iso.map(RustBigint(false, vec![(i128::MAX & ((1 << 64) - 1)) as u64, (i128::MAX >> 64) as u64])));
595    assert_eq!(i128::MIN + 1, iso.map(RustBigint(true, vec![(i128::MAX & ((1 << 64) - 1)) as u64, (i128::MAX >> 64) as u64])));
596    assert_eq!(i64::MAX as i128 + 1, iso.map(RustBigint(false, vec![i64::MAX as u64 + 1])));
597    assert_eq!(u64::MAX as i128, iso.map(RustBigint(false, vec![u64::MAX])));
598}
599
600#[test]
601fn test_sub_assign() {
602    let mut x = RustBigintRing::RING.get_ring().parse("4294836225", 10).unwrap();
603    let y = RustBigintRing::RING.get_ring().parse("4294967297", 10).unwrap();
604    let z = RustBigintRing::RING.get_ring().parse("-131072", 10).unwrap();
605    x = ZZ.sub_ref_fst(&x, y);
606    assert!(ZZ.eq_el(&z, &x));
607}
608
609#[test]
610fn test_assumptions_integer_division() {
611    assert_eq!(-1, -3 / 2);
612    assert_eq!(-1, 3 / -2);
613    assert_eq!(1, -3 / -2);
614    assert_eq!(1, 3 / 2);
615
616    assert_eq!(-1, -3 % 2);
617    assert_eq!(1, 3 % -2);
618    assert_eq!(-1, -3 % -2);
619    assert_eq!(1, 3 % 2);
620}
621
622#[cfg(test)]
623fn edge_case_elements() -> impl Iterator<Item = RustBigint> {
624    
625    const NUMBERS: [&'static str; 10] = [
626        "5444517870735015415413993718908291383295", // power of two - 1
627        "5444517870735015415413993718908291383296", // power of two
628        "-5444517870735015415413993718908291383295",
629        "-5444517870735015415413993718908291383296",
630        "3489", // the rest is random
631        "891023591340178345678931246518793456983745682137459364598623489512389745698237456890239238476873429872346579",
632        "172365798123602365091834765607185713205612370956192783561461248973265193754762751378496572896497125361819754136",
633        "0",
634        "-231780567812394562346324763251741827457123654871236548715623487612384752328164",
635        "+1278367182354612381234568509783420989356938472561078564732895634928563482349872698723465"
636    ];
637
638    NUMBERS.iter().cloned().map(|s| RustBigintRing::RING.get_ring().parse(s, 10)).map(Result::unwrap)
639}
640
641#[test]
642fn test_bigint_ring_axioms() {
643    crate::ring::generic_tests::test_ring_axioms(ZZ, edge_case_elements())
644}
645
646#[test]
647fn test_hash_axioms() {
648    crate::ring::generic_tests::test_hash_axioms(ZZ, edge_case_elements());
649}
650
651#[test]
652fn test_bigint_divisibility_ring_axioms() {
653    crate::divisibility::generic_tests::test_divisibility_axioms(ZZ, edge_case_elements())
654}
655
656#[test]
657fn test_bigint_euclidean_ring_axioms() {
658    crate::pid::generic_tests::test_euclidean_ring_axioms(ZZ, edge_case_elements());
659}
660
661#[test]
662fn test_bigint_principal_ideal_ring_axioms() {
663    crate::pid::generic_tests::test_principal_ideal_ring_axioms(ZZ, edge_case_elements());
664}
665
666#[test]
667fn test_bigint_integer_ring_axioms() {
668    crate::integer::generic_tests::test_integer_axioms(ZZ, edge_case_elements())
669}
670
671#[test]
672fn from_to_float_approx() {
673    let x: f64 = 83465209236517892563478156042389675783219532497861237985328563.;
674    let y = ZZ.to_float_approx(&ZZ.from_float_approx(x).unwrap());
675    assert!(x * 0.99999 < y);
676    assert!(y < x * 1.00001);
677
678    let x = RustBigintRing::RING.get_ring().parse("238238568756187236598172345698172345698713465983465981349196413289715928374691873256349862875423823856875618723659817234569817234569871346598346598134919641328971592837469187325634986287542382385687561872365981723456981723456987134659834659813491964132897159283746918732563498628754", 10).unwrap();
679    let x_f64 = RustBigintRing::RING.to_float_approx(&x);
680    assert!(x_f64 > 2.38e281);
681    assert!(x_f64 < 2.39e281);
682    
683    let x = RustBigintRing::RING.get_ring().parse("17612270634266603266562983043609488425884596885216274157019263443846280837737053004240660825056953589054705681188523315954751538958870401258595088307206392227789986855433848759623746265294744028223494023320398812305222823465701205669244602427862540158018457529069827142861864092328740970800137803882190383463", 10).unwrap();
684    let x_f64 = RustBigintRing::RING.to_float_approx(&x);
685    assert!(x_f64 > 1.76e307);
686    assert!(x_f64 < 1.77e307);
687}
688
689#[bench]
690fn bench_div_300_bits(bencher: &mut test::Bencher) {
691    let x = RustBigintRing::RING.get_ring().parse("2382385687561872365981723456981723456987134659834659813491964132897159283746918732563498628754", 10).unwrap();
692    let y = RustBigintRing::RING.get_ring().parse("48937502893645789234569182735646324895723409587234", 10).unwrap();
693    let z = RustBigintRing::RING.get_ring().parse("48682207850683149082203680872586784064678018", 10).unwrap();
694    bencher.iter(|| {
695        let q = ZZ.euclidean_div(x.clone(), &y);
696        assert!(ZZ.eq_el(&z, &q));
697    })
698}
699
700#[bench]
701fn bench_mul_300_bits(bencher: &mut test::Bencher) {
702    let x = RustBigintRing::RING.get_ring().parse("2382385687561872365981723456981723456987134659834659813491964132897159283746918732563498628754", 10).unwrap();
703    let y = RustBigintRing::RING.get_ring().parse("48937502893645789234569182735646324895723409587234", 10).unwrap();
704    let z = RustBigintRing::RING.get_ring().parse("116588006478839442056346504147013274749794691549803163727888681858469844569693215953808606899770104590589390919543097259495176008551856143726436", 10).unwrap();
705    bencher.iter(|| {
706        let p = ZZ.mul_ref(&x, &y);
707        assert!(ZZ.eq_el(&z, &p));
708    })
709}
710
711#[test]
712fn test_is_zero() {
713    let zero = ZZ.zero();
714    let mut nonzero = ZZ.one();
715    ZZ.mul_pow_2(&mut nonzero, 83124);
716    assert!(ZZ.is_zero(&zero));
717    assert!(ZZ.is_zero(&ZZ.negate(zero)));
718    assert!(!ZZ.is_zero(&nonzero));
719    assert!(!ZZ.is_zero(&ZZ.negate(nonzero)));
720}
721
722#[test]
723fn test_cmp() {
724    assert_eq!(true, ZZ.is_lt(&ZZ.int_hom().map(-1), &ZZ.int_hom().map(2)));
725    assert_eq!(true, ZZ.is_lt(&ZZ.int_hom().map(1), &ZZ.int_hom().map(2)));
726    assert_eq!(false, ZZ.is_lt(&ZZ.int_hom().map(2), &ZZ.int_hom().map(2)));
727    assert_eq!(false, ZZ.is_lt(&ZZ.int_hom().map(3), &ZZ.int_hom().map(2)));
728    assert_eq!(true, ZZ.is_gt(&ZZ.int_hom().map(-1), &ZZ.int_hom().map(-2)));
729
730    assert_eq!(Ordering::Less, ZZ.abs_cmp(&ZZ.int_hom().map(-1), &ZZ.int_hom().map(2)));
731    assert_eq!(Ordering::Less, ZZ.abs_cmp(&ZZ.int_hom().map(1), &ZZ.int_hom().map(2)));
732    assert_eq!(Ordering::Equal, ZZ.abs_cmp(&ZZ.int_hom().map(2), &ZZ.int_hom().map(2)));
733    assert_eq!(Ordering::Greater, ZZ.abs_cmp(&ZZ.int_hom().map(-3), &ZZ.int_hom().map(2)));
734    assert_eq!(Ordering::Greater, ZZ.abs_cmp(&ZZ.int_hom().map(3), &ZZ.int_hom().map(2)));
735    assert_eq!(Ordering::Less, ZZ.abs_cmp(&ZZ.int_hom().map(-1), &ZZ.int_hom().map(-2)));
736}
737
738#[test]
739fn test_get_uniformly_random() {
740    crate::integer::generic_tests::test_integer_get_uniformly_random(ZZ);
741
742    let ring = ZZ;
743    let bound = RustBigintRing::RING.get_ring().parse("11000000000000000", 16).unwrap();
744    let block_bound = RustBigintRing::RING.get_ring().parse("10000000000000000", 16).unwrap();
745    let mut rng = oorandom::Rand64::new(1);
746    let elements: Vec<_> = (0..1000).map(|_| ring.get_uniformly_random(&bound, || rng.rand_u64())).collect();
747    assert!(elements.iter().any(|x| ring.is_lt(x, &block_bound)));
748    assert!(elements.iter().any(|x| ring.is_gt(x, &block_bound)));
749    assert!(elements.iter().all(|x| ring.is_lt(x, &bound)));
750}
751
752#[test]
753fn test_canonical_iso_static_int() {
754    // for the hom test, we have to be able to multiply elements in `StaticRing::<i128>::RING`, so we cannot test `i128::MAX` or `i128::MIN`
755    crate::ring::generic_tests::test_hom_axioms(StaticRing::<i128>::RING, ZZ, [0, 1, -1, -100, 100, i64::MAX as i128, i64::MIN as i128].iter().copied());
756    crate::ring::generic_tests::test_iso_axioms(StaticRing::<i128>::RING, ZZ, [0, 1, -1, -100, 100, i64::MAX as i128, i64::MIN as i128, i128::MAX, i128::MIN].iter().copied());
757}
758
759#[test]
760fn test_serialize() {
761    crate::serialization::generic_tests::test_serialization(ZZ, edge_case_elements())
762}
763
764#[test]
765fn test_serialize_postcard() {
766    let serialized = postcard::to_allocvec(&SerializeWithRing::new(&ZZ.power_of_two(10000), ZZ)).unwrap();
767    let result = DeserializeWithRing::new(ZZ).deserialize(
768        &mut postcard::Deserializer::from_flavor(postcard::de_flavors::Slice::new(&serialized))
769    ).unwrap();
770
771    assert_el_eq!(ZZ, ZZ.power_of_two(10000), result);
772}
feanor_math/rings/rust_bigint.rs

feanor_math/rings/
rust_bigint.rs
