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

feanor_math/
primitive_int.rs
