feanor_math/rings/
direct_power.rs

1use std::array::{from_fn, try_from_fn};
2use std::marker::PhantomData;
3
4use crate::divisibility::*;
5use crate::serialization::*;
6use crate::specialization::{FiniteRingSpecializable, FiniteRingOperation};
7use crate::algorithms::fft::cooley_tuckey::CooleyTuckeyButterfly;
8use crate::integer::{IntegerRing, IntegerRingStore};
9use crate::rings::finite::{FiniteRing, FiniteRingStore};
10use crate::ring::*;
11use crate::iters::*;
12use crate::rings::zn::zn_64::*;
13use crate::homomorphism::*;
14use crate::seq::CloneRingEl;
15
16use feanor_serde::newtype_struct::{DeserializeSeedNewtypeStruct, SerializableNewtypeStruct};
17use feanor_serde::seq::{DeserializeSeedSeq, SerializableSeq};
18use serde::{Serializer, Deserializer, Serialize};
19use serde::de::DeserializeSeed;
20
21///
22/// The `N`-fold direct product ring `R x ... x R`.
23/// 
24/// Currently, this is a quite naive implementation, which just
25/// repeats operations along each component. In the future, this
26/// might become an entrypoint for vectorization or similar. Hence,
27/// it might remain unstable for a while.
28/// 
29#[stability::unstable(feature = "enable")]
30pub struct DirectPowerRingBase<R: RingStore, const N: usize> {
31    base: R
32}
33
34#[stability::unstable(feature = "enable")]
35pub type DirectPowerRing<R, const N: usize> = RingValue<DirectPowerRingBase<R, N>>;
36
37impl<R: RingStore, const N: usize> DirectPowerRing<R, N> {
38
39    #[stability::unstable(feature = "enable")]
40    pub fn new(base: R) -> Self {
41        Self::from(DirectPowerRingBase { base })
42    }
43}
44
45#[stability::unstable(feature = "enable")]
46pub struct DirectPowerRingElCreator<'a, R: RingStore, const N: usize> {
47    ring: &'a DirectPowerRingBase<R, N>
48}
49
50impl<R: RingStore, const N: usize> Clone for DirectPowerRingBase<R, N>
51    where R: Clone
52{
53    fn clone(&self) -> Self {
54        Self { base: self.base.clone() }
55    }
56}
57
58impl<R: RingStore, const N: usize> Copy for DirectPowerRingBase<R, N>
59    where R: Copy, El<R>: Copy
60{}
61
62impl<R: RingStore, const N: usize> PartialEq for DirectPowerRingBase<R, N> {
63    fn eq(&self, other: &Self) -> bool {
64        self.base.get_ring() == other.base.get_ring()
65    }
66}
67
68impl<R: RingStore, const N: usize> RingBase for DirectPowerRingBase<R, N> {
69
70    type Element = [El<R>; N];
71    
72    fn clone_el(&self, val: &Self::Element) -> Self::Element {
73        from_fn(|i| self.base.clone_el(&val[i]))
74    }
75
76    fn add_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) {
77        for (tgt, src) in lhs.into_iter().zip(rhs.into_iter()) {
78            self.base.add_assign_ref(tgt, src)
79        }
80    }
81
82    fn add_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) {
83        for (tgt, src) in lhs.into_iter().zip(rhs.into_iter()) {
84            self.base.add_assign(tgt, src)
85        }
86    }
87
88    fn sub_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) {
89        for (tgt, src) in lhs.into_iter().zip(rhs.into_iter()) {
90            self.base.sub_assign_ref(tgt, src)
91        }
92    }
93
94    fn negate_inplace(&self, lhs: &mut Self::Element) {
95        for val in lhs.into_iter() {
96            self.base.negate_inplace(val);
97        }
98    }
99
100    fn mul_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) {
101        for (tgt, src) in lhs.into_iter().zip(rhs.into_iter()) {
102            self.base.mul_assign(tgt, src)
103        }
104    }
105
106    fn mul_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) {
107        for (tgt, src) in lhs.into_iter().zip(rhs.into_iter()) {
108            self.base.mul_assign_ref(tgt, src)
109        }
110    }
111
112    fn zero(&self) -> Self::Element {
113        from_fn(|_| self.base.zero())
114    }
115
116    fn one(&self) -> Self::Element { 
117        from_fn(|_| self.base.one())
118    }
119
120    fn neg_one(&self) -> Self::Element {
121        from_fn(|_| self.base.neg_one())
122    }
123
124    fn from_int(&self, value: i32) -> Self::Element {
125        let val = self.base.get_ring().from_int(value);
126        from_fn(|_| self.base.clone_el(&val))
127    }
128
129    fn eq_el(&self, lhs: &Self::Element, rhs: &Self::Element) -> bool {
130        lhs.into_iter().zip(rhs.into_iter()).all(|(l, r)| self.base.eq_el(l, r))
131    }
132
133    fn is_zero(&self, value: &Self::Element) -> bool {
134        value.into_iter().all(|v| self.base.is_zero(v))
135    }
136
137    fn is_one(&self, value: &Self::Element) -> bool {
138        value.into_iter().all(|v| self.base.is_one(v))
139    }
140    fn is_neg_one(&self, value: &Self::Element) -> bool {
141        value.into_iter().all(|v| self.base.is_neg_one(v))
142    }
143
144    fn is_commutative(&self) -> bool {
145        self.base.is_commutative()
146    }
147
148    fn is_noetherian(&self) -> bool {
149        self.base.is_noetherian()
150    }
151
152    fn is_approximate(&self) -> bool {
153        self.base.get_ring().is_approximate()
154    }
155
156    fn dbg_within<'a>(&self, value: &Self::Element, out: &mut std::fmt::Formatter<'a>, _env: EnvBindingStrength) -> std::fmt::Result {
157        write!(out, "(")?;
158        for i in 0..N {
159            self.base.get_ring().dbg_within(&value[i], out, EnvBindingStrength::Weakest)?;
160            if i + 1 != N {
161                write!(out, ", ")?;
162            }
163        }
164        write!(out, ")")?;
165        return Ok(());
166    }
167
168    fn square(&self, value: &mut Self::Element) {
169        for val in value.into_iter() {
170            self.base.square(val)
171        }
172    }
173
174    fn sub_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) {
175        for (tgt, src) in lhs.into_iter().zip(rhs.into_iter()) {
176            self.base.sub_assign(tgt, src)
177        }
178    }
179
180    fn mul_assign_int(&self, lhs: &mut Self::Element, rhs: i32) {
181        for tgt in lhs.into_iter() {
182            self.base.get_ring().mul_assign_int(tgt, rhs)
183        }
184    }
185
186    fn sub_self_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) {
187        for (tgt, src) in lhs.into_iter().zip(rhs.into_iter()) {
188            self.base.sub_self_assign(tgt, src)
189        }
190    }
191
192    fn sub_self_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) {
193        for (tgt, src) in lhs.into_iter().zip(rhs.into_iter()) {
194            self.base.sub_self_assign_ref(tgt, src)
195        }
196    }
197
198    fn sum<I>(&self, els: I) -> Self::Element 
199        where I: IntoIterator<Item = Self::Element>
200    {
201        els.into_iter().fold(self.zero(), |a, b| self.add(a, b))
202    }
203
204    fn prod<I>(&self, els: I) -> Self::Element 
205        where I: IntoIterator<Item = Self::Element>
206    {
207        els.into_iter().fold(self.one(), |a, b| self.mul(a, b))
208    }
209    
210    fn characteristic<I: RingStore + Copy>(&self, ZZ: I) -> Option<El<I>>
211        where I::Type: IntegerRing
212    {
213        self.base.get_ring().characteristic(ZZ)
214    }
215}
216
217impl<R: RingStore, const N: usize> RingExtension for DirectPowerRingBase<R, N> {
218
219    type BaseRing = R;
220
221    fn base_ring<'a>(&'a self) -> &'a Self::BaseRing {
222        &self.base
223    }
224
225    fn from(&self, x: El<Self::BaseRing>) -> Self::Element {
226        self.from_ref(&x)
227    }
228
229    fn from_ref(&self, x: &El<Self::BaseRing>) -> Self::Element {
230        from_fn(|_| self.base.clone_el(x))
231    }
232
233    fn mul_assign_base(&self, lhs: &mut Self::Element, rhs: &El<Self::BaseRing>) {
234        for tgt in lhs.into_iter() {
235            self.base.mul_assign_ref(tgt, rhs);
236        }
237    }
238
239    fn mul_assign_base_through_hom<S: ?Sized + RingBase, H: Homomorphism<S, R::Type>>(&self, lhs: &mut Self::Element, rhs: &S::Element, hom: H) {
240        for tgt in lhs.into_iter() {
241            hom.mul_assign_ref_map(tgt, rhs);
242        }
243    }
244}
245
246impl<S: RingStore, R: RingStore, const N: usize> CanHomFrom<DirectPowerRingBase<S, N>> for DirectPowerRingBase<R, N>
247    where R::Type: CanHomFrom<S::Type>
248{
249    type Homomorphism = <R::Type as CanHomFrom<S::Type>>::Homomorphism;
250
251    fn has_canonical_hom(&self, from: &DirectPowerRingBase<S, N>) -> Option<Self::Homomorphism> {
252        self.base.get_ring().has_canonical_hom(from.base.get_ring())
253    }
254
255    fn map_in(&self, from: &DirectPowerRingBase<S, N>, el: <DirectPowerRingBase<S, N> as RingBase>::Element, hom: &Self::Homomorphism) -> Self::Element {
256        let mut el_it = el.into_iter();
257        from_fn(|_| self.base.get_ring().map_in(from.base.get_ring(), el_it.next().unwrap(), hom))
258    }
259
260    fn map_in_ref(&self, from: &DirectPowerRingBase<S, N>, el: &<DirectPowerRingBase<S, N> as RingBase>::Element, hom: &Self::Homomorphism) -> Self::Element {
261        from_fn(|i| self.base.get_ring().map_in_ref(from.base.get_ring(), &el[i], hom))
262    }
263}
264
265impl<S: RingStore, R: RingStore, const N: usize> CanIsoFromTo<DirectPowerRingBase<S, N>> for DirectPowerRingBase<R, N>
266    where R::Type: CanIsoFromTo<S::Type>
267{
268    type Isomorphism = <R::Type as CanIsoFromTo<S::Type>>::Isomorphism;
269
270    fn has_canonical_iso(&self, from: &DirectPowerRingBase<S, N>) -> Option<Self::Isomorphism> {
271        self.base.get_ring().has_canonical_iso(from.base.get_ring())
272    }
273
274    fn map_out(&self, from: &DirectPowerRingBase<S, N>, el: Self::Element, iso: &Self::Isomorphism) -> <DirectPowerRingBase<S, N> as RingBase>::Element {
275        let mut el_it = el.into_iter();
276        from_fn(|_| self.base.get_ring().map_out(from.base.get_ring(), el_it.next().unwrap(), iso))
277    }
278}
279
280impl<R: RingStore, const N: usize> DivisibilityRing for DirectPowerRingBase<R, N>
281    where R::Type: DivisibilityRing
282{
283    type PreparedDivisorData = [<R::Type as DivisibilityRing>::PreparedDivisorData; N];
284
285    fn checked_left_div(&self, lhs: &Self::Element, rhs: &Self::Element) -> Option<Self::Element> {
286        try_from_fn(|i| self.base.checked_left_div(&lhs[i], &rhs[i]))
287    }
288
289    fn prepare_divisor(&self, el: &Self::Element) -> Self::PreparedDivisorData {
290        from_fn(|i| self.base.get_ring().prepare_divisor(&el[i]))
291    }
292
293    fn checked_left_div_prepared(&self, lhs: &Self::Element, rhs: &Self::Element, rhs_prep: &Self::PreparedDivisorData) -> Option<Self::Element> {
294        try_from_fn(|i| self.base.get_ring().checked_left_div_prepared(&lhs[i], &rhs[i], &rhs_prep[i]))
295    }
296    
297    fn divides_left_prepared(&self, lhs: &Self::Element, rhs: &Self::Element, rhs_prep: &Self::PreparedDivisorData) -> bool {
298        (0..N).all(|i| self.base.get_ring().divides_left_prepared(&lhs[i], &rhs[i], &rhs_prep[i]))
299    }
300}
301
302impl<R: RingStore, const N: usize> FiniteRingSpecializable for DirectPowerRingBase<R, N>
303    where R::Type: FiniteRingSpecializable
304{
305    fn specialize<O: FiniteRingOperation<Self>>(op: O) -> O::Output {
306        struct BaseRingCase<R: RingStore, O: FiniteRingOperation<DirectPowerRingBase<R, N>>, const N: usize> {
307            op: O,
308            ring: PhantomData<R>
309        }
310        impl<R: RingStore, O: FiniteRingOperation<DirectPowerRingBase<R, N>>, const N: usize> FiniteRingOperation<R::Type> for BaseRingCase<R, O, N> {
311            type Output = O::Output;
312            fn execute(self) -> Self::Output where R::Type: FiniteRing {
313                self.op.execute()
314            }
315            fn fallback(self) -> Self::Output {
316                self.op.fallback()
317            }
318        }
319        <R::Type as FiniteRingSpecializable>::specialize(BaseRingCase {
320            op: op,
321            ring: PhantomData
322        })
323    }
324}
325
326impl<'a, 'b, R: RingStore, const N: usize> Copy for DirectPowerRingElCreator<'a, R, N> {}
327
328impl<'a, 'b, R: RingStore, const N: usize> Clone for DirectPowerRingElCreator<'a, R, N> {
329    fn clone(&self) -> Self {
330        *self
331    }
332}
333
334impl<'a, 'b, R: RingStore, const N: usize> FnOnce<(&'b [El<R>],)> for DirectPowerRingElCreator<'a, R, N> {
335
336    type Output = [El<R>; N];
337
338    extern "rust-call" fn call_once(self, args: (&'b [El<R>],)) -> Self::Output {
339        self.call(args)
340    }
341}
342
343impl<'a, 'b, R: RingStore, const N: usize> FnMut<(&'b [El<R>],)> for DirectPowerRingElCreator<'a, R, N> {
344
345    extern "rust-call" fn call_mut(&mut self, args: (&'b [El<R>],)) -> Self::Output {
346        self.call(args)
347    }
348}
349
350impl<'a, 'b, R: RingStore, const N: usize> Fn<(&'b [El<R>],)> for DirectPowerRingElCreator<'a, R, N> {
351
352    extern "rust-call" fn call(&self, args: (&'b [El<R>],)) -> Self::Output {
353        assert_eq!(N, args.0.len());
354        from_fn(|i| self.ring.base.clone_el(&args.0[i]))
355    }
356}
357
358impl<R: RingStore, const N: usize> FiniteRing for DirectPowerRingBase<R, N>
359    where R::Type: FiniteRing
360{
361    type ElementsIter<'a> = MultiProduct<<R::Type as FiniteRing>::ElementsIter<'a>, DirectPowerRingElCreator<'a, R, N>, CloneRingEl<&'a R>, [El<R>; N]>
362        where Self: 'a;
363
364    fn elements<'a>(&'a self) -> Self::ElementsIter<'a> {
365        multi_cartesian_product((0..N).map(|_| self.base.elements()), DirectPowerRingElCreator { ring: self }, CloneRingEl(&self.base))
366    }
367
368    fn random_element<G: FnMut() -> u64>(&self, mut rng: G) -> <Self as RingBase>::Element {
369        from_fn(|_| self.base.random_element(&mut rng))
370    }
371
372    fn size<I: RingStore + Copy>(&self, ZZ: I) -> Option<El<I>>
373        where I::Type: IntegerRing
374    {
375        let base_size = self.base.size(ZZ)?;
376        if ZZ.get_ring().representable_bits().is_none() || ZZ.get_ring().representable_bits().unwrap() >= ZZ.abs_log2_ceil(&base_size).unwrap_or(0) * N {
377            return Some(ZZ.pow(base_size, N));
378        } else {
379            return None;
380        }
381    }
382}
383
384macro_rules! specialize_butterfly {
385    ($($num:literal),*) => { $(
386                
387        impl CooleyTuckeyButterfly<ZnFastmulBase> for DirectPowerRingBase<Zn, $num> {
388
389            #[inline(always)]
390            fn butterfly_new<H: Homomorphism<ZnFastmulBase, Self>>(hom: H, x: &mut Self::Element, y: &mut Self::Element, twiddle: &ZnFastmulEl) {
391                for (x, y) in x.into_iter().zip(y.into_iter()) {
392                    // the only homomorphism this can be is the `CanHom` composed with an `Inclusion`
393                    <ZnBase as CooleyTuckeyButterfly<ZnFastmulBase>>::butterfly_new(CanHom::from_raw_parts(hom.domain(), hom.codomain().base_ring(), ()), x, y, twiddle);
394                }
395            }
396
397            #[inline(always)]
398            fn inv_butterfly_new<H: Homomorphism<ZnFastmulBase, Self>>(hom: H, x: &mut Self::Element, y: &mut Self::Element, twiddle: &ZnFastmulEl) {
399                for (x, y) in x.into_iter().zip(y.into_iter()) {
400                    // the only homomorphism this can be is the `CanHom` composed with an `Inclusion`
401                    <ZnBase as CooleyTuckeyButterfly<ZnFastmulBase>>::inv_butterfly_new(CanHom::from_raw_parts(hom.domain(), hom.codomain().base_ring(), ()), x, y, twiddle);
402                }
403            }
404            
405            #[inline(always)]
406            fn prepare_for_fft(&self, value: &mut [ZnEl; $num]) {
407                for x in value.into_iter() {
408                    <ZnBase as CooleyTuckeyButterfly<ZnFastmulBase>>::prepare_for_fft(self.base_ring().get_ring(), x)
409                }
410            }
411            
412            #[inline(always)]
413            fn prepare_for_inv_fft(&self, value: &mut [ZnEl; $num]) {
414                for x in value.into_iter() {
415                    <ZnBase as CooleyTuckeyButterfly<ZnFastmulBase>>::prepare_for_inv_fft(self.base_ring().get_ring(), x)
416                }
417            }
418        }
419    )* }
420}
421specialize_butterfly!{ 1, 2, 3, 4, 5, 6, 7, 8, 16 }
422
423impl<R: RingStore, const N: usize> HashableElRing for DirectPowerRingBase<R, N>
424    where R::Type: HashableElRing
425{
426    fn hash<H: std::hash::Hasher>(&self, el: &Self::Element, h: &mut H) {
427        for val in el.into_iter() {
428            self.base.get_ring().hash(val, h);
429        }
430    }
431}
432
433impl<R: RingStore, const N: usize> SerializableElementRing for DirectPowerRingBase<R, N>
434    where R::Type: SerializableElementRing
435{
436    fn deserialize<'de, D>(&self, deserializer: D) -> Result<Self::Element, D::Error>
437        where D: Deserializer<'de>
438    {
439        DeserializeSeedNewtypeStruct::new("DirectPowerRingEl", DeserializeSeedSeq::new(
440            std::iter::repeat(DeserializeWithRing::new(self.base_ring())).take(N + 1),
441            (from_fn(|_| None), 0),
442            |(mut current, mut current_idx), next| {
443                current[current_idx] = Some(next);
444                current_idx += 1;
445                (current, current_idx)
446            }
447        )).deserialize(deserializer).map(|(res, len): ([Option<_>; N], usize)| {
448            assert_eq!(N, len);
449            let mut res_it = res.into_iter();
450            from_fn(|_| res_it.next().unwrap().unwrap())
451        })
452    }
453
454    fn serialize<S>(&self, el: &Self::Element, serializer: S) -> Result<S::Ok, S::Error>
455        where S: Serializer
456    {
457        SerializableNewtypeStruct::new("DirectPowerRingEl", SerializableSeq::new_with_len(
458            (0..N).map(|i| SerializeWithRing::new(&el[i], self.base_ring())), N
459        )).serialize(serializer)
460    }
461}
462
463#[cfg(test)]
464use crate::primitive_int::StaticRing;
465
466#[test]
467fn test_ring_axioms() {
468    let ring: DirectPowerRing<_, 3> = DirectPowerRing::new(Zn::new(3));
469    crate::ring::generic_tests::test_ring_axioms(&ring, ring.elements());
470}
471
472#[test]
473fn test_can_hom_axioms() {
474    let from: DirectPowerRing<_, 3> = DirectPowerRing::new(StaticRing::<i64>::RING);
475    let ring: DirectPowerRing<_, 3> = DirectPowerRing::new(Zn::new(3));
476    crate::ring::generic_tests::test_hom_axioms(&from, &ring, multi_cartesian_product((0..3).map(|_| -4..5), clone_array::<_, 3>, |_, x| *x));
477}
478
479#[test]
480fn test_hash_axioms() {
481    let ring: DirectPowerRing<_, 3> = DirectPowerRing::new(Zn::new(3));
482    crate::ring::generic_tests::test_hash_axioms(&ring, ring.elements());
483}
484
485#[test]
486fn test_serialization() {
487    let ring: DirectPowerRing<_, 3> = DirectPowerRing::new(Zn::new(3));
488    crate::serialization::generic_tests::test_serialization(&ring, ring.elements());
489}
feanor_math/rings/direct_power.rs

feanor_math/rings/
direct_power.rs
