feanor_math/
primitive_int.rs

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

feanor_math/
primitive_int.rs
