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

feanor_math/rings/
rust_bigint.rs
