feanor_math/rings/
direct_power.rs

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

feanor_math/rings/
direct_power.rs
