feanor_math/rings/
rust_bigint.rs

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

feanor_math/rings/
rust_bigint.rs
