Struct BitwisexorConvolve

Source

pub struct BitwisexorConvolve<M, const TRY: bool = false> { /* private fields */ }

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 37)

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