Struct BitwisexorConvolve

Source

pub struct BitwisexorConvolve<M, const TRY: bool = false> {
    _marker: PhantomData<fn() -> M>,
}

Fields§

§_marker: PhantomData<fn() -> M>

Implementations§

Source §

impl<G, const TRY: bool> BitwisexorConvolve<G, TRY>
where G: Group,

Source

pub fn hadamard_transform(f: &mut [G::T])

Examples found in repository ?

crates/competitive/src/math/bitwisexor_convolve.rs (line 33)

32    fn transform(mut t: Self::T, _len: usize) -> Self::F {
33        BitwisexorConvolve::<R::Additive, false>::hadamard_transform(&mut t);
34        t
35    }
36
37    fn inverse_transform(mut f: Self::F, len: usize) -> Self::T {
38        BitwisexorConvolve::<R::Additive, false>::hadamard_transform(&mut f);
39        let len = R::T::from(len);
40        for f in f.iter_mut() {
41            *f = R::div(f, &len);
42        }
43        f
44    }
45
46    fn multiply(f: &mut Self::F, g: &Self::F) {
47        for (f, g) in f.iter_mut().zip(g) {
48            *f = R::mul(f, g);
49        }
50    }
51
52    fn convolve(a: Self::T, b: Self::T) -> Self::T {
53        assert_eq!(a.len(), b.len());
54        let len = a.len();
55        let same = a == b;
56        let mut a = Self::transform(a, len);
57        if same {
58            for a in a.iter_mut() {
59                *a = R::mul(a, a);
60            }
61        } else {
62            let b = Self::transform(b, len);
63            Self::multiply(&mut a, &b);
64        }
65        Self::inverse_transform(a, len)
66    }
67}
68
69impl<R> ConvolveSteps for BitwisexorConvolve<R, true>
70where
71    R: Field<T: PartialEq + TryFrom<usize>, Additive: Invertible, Multiplicative: Invertible>,
72    <R::T as TryFrom<usize>>::Error: Debug,
73{
74    type T = Vec<R::T>;
75    type F = Vec<R::T>;
76
77    fn length(t: &Self::T) -> usize {
78        t.len()
79    }
80
81    fn transform(mut t: Self::T, _len: usize) -> Self::F {
82        BitwisexorConvolve::<R::Additive, true>::hadamard_transform(&mut t);
83        t
84    }
85
86    fn inverse_transform(mut f: Self::F, len: usize) -> Self::T {
87        BitwisexorConvolve::<R::Additive, true>::hadamard_transform(&mut f);
88        let len = R::T::try_from(len).unwrap();
89        for f in f.iter_mut() {
90            *f = R::div(f, &len);
91        }
92        f
93    }