这一算法来自于我们对“线性递推式拟合”的视角转换,其后得到的算法是自然的。
引理 1. 如果两个有理分式
p
1
/
q
1
,
p
2
/
q
2
p_1/q_1, p_2/q_2
p1/q1,p2/q2 均有
deg
p
<
n
,
deg
q
≤
n
\deg p<n, \deg q\leq n
degp<n,degq≤n 且展开式
p
1
/
q
1
≡
p
2
/
q
2
(
m
o
d
x
2
n
)
p_1/q_1 \equiv p_2/q_2 \pmod {x^{2n}}
p1/q1≡p2/q2(modx2n),那么
p
1
/
q
1
=
p
2
/
q
2
p_1/q_1 = p_2/q_2
p1/q1=p2/q2。
证明. 通分,等价于
p
1
q
2
=
q
1
p
2
p_1q_2=q_1p_2
p1q2=q1p2,由两边次数均
<
2
n
<2n
<2n,而同余式保留了全部信息。
这一引理告诉我们,若一个
n
n
n 阶线性递推式确实拟合了其前
2
n
2n
2n 项,那么通分之后就一定是“最小”的。
为了解决这一问题,我们首先将问题适当泛化:
「有理函数重建」(Rational Function Reconstruction):给定域上的多项式
f
(
x
)
,
M
(
x
)
f(x),M(x)
f(x),M(x),设
deg
M
=
n
\deg M = n
degM=n,当多项式
p
,
q
p,q
p,q 满足
deg
q
≤
n
−
k
,
deg
p
<
k
\deg q \leq n-k, \deg p < k
degq≤n−k,degp<k 时,若
p
≡
q
f
(
m
o
d
M
)
p\equiv qf \pmod M
p≡qf(modM),那么称
p
,
q
p,q
p,q 是一个
(
k
,
n
−
k
)
(k,n-k)
(k,n−k) 有理逼近。
接下来,我们将发现任何一个
k
k
k,都存在
(
k
,
n
−
k
)
(k,n-k)
(k,n−k) 有理逼近。将同余式写作
p
≡
q
f
+
M
t
p\equiv qf + Mt
p≡qf+Mt,这诱导我们考虑欧几里得过程:最初有
[
f
M
]
=
[
1
0
0
1
]
[
f
M
]
\begin{bmatrix} f\\ M \end{bmatrix}= \begin{bmatrix} 1 & 0\\ 0 & 1\\ \end{bmatrix} \begin{bmatrix} f\\ M \end{bmatrix}
[fM]=[1001][fM]
在欧几里得的过程中,有中间量
[
A
B
]
=
[
X
A
Y
A
X
B
Y
B
]
[
f
M
]
\begin{bmatrix} A\\ B \end{bmatrix}= \begin{bmatrix} X_A & Y_A\\ X_B & Y_B\\ \end{bmatrix} \begin{bmatrix} f\\ M \end{bmatrix}
[AB]=[XAXBYAYB][fM]
不妨设
k
−
1
=
deg
A
≥
deg
B
=
m
k-1=\deg A \ge \deg B=m
k−1=degA≥degB=m,那么我们接下来进行多项式取模,就应当逐步将
A
A
A 的度数从
<
k
<k
<k 降到
<
m
<m
<m,然后交换
A
,
B
A,B
A,B。此时我们归纳假设
deg
X
A
,
deg
X
B
≤
n
−
k
\deg X_A, \deg X_B \leq n-k
degXA,degXB≤n−k,那么由于辗转相除
A
−
d
B
A-dB
A−dB 的系数有
deg
d
<
k
−
m
\deg d < k-m
degd<k−m,可知
f
f
f 的系数
X
A
−
d
X
B
X_A-dX_B
XA−dXB,那么新的系数为
X
A
−
d
X
B
,
X
B
X_A-dX_B,X_B
XA−dXB,XB。度数均
<
n
−
m
< n-m
<n−m。
我们现在设
k
′
=
m
+
1
,
m
′
=
deg
(
A
−
d
B
)
k'=m+1,m'=\deg (A-dB)
k′=m+1,m′=deg(A−dB),也就有新的系数的度数均
≤
n
−
k
′
\le n-k'
≤n−k′。注意我们每次辗转相除后得到的
(
k
,
n
−
k
)
(k,n-k)
(k,n−k) 有理逼近的
k
k
k 是一段区间,且刚好拼出了
1
∼
n
1\sim n
1∼n 的所有整数。取对应的
p
=
A
,
q
=
X
A
p=A,q=X_A
p=A,q=XA 即可。
辗转相除过程的这个序列通过 HALF-GCD 算法可以在
Θ
(
n
log
2
n
)
\Theta(n\log ^2n)
Θ(nlog2n) 时间内计算。严格来说,我们是通过 HALF-GCD 算法计算出的矩阵列,可以算出任何一个阶段的有理函数重建。但对于我们对线性递推式的计算而言,只做
n
n
n 消到
n
/
2
n/2
n/2 这第一轮刚好足够我们求出信息。
不过这里似乎
p
,
q
p,q
p,q 是可能有
x
x
x 的幂的,但如果将引理 1 稍微改改就会发现,如果我们给的数列真的有一个递推式,那就算
p
,
q
p,q
p,q 有
x
x
x 的幂,通分之后肯定还是正确的。
版权归原作者 Entropy Increaser 所有, 如有侵权,请联系我们删除。