fn berlekamp_massey_naive<T>(a: &[T], max_work: usize) -> Option<Vec<T>>where
T: FormalPowerSeriesCoefficient,Examples found in repository?
crates/competitive/src/math/formal_power_series/berlekamp_massey.rs (line 232)
221 pub fn berlekamp_massey(input: &[T]) -> Self {
222 if input.last().is_none_or(|value| value.is_zero())
223 && input.iter().all(|value| value.is_zero())
224 {
225 return Self::one();
226 }
227 let max_work = if input.len() <= 1536 {
228 usize::MAX
229 } else {
230 input.len().saturating_mul(2)
231 };
232 if let Some(recurrence) = berlekamp_massey_naive(input, max_work) {
233 return Self::from_vec(recurrence);
234 }
235 let n = input.len();
236 let leading_zeros = input.iter().take_while(|value| value.is_zero()).count();
237 let sequence = Self::from_vec(input.to_vec()).trimed();
238 let mut modulus = Self::zeros(n + 1);
239 modulus[n] = T::one();
240 let (matrix, _) = half_gcd(&modulus, &sequence, n / 2, n.max(1).next_power_of_two());
241 let (x, y) = matrix.multiply_vector(&modulus, &sequence);
242 let mut recurrence = if y.length() == 0 {
243 matrix.a01.clone()
244 } else {
245 matrix.a11.clone()
246 };
247 let recurrence_leading_zeros = recurrence
248 .iter()
249 .take_while(|value| value.is_zero())
250 .count();
251 if recurrence_leading_zeros > 0 {
252 let (division, _) = x.div_rem(y.clone());
253 recurrence = add(recurrence * division, matrix.a01);
254 }
255 let inverse = T::one() / &recurrence[0];
256 for value in recurrence.iter_mut() {
257 *value *= &inverse;
258 }
259 let minimum_length = (leading_zeros + 2).max(y.length() + 1);
260 if recurrence.length() < minimum_length {
261 recurrence.resize(minimum_length);
262 }
263 recurrence
264 }