feanor_math/rings/
rust_bigint.rs

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

feanor_math/rings/
rust_bigint.rs
