feanor_math/
primitive_int.rs

1use std::any::TypeId;
2use std::fmt::{Debug, Display};
3use std::marker::PhantomData;
4use std::ops::{AddAssign, Div, MulAssign, Neg, Rem, Shr, SubAssign};
5
6use feanor_serde::newtype_struct::{DeserializeSeedNewtypeStruct, SerializableNewtypeStruct};
7use serde::de::{DeserializeOwned, DeserializeSeed};
8use serde::{Deserialize, Deserializer, Serialize, Serializer};
9
10use crate::algorithms::convolution::KaratsubaHint;
11use crate::algorithms::matmul::StrassenHint;
12use crate::divisibility::*;
13use crate::homomorphism::*;
14use crate::integer::*;
15use crate::ordered::*;
16use crate::pid::{EuclideanRing, PrincipalIdealRing};
17use crate::ring::*;
18use crate::serialization::SerializableElementRing;
19use crate::specialization::*;
20use crate::{
21    algorithms, impl_eval_poly_locally_for_ZZ, impl_interpolation_base_ring_char_zero, impl_poly_gcd_locally_for_ZZ,
22};
23
24/// Trait for `i8` to `i128`.
25pub trait PrimitiveInt:
26    'static
27    + Send
28    + Sync
29    + Serialize
30    + DeserializeOwned
31    + AddAssign
32    + SubAssign
33    + MulAssign
34    + Neg<Output = Self>
35    + Shr<usize, Output = Self>
36    + Eq
37    + Into<Self::Larger>
38    + TryFrom<Self::Larger>
39    + From<i8>
40    + TryFrom<i32>
41    + TryFrom<i128>
42    + Into<i128>
43    + Copy
44    + Div<Self, Output = Self>
45    + Rem<Self, Output = Self>
46    + Display
47{
48    /// The primitive integer that is "twice as large" as this one.
49    /// The only exception is `i128`, for which there is no larger primitive integer.
50    type Larger: PrimitiveInt;
51
52    /// Returns the number of bits of this integer type.
53    fn bits() -> usize;
54
55    /// The functions [`i8::overflowing_mul()`] to [`i128::overflowing_mul()`].
56    fn overflowing_mul(self, rhs: Self) -> Self;
57
58    /// The functions [`i8::overflowing_sub()`] to [`i128::overflowing_sub()`].
59    fn overflowing_sub(self, rhs: Self) -> Self;
60}
61
62impl PrimitiveInt for i8 {
63    type Larger = i16;
64
65    fn bits() -> usize { Self::BITS as usize }
66    fn overflowing_mul(self, rhs: Self) -> Self { i8::overflowing_mul(self, rhs).0 }
67    fn overflowing_sub(self, rhs: Self) -> Self { i8::overflowing_sub(self, rhs).0 }
68}
69
70impl PrimitiveInt for i16 {
71    type Larger = i32;
72
73    fn bits() -> usize { Self::BITS as usize }
74    fn overflowing_mul(self, rhs: Self) -> Self { i16::overflowing_mul(self, rhs).0 }
75    fn overflowing_sub(self, rhs: Self) -> Self { i16::overflowing_sub(self, rhs).0 }
76}
77
78impl PrimitiveInt for i32 {
79    type Larger = i64;
80
81    fn bits() -> usize { Self::BITS as usize }
82    fn overflowing_mul(self, rhs: Self) -> Self { i32::overflowing_mul(self, rhs).0 }
83    fn overflowing_sub(self, rhs: Self) -> Self { i32::overflowing_sub(self, rhs).0 }
84}
85
86impl PrimitiveInt for i64 {
87    type Larger = i128;
88
89    fn bits() -> usize { Self::BITS as usize }
90    fn overflowing_mul(self, rhs: Self) -> Self { i64::overflowing_mul(self, rhs).0 }
91    fn overflowing_sub(self, rhs: Self) -> Self { i64::overflowing_sub(self, rhs).0 }
92}
93
94impl PrimitiveInt for i128 {
95    type Larger = i128;
96
97    fn bits() -> usize { Self::BITS as usize }
98    fn overflowing_mul(self, rhs: Self) -> Self { i128::overflowing_mul(self, rhs).0 }
99    fn overflowing_sub(self, rhs: Self) -> Self { i128::overflowing_sub(self, rhs).0 }
100}
101
102macro_rules! specialize_int_cast {
103    ($(($int_from:ty, $int_to:ty)),*) => {
104        $(
105            impl IntCast<StaticRingBase<$int_from>> for StaticRingBase<$int_to> {
106
107                fn cast(&self, _: &StaticRingBase<$int_from>, value: $int_from) -> Self::Element {
108                    <$int_to>::try_from(<_ as Into<i128>>::into(value)).map_err(|_| ()).unwrap()
109                }
110            }
111        )*
112    };
113}
114
115specialize_int_cast! {
116    (i8, i8), (i8, i16), (i8, i32), (i8, i64), (i8, i128),
117    (i16, i8), (i16, i16), (i16, i32), (i16, i64), (i16, i128),
118    (i32, i8), (i32, i16), (i32, i32), (i32, i64), (i32, i128),
119    (i64, i8), (i64, i16), (i64, i32), (i64, i64), (i64, i128),
120    (i128, i8), (i128, i16), (i128, i32), (i128, i64), (i128, i128)
121}
122
123impl<T: PrimitiveInt> DivisibilityRing for StaticRingBase<T> {
124    type PreparedDivisorData = PrimitiveIntPreparedDivisorData<T>;
125
126    fn checked_left_div(&self, lhs: &Self::Element, rhs: &Self::Element) -> Option<Self::Element> {
127        if self.is_zero(lhs) && self.is_zero(rhs) {
128            return Some(self.zero());
129        } else if self.is_zero(rhs) {
130            return None;
131        }
132        let (div, rem) = self.euclidean_div_rem(*lhs, rhs);
133        if self.is_zero(&rem) {
134            return Some(div);
135        } else {
136            return None;
137        }
138    }
139
140    fn balance_factor<'a, I>(&self, elements: I) -> Option<Self::Element>
141    where
142        I: Iterator<Item = &'a Self::Element>,
143        Self: 'a,
144    {
145        Some(elements.fold(self.zero(), |a, b| self.ideal_gen(&a, b)))
146    }
147
148    fn prepare_divisor(&self, x: &Self::Element) -> Self::PreparedDivisorData {
149        // currently prepared division is not implemented for i128, as using Barett-reduction here
150        // requires 256-bit arithmetic, and I saw no need to make that effort
151        if TypeId::of::<T>() == TypeId::of::<i128>() {
152            return PrimitiveIntPreparedDivisorData(T::from(0));
153        }
154        return match <T as Into<i128>>::into(*x) {
155            0 => PrimitiveIntPreparedDivisorData(T::from(0)),
156            1 => PrimitiveIntPreparedDivisorData(T::try_from((1i128 << (T::bits() - 1)) - 1).ok().unwrap()),
157            -1 => PrimitiveIntPreparedDivisorData(T::try_from((-1i128 << (T::bits() - 1)) + 1).ok().unwrap()),
158            val => PrimitiveIntPreparedDivisorData(
159                <T as TryFrom<i128>>::try_from((1i128 << (T::bits() - 1)) / val)
160                    .ok()
161                    .unwrap(),
162            ),
163        };
164    }
165
166    fn checked_left_div_prepared(
167        &self,
168        lhs: &Self::Element,
169        rhs: &Self::Element,
170        rhs_prep: &Self::PreparedDivisorData,
171    ) -> Option<Self::Element> {
172        // currently prepared division is not implemented for i128, as using Barett-reduction here
173        // requires 256-bit arithmetic, and I saw no need to make that effort
174        if TypeId::of::<T>() == TypeId::of::<i128>() {
175            return self.checked_left_div(lhs, rhs);
176        }
177        if *rhs == T::from(0) {
178            if *lhs == T::from(0) { Some(T::from(0)) } else { None }
179        } else {
180            let mut prod = <T as Into<T::Larger>>::into(*lhs);
181            prod *= <T as Into<T::Larger>>::into(rhs_prep.0);
182            let mut result = <T as TryFrom<T::Larger>>::try_from(prod >> (T::bits() - 1))
183                .ok()
184                .unwrap();
185            let remainder = T::overflowing_sub(*lhs, T::overflowing_mul(result, *rhs));
186            if remainder == T::from(0) {
187                Some(result)
188            } else if remainder == *rhs {
189                result += T::from(1);
190                Some(result)
191            } else if -remainder == *rhs {
192                result -= T::from(1);
193                Some(result)
194            } else {
195                None
196            }
197        }
198    }
199}
200
201/// Data associated to an element of [`StaticRing`] that allows for faster division.
202///
203/// See also [`DivisibilityRing::prepare_divisor()`].
204#[derive(Clone, Copy, Debug)]
205pub struct PrimitiveIntPreparedDivisorData<T: PrimitiveInt>(T);
206
207impl<T: PrimitiveInt> Domain for StaticRingBase<T> {}
208
209impl<T: PrimitiveInt> PrincipalIdealRing for StaticRingBase<T> {
210    fn checked_div_min(&self, lhs: &Self::Element, rhs: &Self::Element) -> Option<Self::Element> {
211        if self.is_zero(lhs) && self.is_zero(rhs) {
212            return Some(self.one());
213        }
214        self.checked_left_div(lhs, rhs)
215    }
216
217    fn extended_ideal_gen(
218        &self,
219        lhs: &Self::Element,
220        rhs: &Self::Element,
221    ) -> (Self::Element, Self::Element, Self::Element) {
222        algorithms::eea::eea(*lhs, *rhs, StaticRing::<T>::RING)
223    }
224}
225
226impl<T: PrimitiveInt> EuclideanRing for StaticRingBase<T> {
227    fn euclidean_div_rem(&self, lhs: Self::Element, rhs: &Self::Element) -> (Self::Element, Self::Element) {
228        (lhs / *rhs, lhs % *rhs)
229    }
230
231    fn euclidean_deg(&self, val: &Self::Element) -> Option<usize> {
232        RingRef::new(self)
233            .can_iso::<StaticRing<i128>>(&StaticRing::<i128>::RING)
234            .unwrap()
235            .map(*val)
236            .checked_abs()
237            .and_then(|x| usize::try_from(x).ok())
238    }
239}
240
241impl<T: PrimitiveInt> OrderedRing for StaticRingBase<T> {
242    fn cmp(&self, lhs: &Self::Element, rhs: &Self::Element) -> std::cmp::Ordering {
243        RingRef::new(self)
244            .can_iso::<StaticRing<i128>>(&StaticRing::<i128>::RING)
245            .unwrap()
246            .map(*lhs)
247            .cmp(
248                &RingRef::new(self)
249                    .can_iso::<StaticRing<i128>>(&StaticRing::<i128>::RING)
250                    .unwrap()
251                    .map(*rhs),
252            )
253    }
254}
255
256impl_interpolation_base_ring_char_zero! { <{T}> InterpolationBaseRing for StaticRingBase<T> where T: PrimitiveInt }
257
258impl_poly_gcd_locally_for_ZZ! { <{T}> IntegerPolyGCDRing for StaticRingBase<T> where T: PrimitiveInt }
259
260impl_eval_poly_locally_for_ZZ! { <{T}> EvalPolyLocallyRing for StaticRingBase<T> where T: PrimitiveInt }
261
262impl<T> FiniteRingSpecializable for StaticRingBase<T>
263where
264    T: PrimitiveInt,
265{
266    fn specialize<O: FiniteRingOperation<Self>>(op: O) -> O::Output { op.fallback() }
267}
268
269impl<T: PrimitiveInt> IntegerRing for StaticRingBase<T> {
270    fn to_float_approx(&self, value: &Self::Element) -> f64 {
271        RingRef::new(self)
272            .can_iso::<StaticRing<i128>>(&StaticRing::<i128>::RING)
273            .unwrap()
274            .map(*value) as f64
275    }
276
277    fn from_float_approx(&self, value: f64) -> Option<Self::Element> {
278        Some(RingRef::new(self).coerce::<StaticRing<i128>>(&StaticRing::<i128>::RING, value as i128))
279    }
280
281    fn abs_is_bit_set(&self, value: &Self::Element, i: usize) -> bool {
282        match RingRef::new(self)
283            .can_iso::<StaticRing<i128>>(&StaticRing::<i128>::RING)
284            .unwrap()
285            .map(*value)
286        {
287            i128::MIN => i == i128::BITS as usize - 1,
288            x => (x.abs() >> i) & 1 == 1,
289        }
290    }
291
292    fn abs_highest_set_bit(&self, value: &Self::Element) -> Option<usize> {
293        match RingRef::new(self)
294            .can_iso::<StaticRing<i128>>(&StaticRing::<i128>::RING)
295            .unwrap()
296            .map(*value)
297        {
298            0 => None,
299            i128::MIN => Some(i128::BITS as usize - 1),
300            x => Some(i128::BITS as usize - x.abs().leading_zeros() as usize - 1),
301        }
302    }
303
304    fn abs_lowest_set_bit(&self, value: &Self::Element) -> Option<usize> {
305        match RingRef::new(self)
306            .can_iso::<StaticRing<i128>>(&StaticRing::<i128>::RING)
307            .unwrap()
308            .map(*value)
309        {
310            0 => None,
311            i128::MIN => Some(i128::BITS as usize - 1),
312            x => Some(x.abs().trailing_zeros() as usize),
313        }
314    }
315
316    fn euclidean_div_pow_2(&self, value: &mut Self::Element, power: usize) {
317        *value = RingRef::new(self).coerce::<StaticRing<i128>>(
318            &StaticRing::<i128>::RING,
319            RingRef::new(self)
320                .can_iso::<StaticRing<i128>>(&StaticRing::<i128>::RING)
321                .unwrap()
322                .map(*value)
323                / (1 << power),
324        );
325    }
326
327    fn mul_pow_2(&self, value: &mut Self::Element, power: usize) {
328        *value = RingRef::new(self).coerce::<StaticRing<i128>>(
329            &StaticRing::<i128>::RING,
330            RingRef::new(self)
331                .can_iso::<StaticRing<i128>>(&StaticRing::<i128>::RING)
332                .unwrap()
333                .map(*value)
334                << power,
335        );
336    }
337
338    fn get_uniformly_random_bits<G: FnMut() -> u64>(&self, log2_bound_exclusive: usize, mut rng: G) -> Self::Element {
339        assert!(log2_bound_exclusive < T::bits());
340        RingRef::new(self).coerce::<StaticRing<i128>>(
341            &StaticRing::<i128>::RING,
342            ((((rng() as u128) << u64::BITS) | (rng() as u128)) & ((1 << log2_bound_exclusive) - 1)) as i128,
343        )
344    }
345
346    fn representable_bits(&self) -> Option<usize> { Some(T::bits() - 1) }
347}
348
349impl<T: PrimitiveInt> HashableElRing for StaticRingBase<T> {
350    fn hash<H: std::hash::Hasher>(&self, el: &Self::Element, h: &mut H) {
351        h.write_i128(
352            RingRef::new(self)
353                .can_iso::<StaticRing<i128>>(&StaticRing::<i128>::RING)
354                .unwrap()
355                .map(*el),
356        )
357    }
358}
359
360/// The ring of integers `Z`, using the arithmetic of the primitive integer type `T`.
361///
362/// For the difference to [`StaticRing`], see the documentation of [`crate::ring::RingStore`].
363pub struct StaticRingBase<T> {
364    element: PhantomData<T>,
365}
366
367impl<T> Debug for StaticRingBase<T> {
368    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { write!(f, "Z") }
369}
370
371impl<T> PartialEq for StaticRingBase<T> {
372    fn eq(&self, _: &Self) -> bool { true }
373}
374
375impl<T: PrimitiveInt> RingValue<StaticRingBase<T>> {
376    /// The singleton ring instance of [`StaticRing`].
377    pub const RING: StaticRing<T> = RingValue::from(StaticRingBase { element: PhantomData });
378}
379
380impl<T> Copy for StaticRingBase<T> {}
381
382impl<T> Clone for StaticRingBase<T> {
383    fn clone(&self) -> Self { *self }
384}
385
386impl<T: PrimitiveInt> RingBase for StaticRingBase<T> {
387    type Element = T;
388
389    fn clone_el(&self, val: &Self::Element) -> Self::Element { *val }
390
391    fn add_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) { *lhs += rhs; }
392
393    fn negate_inplace(&self, lhs: &mut Self::Element) { *lhs = -*lhs; }
394
395    fn mul_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) { *lhs *= rhs; }
396
397    fn from_int(&self, value: i32) -> Self::Element { T::try_from(value).map_err(|_| ()).unwrap() }
398
399    fn eq_el(&self, lhs: &Self::Element, rhs: &Self::Element) -> bool { *lhs == *rhs }
400
401    fn is_commutative(&self) -> bool { true }
402    fn is_noetherian(&self) -> bool { true }
403
404    fn dbg_within<'a>(
405        &self,
406        value: &Self::Element,
407        out: &mut std::fmt::Formatter<'a>,
408        _: EnvBindingStrength,
409    ) -> std::fmt::Result {
410        write!(out, "{}", *value)
411    }
412
413    fn characteristic<I: RingStore>(&self, ZZ: I) -> Option<El<I>>
414    where
415        I::Type: IntegerRing,
416    {
417        Some(ZZ.zero())
418    }
419
420    fn pow_gen<R: RingStore>(&self, x: Self::Element, power: &El<R>, integers: R) -> Self::Element
421    where
422        R::Type: IntegerRing,
423    {
424        assert!(!integers.is_neg(power));
425        algorithms::sqr_mul::generic_abs_square_and_multiply(
426            x,
427            power,
428            &integers,
429            |mut a| {
430                self.square(&mut a);
431                a
432            },
433            |a, b| self.mul_ref_fst(a, b),
434            self.one(),
435        )
436    }
437
438    fn is_approximate(&self) -> bool { false }
439}
440
441impl KaratsubaHint for StaticRingBase<i8> {
442    fn karatsuba_threshold(&self) -> usize { 4 }
443}
444
445impl KaratsubaHint for StaticRingBase<i16> {
446    fn karatsuba_threshold(&self) -> usize { 4 }
447}
448
449impl KaratsubaHint for StaticRingBase<i32> {
450    fn karatsuba_threshold(&self) -> usize { 4 }
451}
452
453impl KaratsubaHint for StaticRingBase<i64> {
454    fn karatsuba_threshold(&self) -> usize { 4 }
455}
456
457impl KaratsubaHint for StaticRingBase<i128> {
458    fn karatsuba_threshold(&self) -> usize { 3 }
459}
460
461impl StrassenHint for StaticRingBase<i8> {
462    fn strassen_threshold(&self) -> usize { 6 }
463}
464
465impl StrassenHint for StaticRingBase<i16> {
466    fn strassen_threshold(&self) -> usize { 6 }
467}
468
469impl StrassenHint for StaticRingBase<i32> {
470    fn strassen_threshold(&self) -> usize { 6 }
471}
472
473impl StrassenHint for StaticRingBase<i64> {
474    fn strassen_threshold(&self) -> usize { 6 }
475}
476
477impl StrassenHint for StaticRingBase<i128> {
478    fn strassen_threshold(&self) -> usize { 5 }
479}
480
481impl<T: PrimitiveInt> SerializableElementRing for StaticRingBase<T> {
482    fn deserialize<'de, D>(&self, deserializer: D) -> Result<Self::Element, D::Error>
483    where
484        D: Deserializer<'de>,
485    {
486        T::deserialize(deserializer)
487    }
488
489    fn serialize<S>(&self, el: &Self::Element, serializer: S) -> Result<S::Ok, S::Error>
490    where
491        S: Serializer,
492    {
493        T::serialize(el, serializer)
494    }
495}
496
497impl<T: PrimitiveInt> Serialize for StaticRingBase<T> {
498    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
499    where
500        S: Serializer,
501    {
502        SerializableNewtypeStruct::new("IntegerRing(primitive int)", ()).serialize(serializer)
503    }
504}
505
506impl<'de, T: PrimitiveInt> Deserialize<'de> for StaticRingBase<T> {
507    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
508    where
509        D: Deserializer<'de>,
510    {
511        DeserializeSeedNewtypeStruct::new("IntegerRing(primitive int)", PhantomData::<()>)
512            .deserialize(deserializer)
513            .map(|()| StaticRing::<T>::RING.into())
514    }
515}
516
517/// The ring of integers `Z`, using the arithmetic of the primitive integer type `T`.
518pub type StaticRing<T> = RingValue<StaticRingBase<T>>;
519
520impl<T: PrimitiveInt> Default for StaticRingBase<T> {
521    fn default() -> Self { StaticRing::RING.into() }
522}
523
524#[test]
525fn test_ixx_bit_op() {
526    let ring_i16 = StaticRing::<i16>::RING;
527    let ring_i128 = StaticRing::<i128>::RING;
528    assert_eq!(Some(2), ring_i16.abs_highest_set_bit(&0x5));
529    assert_eq!(Some(15), ring_i16.abs_highest_set_bit(&i16::MIN));
530    assert_eq!(Some(1), ring_i16.abs_highest_set_bit(&-2));
531    assert_eq!(Some(2), ring_i128.abs_highest_set_bit(&0x5));
532    assert_eq!(Some(127), ring_i128.abs_highest_set_bit(&i128::MIN));
533    assert_eq!(Some(126), ring_i128.abs_highest_set_bit(&(i128::MIN + 1)));
534    assert_eq!(Some(126), ring_i128.abs_highest_set_bit(&(-1 - i128::MIN)));
535    assert_eq!(Some(1), ring_i128.abs_highest_set_bit(&-2));
536    assert_eq!(true, ring_i128.abs_is_bit_set(&-12, 2));
537    assert_eq!(false, ring_i128.abs_is_bit_set(&-12, 1));
538    assert_eq!(true, ring_i128.abs_is_bit_set(&i128::MIN, 127));
539    assert_eq!(false, ring_i128.abs_is_bit_set(&i128::MIN, 126));
540}
541
542#[test]
543fn test_get_uniformly_random() {
544    crate::integer::generic_tests::test_integer_get_uniformly_random(StaticRing::<i8>::RING);
545    crate::integer::generic_tests::test_integer_get_uniformly_random(StaticRing::<i16>::RING);
546    crate::integer::generic_tests::test_integer_get_uniformly_random(StaticRing::<i32>::RING);
547    crate::integer::generic_tests::test_integer_get_uniformly_random(StaticRing::<i64>::RING);
548    crate::integer::generic_tests::test_integer_get_uniformly_random(StaticRing::<i128>::RING);
549}
550
551#[test]
552fn test_integer_axioms() {
553    crate::integer::generic_tests::test_integer_axioms(
554        StaticRing::<i8>::RING,
555        [-2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8].into_iter(),
556    );
557    crate::integer::generic_tests::test_integer_axioms(
558        StaticRing::<i16>::RING,
559        [-2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8].into_iter(),
560    );
561    crate::integer::generic_tests::test_integer_axioms(
562        StaticRing::<i32>::RING,
563        [-2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8].into_iter(),
564    );
565    crate::integer::generic_tests::test_integer_axioms(
566        StaticRing::<i64>::RING,
567        [-2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8].into_iter(),
568    );
569    crate::integer::generic_tests::test_integer_axioms(
570        StaticRing::<i128>::RING,
571        [-2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8].into_iter(),
572    );
573}
574
575#[test]
576fn test_euclidean_ring_axioms() {
577    crate::pid::generic_tests::test_euclidean_ring_axioms(
578        StaticRing::<i8>::RING,
579        [-2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8].into_iter(),
580    );
581    crate::pid::generic_tests::test_euclidean_ring_axioms(
582        StaticRing::<i16>::RING,
583        [-2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8].into_iter(),
584    );
585    crate::pid::generic_tests::test_euclidean_ring_axioms(
586        StaticRing::<i32>::RING,
587        [-2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8].into_iter(),
588    );
589    crate::pid::generic_tests::test_euclidean_ring_axioms(
590        StaticRing::<i64>::RING,
591        [-2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8].into_iter(),
592    );
593    crate::pid::generic_tests::test_euclidean_ring_axioms(
594        StaticRing::<i128>::RING,
595        [-2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8].into_iter(),
596    );
597}
598
599#[test]
600fn test_principal_ideal_ring_ring_axioms() {
601    crate::pid::generic_tests::test_principal_ideal_ring_axioms(StaticRing::<i8>::RING, [-2, -1, 0, 1, 2].into_iter());
602    crate::pid::generic_tests::test_principal_ideal_ring_axioms(
603        StaticRing::<i16>::RING,
604        [-2, -1, 0, 1, 2, 3, 4].into_iter(),
605    );
606    crate::pid::generic_tests::test_principal_ideal_ring_axioms(
607        StaticRing::<i32>::RING,
608        [-2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8].into_iter(),
609    );
610    crate::pid::generic_tests::test_principal_ideal_ring_axioms(
611        StaticRing::<i64>::RING,
612        [-2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8].into_iter(),
613    );
614    crate::pid::generic_tests::test_principal_ideal_ring_axioms(
615        StaticRing::<i128>::RING,
616        [-2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8].into_iter(),
617    );
618}
619
620#[test]
621fn test_lowest_set_bit() {
622    assert_eq!(None, StaticRing::<i32>::RING.abs_lowest_set_bit(&0));
623    assert_eq!(Some(0), StaticRing::<i32>::RING.abs_lowest_set_bit(&3));
624    assert_eq!(Some(0), StaticRing::<i32>::RING.abs_lowest_set_bit(&-3));
625    assert_eq!(None, StaticRing::<i128>::RING.abs_lowest_set_bit(&0));
626    assert_eq!(Some(127), StaticRing::<i128>::RING.abs_lowest_set_bit(&i128::MIN));
627    assert_eq!(Some(0), StaticRing::<i128>::RING.abs_lowest_set_bit(&i128::MAX));
628}
629
630#[test]
631fn test_prepared_div() {
632    type PrimInt = i8;
633    for x in PrimInt::MIN..PrimInt::MAX {
634        let div_x = PreparedDivisor::new(StaticRing::<PrimInt>::RING.get_ring(), x);
635        for y in PrimInt::MIN..PrimInt::MAX {
636            if x == 0 {
637                if y == 0 {
638                    assert!(
639                        div_x
640                            .checked_left_div_by(&y, StaticRing::<PrimInt>::RING.get_ring())
641                            .is_some()
642                    );
643                } else {
644                    assert!(
645                        div_x
646                            .checked_left_div_by(&y, StaticRing::<PrimInt>::RING.get_ring())
647                            .is_none()
648                    );
649                }
650            } else if y == PrimInt::MIN && x == -1 {
651                // this cannot be evaluated without overflow
652            } else if y % x == 0 {
653                assert_eq!(
654                    y / x,
655                    div_x
656                        .checked_left_div_by(&y, StaticRing::<PrimInt>::RING.get_ring())
657                        .unwrap()
658                );
659            } else {
660                assert!(
661                    div_x
662                        .checked_left_div_by(&y, StaticRing::<PrimInt>::RING.get_ring())
663                        .is_none()
664                );
665            }
666        }
667    }
668}
669
670#[test]
671fn test_serialization() {
672    crate::serialization::generic_tests::test_serialize_deserialize(StaticRing::<i8>::RING.into());
673    crate::serialization::generic_tests::test_serialize_deserialize(StaticRing::<i16>::RING.into());
674    crate::serialization::generic_tests::test_serialize_deserialize(StaticRing::<i32>::RING.into());
675    crate::serialization::generic_tests::test_serialize_deserialize(StaticRing::<i64>::RING.into());
676    crate::serialization::generic_tests::test_serialize_deserialize(StaticRing::<i128>::RING.into());
677}
feanor_math/primitive_int.rs

feanor_math/
primitive_int.rs
