Struct SubsetConvolve

Source

pub struct SubsetConvolve<M> {
    _marker: PhantomData<fn() -> M>,
}

Fields§

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

Implementations§

Source §

impl<R> SubsetConvolve<R>
where R: Ring<T: PartialEq, Additive: Invertible>,

Source

fn ranked(t: Vec<R::T>, len: usize) -> (Vec<R::T>, usize)

Examples found in repository ?

crates/competitive/src/math/subset_convolve.rs (line 63)

62    fn transform(t: Self::T, len: usize) -> Self::F {
63        let (mut f, width) = Self::ranked(t, len);
64        let k = width - 1;
65        for bit in 0..k {
66            let half = 1 << bit;
67            for base in (0..len).step_by(half * 2) {
68                for lower in base..base + half {
69                    let upper = lower + half;
70                    let ranks = lower.count_ones() as usize + 1;
71                    let (lower_rows, upper_rows) = f.split_at_mut(upper * width);
72                    let lower_row = &lower_rows[lower * width..lower * width + ranks];
73                    let upper_row = &mut upper_rows[..ranks];
74                    for (upper, lower) in upper_row.iter_mut().zip(lower_row) {
75                        R::add_assign(upper, lower);
76                    }
77                }
78            }
79        }
80        (f, width)
81    }
82
83    fn inverse_transform((mut f, width): Self::F, len: usize) -> Self::T {
84        let k = width - 1;
85        for bit in 0..k {
86            let half = 1 << bit;
87            for base in (0..len).step_by(half * 2) {
88                for lower in base..base + half {
89                    let upper = lower + half;
90                    let rank = lower.count_ones() as usize;
91                    let (lower_rows, upper_rows) = f.split_at_mut(upper * width);
92                    let lower_row = &lower_rows[lower * width + rank..lower * width + width];
93                    let upper_row = &mut upper_rows[rank..width];
94                    for (upper, lower) in upper_row.iter_mut().zip(lower_row) {
95                        R::sub_assign(upper, lower);
96                    }
97                }
98            }
99        }
100        Self::diagonal(f, width)
101    }
102
103    fn multiply(f: &mut Self::F, g: &Self::F) {
104        let (f, width) = f;
105        let (g, _) = g;
106        let mut right = vec![R::zero(); *width];
107        let mut output = vec![R::zero(); *width];
108        for (i, f) in f.chunks_exact_mut(*width).enumerate() {
109            let rank = i.count_ones() as usize;
110            let g = &g[i * *width..(i + 1) * *width];
111            let end = Self::multiply_row(f, g, &mut right, &mut output, rank);
112            f[rank..=end].clone_from_slice(&output[rank..=end]);
113        }
114    }
115
116    fn convolve(a: Self::T, b: Self::T) -> Self::T {
117        assert_eq!(a.len(), b.len());
118        let len = a.len();
119        let same = a == b;
120        let (mut x, width) = Self::ranked(a, len);
121        let (mut y, _) = if same {
122            (x.clone(), width)
123        } else {
124            Self::ranked(b, len)
125        };
126        let mut right = vec![R::zero(); width];
127        let mut output = vec![R::zero(); width];
128        for i in 0..len {
129            for bit in (0..(i | len).trailing_zeros() as usize).rev() {
130                let half = width << bit;
131                let start = i * width;
132                let (lower, upper) = x[start..start + half * 2].split_at_mut(half);
133                for (upper, lower) in upper.iter_mut().zip(lower) {
134                    R::add_assign(upper, lower);
135                }
136                let (lower, upper) = y[start..start + half * 2].split_at_mut(half);
137                for (upper, lower) in upper.iter_mut().zip(lower) {
138                    R::add_assign(upper, lower);
139                }
140            }
141
142            let rank = i.count_ones() as usize;
143            let start = i * width;
144            let x_row = &x[start..start + width];
145            let y_row = &y[start..start + width];
146            output.fill(R::zero());
147            Self::multiply_row(x_row, y_row, &mut right, &mut output, rank);
148            x[start..start + width].clone_from_slice(&output);
149
150            for bit in 0..i.trailing_ones() as usize {
151                let end = (i + 1) * width;
152                let half = width << bit;
153                let (lower, upper) = x[end - half * 2..end].split_at_mut(half);
154                for (upper, lower) in upper.iter_mut().zip(lower) {
155                    R::sub_assign(upper, lower);
156                }
157            }
158        }
159        Self::diagonal(x, width)
160    }

Source

fn diagonal(ranked: Vec<R::T>, width: usize) -> Vec<R::T>

Examples found in repository ?

crates/competitive/src/math/subset_convolve.rs (line 100)

83    fn inverse_transform((mut f, width): Self::F, len: usize) -> Self::T {
84        let k = width - 1;
85        for bit in 0..k {
86            let half = 1 << bit;
87            for base in (0..len).step_by(half * 2) {
88                for lower in base..base + half {
89                    let upper = lower + half;
90                    let rank = lower.count_ones() as usize;
91                    let (lower_rows, upper_rows) = f.split_at_mut(upper * width);
92                    let lower_row = &lower_rows[lower * width + rank..lower * width + width];
93                    let upper_row = &mut upper_rows[rank..width];
94                    for (upper, lower) in upper_row.iter_mut().zip(lower_row) {
95                        R::sub_assign(upper, lower);
96                    }
97                }
98            }
99        }
100        Self::diagonal(f, width)
101    }
102
103    fn multiply(f: &mut Self::F, g: &Self::F) {
104        let (f, width) = f;
105        let (g, _) = g;
106        let mut right = vec![R::zero(); *width];
107        let mut output = vec![R::zero(); *width];
108        for (i, f) in f.chunks_exact_mut(*width).enumerate() {
109            let rank = i.count_ones() as usize;
110            let g = &g[i * *width..(i + 1) * *width];
111            let end = Self::multiply_row(f, g, &mut right, &mut output, rank);
112            f[rank..=end].clone_from_slice(&output[rank..=end]);
113        }
114    }
115
116    fn convolve(a: Self::T, b: Self::T) -> Self::T {
117        assert_eq!(a.len(), b.len());
118        let len = a.len();
119        let same = a == b;
120        let (mut x, width) = Self::ranked(a, len);
121        let (mut y, _) = if same {
122            (x.clone(), width)
123        } else {
124            Self::ranked(b, len)
125        };
126        let mut right = vec![R::zero(); width];
127        let mut output = vec![R::zero(); width];
128        for i in 0..len {
129            for bit in (0..(i | len).trailing_zeros() as usize).rev() {
130                let half = width << bit;
131                let start = i * width;
132                let (lower, upper) = x[start..start + half * 2].split_at_mut(half);
133                for (upper, lower) in upper.iter_mut().zip(lower) {
134                    R::add_assign(upper, lower);
135                }
136                let (lower, upper) = y[start..start + half * 2].split_at_mut(half);
137                for (upper, lower) in upper.iter_mut().zip(lower) {
138                    R::add_assign(upper, lower);
139                }
140            }
141
142            let rank = i.count_ones() as usize;
143            let start = i * width;
144            let x_row = &x[start..start + width];
145            let y_row = &y[start..start + width];
146            output.fill(R::zero());
147            Self::multiply_row(x_row, y_row, &mut right, &mut output, rank);
148            x[start..start + width].clone_from_slice(&output);
149
150            for bit in 0..i.trailing_ones() as usize {
151                let end = (i + 1) * width;
152                let half = width << bit;
153                let (lower, upper) = x[end - half * 2..end].split_at_mut(half);
154                for (upper, lower) in upper.iter_mut().zip(lower) {
155                    R::sub_assign(upper, lower);
156                }
157            }
158        }
159        Self::diagonal(x, width)
160    }

Source

fn multiply_row( x: &[R::T], y: &[R::T], right: &mut [R::T], output: &mut [R::T], rank: usize, ) -> usize

Examples found in repository ?

crates/competitive/src/math/subset_convolve.rs (line 111)

103    fn multiply(f: &mut Self::F, g: &Self::F) {
104        let (f, width) = f;
105        let (g, _) = g;
106        let mut right = vec![R::zero(); *width];
107        let mut output = vec![R::zero(); *width];
108        for (i, f) in f.chunks_exact_mut(*width).enumerate() {
109            let rank = i.count_ones() as usize;
110            let g = &g[i * *width..(i + 1) * *width];
111            let end = Self::multiply_row(f, g, &mut right, &mut output, rank);
112            f[rank..=end].clone_from_slice(&output[rank..=end]);
113        }
114    }
115
116    fn convolve(a: Self::T, b: Self::T) -> Self::T {
117        assert_eq!(a.len(), b.len());
118        let len = a.len();
119        let same = a == b;
120        let (mut x, width) = Self::ranked(a, len);
121        let (mut y, _) = if same {
122            (x.clone(), width)
123        } else {
124            Self::ranked(b, len)
125        };
126        let mut right = vec![R::zero(); width];
127        let mut output = vec![R::zero(); width];
128        for i in 0..len {
129            for bit in (0..(i | len).trailing_zeros() as usize).rev() {
130                let half = width << bit;
131                let start = i * width;
132                let (lower, upper) = x[start..start + half * 2].split_at_mut(half);
133                for (upper, lower) in upper.iter_mut().zip(lower) {
134                    R::add_assign(upper, lower);
135                }
136                let (lower, upper) = y[start..start + half * 2].split_at_mut(half);
137                for (upper, lower) in upper.iter_mut().zip(lower) {
138                    R::add_assign(upper, lower);
139                }
140            }
141
142            let rank = i.count_ones() as usize;
143            let start = i * width;
144            let x_row = &x[start..start + width];
145            let y_row = &y[start..start + width];
146            output.fill(R::zero());
147            Self::multiply_row(x_row, y_row, &mut right, &mut output, rank);
148            x[start..start + width].clone_from_slice(&output);
149
150            for bit in 0..i.trailing_ones() as usize {
151                let end = (i + 1) * width;
152                let half = width << bit;
153                let (lower, upper) = x[end - half * 2..end].split_at_mut(half);
154                for (upper, lower) in upper.iter_mut().zip(lower) {
155                    R::sub_assign(upper, lower);
156                }
157            }
158        }
159        Self::diagonal(x, width)
160    }