| 3 | return abs(a - b) < EPS; } |
| 4 | template <class Num> |
| 5 | vector<Num> berlekamp_massey(vector<Num> s) { |
| 6 | int m = 1, L = 0; bool sw; |
| 7 | vector<Num> C = {1}, B = {1}, T, res; Num b = 1, a; |
| 8 | rep(i,0,s.size()) { |
| 9 | Num d = s[i]; |
| 10 | rep(j,1,L+1) d = d + C[j] * s[i-j]; |
| 11 | if (eq(d,Num(0))) { m++; continue; } |
| 12 | if ((sw = 2*L <= i)) C.resize((L = i+1-L)+1), T = C; |
| 13 | a = d / b; for (int j = m; j < C.size(); j++) |
| 14 | C[j] = C[j] - a * B[j-m]; |
| 15 | m++; if (sw) B = T, b = d, m = 1; } |
| 16 | for (int i = 1; i <= L; i++) res.push_back(-C[i]); |
| 17 | return res; } |
| 18 | // vim: cc=60 ts=2 sts=2 sw=2: |