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                if data.len() == 0 {
417                    Vec::new_in(self.allocator.clone())
418                } else {
419                    let mut result_data =
420                        Vec::with_capacity_in((data.len() - 1) / size_of::<u64>() + 1, self.allocator.clone());
421                    let (chunks, last) = data.as_chunks();
422                    for digit in chunks {
423                        result_data.push(u64::from_le_bytes(*digit));
424                    }
425                    result_data.push(u64::from_le_bytes(std::array::from_fn(|i| {
426                        if i >= last.len() { 0 } else { last[i] }
427                    })));
428                    return result_data;
429                }
430            })?;
431            return Ok(RustBigint(negative, data));
432        }
433    }
434
435    fn serialize<S>(&self, el: &Self::Element, serializer: S) -> Result<S::Ok, S::Error>
436    where
437        S: Serializer,
438    {
439        if serializer.is_human_readable() {
440            SerializableNewtypeStruct::new("BigInt", format!("{}", RingRef::new(self).format(el)).as_str())
441                .serialize(serializer)
442        } else {
443            let len = highest_set_block(&el.1).map(|n| n + 1).unwrap_or(0);
444            let mut data = Vec::with_capacity_in(len * size_of::<u64>(), &self.allocator);
445            for digit in &el.1 {
446                data.extend(digit.to_le_bytes());
447            }
448            let mut seq = serializer.serialize_tuple(2)?;
449            seq.serialize_element(&self.is_neg(el))?;
450            seq.serialize_element(serde_bytes::Bytes::new(&data[..]))?;
451            return seq.end();
452        }
453    }
454}
455
456impl_interpolation_base_ring_char_zero! { <{A}> InterpolationBaseRing for RustBigintRingBase<A> where A: Allocator + Clone }
457
458impl_poly_gcd_locally_for_ZZ! { <{A}> IntegerPolyGCDRing for RustBigintRingBase<A> where A: Allocator + Clone }
459
460impl_eval_poly_locally_for_ZZ! { <{A}> EvalPolyLocallyRing for RustBigintRingBase<A> where A: Allocator + Clone }
461
462impl<A> FiniteRingSpecializable for RustBigintRingBase<A>
463where
464    A: Allocator + Clone,
465{
466    fn specialize<O: FiniteRingOperation<Self>>(op: O) -> O::Output { op.fallback() }
467}
468
469impl<A: Allocator + Clone> IntegerRing for RustBigintRingBase<A> {
470    fn to_float_approx(&self, value: &Self::Element) -> f64 {
471        let sign = if value.0 { -1.0 } else { 1.0 };
472        match highest_set_block(&value.1) {
473            None => 0.0,
474            Some(0) => value.1[0] as f64 * sign,
475            Some(d) => {
476                (value.1[d] as f64 * 2.0f64.powi((d * u64::BITS as usize).try_into().unwrap())
477                    + value.1[d - 1] as f64 * 2.0f64.powi(((d - 1) * u64::BITS as usize).try_into().unwrap()))
478                    * sign
479            }
480        }
481    }
482
483    fn from_float_approx(&self, mut value: f64) -> Option<Self::Element> {
484        if value.round() == 0.0 {
485            return Some(self.zero());
486        }
487        let sign = value < 0.0;
488        value = value.abs();
489        let scale: i32 = (value.log2().ceil() as i64).try_into().unwrap();
490        let significant_digits = std::cmp::min(scale, u64::BITS.try_into().unwrap());
491        let most_significant_bits = (value / 2.0f64.powi(scale - significant_digits)) as u64;
492        let mut result = self.one();
493        result.1[0] = most_significant_bits;
494        result.0 = sign;
495        self.mul_pow_2(&mut result, (scale - significant_digits) as usize);
496        return Some(result);
497    }
498
499    fn abs_lowest_set_bit(&self, value: &Self::Element) -> Option<usize> {
500        if self.is_zero(value) {
501            return None;
502        }
503        for i in 0..value.1.len() {
504            if value.1[i] != 0 {
505                return Some(i * u64::BITS as usize + value.1[i].trailing_zeros() as usize);
506            }
507        }
508        unreachable!()
509    }
510
511    fn abs_is_bit_set(&self, value: &Self::Element, i: usize) -> bool {
512        if i / u64::BITS as usize >= value.1.len() {
513            false
514        } else {
515            (value.1[i / u64::BITS as usize] >> (i % u64::BITS as usize)) & 1 == 1
516        }
517    }
518
519    fn abs_highest_set_bit(&self, value: &Self::Element) -> Option<usize> {
520        let block = highest_set_block(&value.1)?;
521        Some(block * u64::BITS as usize + u64::BITS as usize - value.1[block].leading_zeros() as usize - 1)
522    }
523
524    fn euclidean_div_pow_2(&self, value: &mut Self::Element, power: usize) { bigint_rshift(&mut value.1, power); }
525
526    fn mul_pow_2(&self, value: &mut Self::Element, power: usize) { bigint_lshift(&mut value.1, power) }
527
528    fn get_uniformly_random_bits<G: FnMut() -> u64>(&self, log2_bound_exclusive: usize, mut rng: G) -> Self::Element {
529        let blocks = log2_bound_exclusive / u64::BITS as usize;
530        let in_block = log2_bound_exclusive % u64::BITS as usize;
531        let mut result = Vec::with_capacity_in(blocks + if in_block > 0 { 1 } else { 0 }, self.allocator.clone());
532        if in_block == 0 {
533            result.extend((0..blocks).map(|_| rng()));
534        } else {
535            let last = rng() & 1u64.overflowing_shl(in_block as u32).0.overflowing_sub(1).0;
536            result.extend((0..blocks).map(|_| rng()).chain(std::iter::once(last)));
537        }
538        return RustBigint(false, result);
539    }
540
541    fn representable_bits(&self) -> Option<usize> { None }
542}
543
544#[cfg(test)]
545use crate::homomorphism::*;
546
547#[cfg(test)]
548const ZZ: RustBigintRing = RustBigintRing::RING;
549
550#[test]
551fn test_print_power_2() {
552    let x = RustBigint(false, vec![0, 0, 1]);
553    assert_eq!(
554        "340282366920938463463374607431768211456",
555        format!("{}", RustBigintRing::RING.format(&x))
556    );
557}
558
559#[test]
560fn test_from() {
561    assert!(ZZ.eq_el(&RustBigint(false, vec![]), &ZZ.int_hom().map(0)));
562    assert!(ZZ.eq_el(&RustBigint(false, vec![2138479]), &ZZ.int_hom().map(2138479)));
563    assert!(ZZ.eq_el(&RustBigint(true, vec![2138479]), &ZZ.int_hom().map(-2138479)));
564    // assert!(ZZ.eq(&RustBigint(false, vec![0x38691a350bf12fca, 0x1]),
565    // &ZZ.from_z_gen(0x138691a350bf12fca, &i128::RING)));
566}
567
568#[test]
569fn test_to_i128() {
570    let iso = ZZ.can_iso(&StaticRing::<i128>::RING).unwrap();
571    assert_eq!(0, iso.map(RustBigint(false, vec![])));
572    assert_eq!(2138479, iso.map(RustBigint(false, vec![2138479])));
573    assert_eq!(-2138479, iso.map(RustBigint(true, vec![2138479])));
574    assert_eq!(
575        0x138691A350BF12FCA,
576        iso.map(RustBigint(false, vec![0x38691A350BF12FCA, 0x1]))
577    );
578    assert_eq!(
579        i128::MAX,
580        iso.map(RustBigint(
581            false,
582            vec![(i128::MAX & ((1 << 64) - 1)) as u64, (i128::MAX >> 64) as u64]
583        ))
584    );
585    assert_eq!(
586        i128::MIN + 1,
587        iso.map(RustBigint(
588            true,
589            vec![(i128::MAX & ((1 << 64) - 1)) as u64, (i128::MAX >> 64) as u64]
590        ))
591    );
592    assert_eq!(
593        i64::MAX as i128 + 1,
594        iso.map(RustBigint(false, vec![i64::MAX as u64 + 1]))
595    );
596    assert_eq!(u64::MAX as i128, iso.map(RustBigint(false, vec![u64::MAX])));
597}
598
599#[test]
600fn test_sub_assign() {
601    let mut x = RustBigintRing::RING.get_ring().parse("4294836225", 10).unwrap();
602    let y = RustBigintRing::RING.get_ring().parse("4294967297", 10).unwrap();
603    let z = RustBigintRing::RING.get_ring().parse("-131072", 10).unwrap();
604    x = ZZ.sub_ref_fst(&x, y);
605    assert!(ZZ.eq_el(&z, &x));
606}
607
608#[test]
609fn test_assumptions_integer_division() {
610    assert_eq!(-1, -3 / 2);
611    assert_eq!(-1, 3 / -2);
612    assert_eq!(1, -3 / -2);
613    assert_eq!(1, 3 / 2);
614
615    assert_eq!(-1, -3 % 2);
616    assert_eq!(1, 3 % -2);
617    assert_eq!(-1, -3 % -2);
618    assert_eq!(1, 3 % 2);
619}
620
621#[cfg(test)]
622fn edge_case_elements() -> impl Iterator<Item = RustBigint> {
623    const NUMBERS: [&'static str; 10] = [
624        "5444517870735015415413993718908291383295", // power of two - 1
625        "5444517870735015415413993718908291383296", // power of two
626        "-5444517870735015415413993718908291383295",
627        "-5444517870735015415413993718908291383296",
628        "3489", // the rest is random
629        "891023591340178345678931246518793456983745682137459364598623489512389745698237456890239238476873429872346579",
630        "172365798123602365091834765607185713205612370956192783561461248973265193754762751378496572896497125361819754136",
631        "0",
632        "-231780567812394562346324763251741827457123654871236548715623487612384752328164",
633        "+1278367182354612381234568509783420989356938472561078564732895634928563482349872698723465",
634    ];
635
636    NUMBERS
637        .iter()
638        .cloned()
639        .map(|s| RustBigintRing::RING.get_ring().parse(s, 10))
640        .map(Result::unwrap)
641        .chain([RustBigint(false, vec![])])
642}
643
644#[test]
645fn test_bigint_ring_axioms() { crate::ring::generic_tests::test_ring_axioms(ZZ, edge_case_elements()) }
646
647#[test]
648fn test_hash_axioms() { crate::ring::generic_tests::test_hash_axioms(ZZ, edge_case_elements()); }
649
650#[test]
651fn test_bigint_divisibility_ring_axioms() {
652    crate::divisibility::generic_tests::test_divisibility_axioms(ZZ, edge_case_elements())
653}
654
655#[test]
656fn test_bigint_euclidean_ring_axioms() {
657    crate::pid::generic_tests::test_euclidean_ring_axioms(ZZ, edge_case_elements());
658}
659
660#[test]
661fn test_bigint_principal_ideal_ring_axioms() {
662    crate::pid::generic_tests::test_principal_ideal_ring_axioms(ZZ, edge_case_elements());
663}
664
665#[test]
666fn test_bigint_integer_ring_axioms() { crate::integer::generic_tests::test_integer_axioms(ZZ, edge_case_elements()) }
667
668#[test]
669fn from_to_float_approx() {
670    let x: f64 = 83465209236517892563478156042389675783219532497861237985328563.0;
671    let y = ZZ.to_float_approx(&ZZ.from_float_approx(x).unwrap());
672    assert!(x * 0.99999 < y);
673    assert!(y < x * 1.00001);
674
675    let x = RustBigintRing::RING.get_ring().parse("238238568756187236598172345698172345698713465983465981349196413289715928374691873256349862875423823856875618723659817234569817234569871346598346598134919641328971592837469187325634986287542382385687561872365981723456981723456987134659834659813491964132897159283746918732563498628754", 10).unwrap();
676    let x_f64 = RustBigintRing::RING.to_float_approx(&x);
677    assert!(x_f64 > 2.38e281);
678    assert!(x_f64 < 2.39e281);
679
680    let x = RustBigintRing::RING.get_ring().parse("17612270634266603266562983043609488425884596885216274157019263443846280837737053004240660825056953589054705681188523315954751538958870401258595088307206392227789986855433848759623746265294744028223494023320398812305222823465701205669244602427862540158018457529069827142861864092328740970800137803882190383463", 10).unwrap();
681    let x_f64 = RustBigintRing::RING.to_float_approx(&x);
682    assert!(x_f64 > 1.76e307);
683    assert!(x_f64 < 1.77e307);
684}
685
686#[bench]
687fn bench_div_300_bits(bencher: &mut test::Bencher) {
688    let x = RustBigintRing::RING
689        .get_ring()
690        .parse(
691            "2382385687561872365981723456981723456987134659834659813491964132897159283746918732563498628754",
692            10,
693        )
694        .unwrap();
695    let y = RustBigintRing::RING
696        .get_ring()
697        .parse("48937502893645789234569182735646324895723409587234", 10)
698        .unwrap();
699    let z = RustBigintRing::RING
700        .get_ring()
701        .parse("48682207850683149082203680872586784064678018", 10)
702        .unwrap();
703    bencher.iter(|| {
704        let q = ZZ.euclidean_div(x.clone(), &y);
705        assert!(ZZ.eq_el(&z, &q));
706    })
707}
708
709#[bench]
710fn bench_mul_300_bits(bencher: &mut test::Bencher) {
711    let x = RustBigintRing::RING
712        .get_ring()
713        .parse(
714            "2382385687561872365981723456981723456987134659834659813491964132897159283746918732563498628754",
715            10,
716        )
717        .unwrap();
718    let y = RustBigintRing::RING
719        .get_ring()
720        .parse("48937502893645789234569182735646324895723409587234", 10)
721        .unwrap();
722    let z = RustBigintRing::RING.get_ring().parse("116588006478839442056346504147013274749794691549803163727888681858469844569693215953808606899770104590589390919543097259495176008551856143726436", 10).unwrap();
723    bencher.iter(|| {
724        let p = ZZ.mul_ref(&x, &y);
725        assert!(ZZ.eq_el(&z, &p));
726    })
727}
728
729#[test]
730fn test_is_zero() {
731    let zero = ZZ.zero();
732    let mut nonzero = ZZ.one();
733    ZZ.mul_pow_2(&mut nonzero, 83124);
734    assert!(ZZ.is_zero(&zero));
735    assert!(ZZ.is_zero(&ZZ.negate(zero)));
736    assert!(!ZZ.is_zero(&nonzero));
737    assert!(!ZZ.is_zero(&ZZ.negate(nonzero)));
738}
739
740#[test]
741fn test_cmp() {
742    assert_eq!(true, ZZ.is_lt(&ZZ.int_hom().map(-1), &ZZ.int_hom().map(2)));
743    assert_eq!(true, ZZ.is_lt(&ZZ.int_hom().map(1), &ZZ.int_hom().map(2)));
744    assert_eq!(false, ZZ.is_lt(&ZZ.int_hom().map(2), &ZZ.int_hom().map(2)));
745    assert_eq!(false, ZZ.is_lt(&ZZ.int_hom().map(3), &ZZ.int_hom().map(2)));
746    assert_eq!(true, ZZ.is_gt(&ZZ.int_hom().map(-1), &ZZ.int_hom().map(-2)));
747
748    assert_eq!(Ordering::Less, ZZ.abs_cmp(&ZZ.int_hom().map(-1), &ZZ.int_hom().map(2)));
749    assert_eq!(Ordering::Less, ZZ.abs_cmp(&ZZ.int_hom().map(1), &ZZ.int_hom().map(2)));
750    assert_eq!(Ordering::Equal, ZZ.abs_cmp(&ZZ.int_hom().map(2), &ZZ.int_hom().map(2)));
751    assert_eq!(
752        Ordering::Greater,
753        ZZ.abs_cmp(&ZZ.int_hom().map(-3), &ZZ.int_hom().map(2))
754    );
755    assert_eq!(
756        Ordering::Greater,
757        ZZ.abs_cmp(&ZZ.int_hom().map(3), &ZZ.int_hom().map(2))
758    );
759    assert_eq!(Ordering::Less, ZZ.abs_cmp(&ZZ.int_hom().map(-1), &ZZ.int_hom().map(-2)));
760}
761
762#[test]
763fn test_get_uniformly_random() {
764    crate::integer::generic_tests::test_integer_get_uniformly_random(ZZ);
765
766    let ring = ZZ;
767    let bound = RustBigintRing::RING.get_ring().parse("11000000000000000", 16).unwrap();
768    let block_bound = RustBigintRing::RING.get_ring().parse("10000000000000000", 16).unwrap();
769    let mut rng = oorandom::Rand64::new(1);
770    let elements: Vec<_> = (0..1000)
771        .map(|_| ring.get_uniformly_random(&bound, || rng.rand_u64()))
772        .collect();
773    assert!(elements.iter().any(|x| ring.is_lt(x, &block_bound)));
774    assert!(elements.iter().any(|x| ring.is_gt(x, &block_bound)));
775    assert!(elements.iter().all(|x| ring.is_lt(x, &bound)));
776}
777
778#[test]
779fn test_canonical_iso_static_int() {
780    // for the hom test, we have to be able to multiply elements in `StaticRing::<i128>::RING`, so
781    // we cannot test `i128::MAX` or `i128::MIN`
782    crate::ring::generic_tests::test_hom_axioms(
783        StaticRing::<i128>::RING,
784        ZZ,
785        [0, 1, -1, -100, 100, i64::MAX as i128, i64::MIN as i128]
786            .iter()
787            .copied(),
788    );
789    crate::ring::generic_tests::test_iso_axioms(
790        StaticRing::<i128>::RING,
791        ZZ,
792        [
793            0,
794            1,
795            -1,
796            -100,
797            100,
798            i64::MAX as i128,
799            i64::MIN as i128,
800            i128::MAX,
801            i128::MIN,
802        ]
803        .iter()
804        .copied(),
805    );
806}
807
808#[test]
809fn test_serialize() { crate::serialization::generic_tests::test_serialization(ZZ, edge_case_elements()) }
810
811#[test]
812fn test_serialize_postcard() {
813    let serialized = postcard::to_allocvec(&SerializeWithRing::new(&ZZ.power_of_two(10000), ZZ)).unwrap();
814    let result = DeserializeWithRing::new(ZZ)
815        .deserialize(&mut postcard::Deserializer::from_flavor(
816            postcard::de_flavors::Slice::new(&serialized),
817        ))
818        .unwrap();
819
820    assert_el_eq!(ZZ, ZZ.power_of_two(10000), result);
821}
feanor_math/rings/rust_bigint.rs

feanor_math/rings/
rust_bigint.rs
