[数论] 辗转相除法的步数上限

zhcosin

辗转相除法是用来求两个（正）整数的最大公因数的，给定两个正整数$a$和$b$，设$a>b$，那么按带余除法，有$a=qb+r$，其中$q$和$r$都是整数并且$0 \leqslant r < b$，分别称为$a$除以$b$所得的商和余数，如果$r \neq 0$，则再拿$b$除以$r$得余数$r_1$，如果$r_1$仍然不为零，则继续拿$r$除以$r_1$得余数$r_2$，依次下去，由于每做一次除法，所得余数必定减少一，所以这个过程必定在有限步之内结束，即进行到某一步后必然有$r_n=0$，显然这个步数不会超过$b$，所以问题就来了，这个步数，能否表示成$a$和$b$的二元函数，或者能得出一个上限也可以。印象中看到过一个是$\log_2 b$的上限。

hbghlyj

这个计算机科学讲义的Prop 6.1.3(第8页)$\newcommand{\S}{§}$
Prop 6.1.3. Given two numbers $n$ and $m$, with $n \geq m$, let $f_{r}$ be the smallest Fibonacci number that exceeds $n$. Then the number of recursive calls in the Euclidean algorithm is at most $r$.
Proof: Suppose that there are $s$ calls. Then let
$$
n_{0}, n_{1}, \ldots, n_{s}
$$
be the sequence of values of the first argument in the successive calls. Thus,
$$
n_{0}=n \quad \text { and } \quad n_{s}=\operatorname{gcd}(n, m)
$$We observe that $n_{s} \geq 1>f_{0}$ and that $n_{s-1} \geq 2>f_{1}$. It follows by induction, in general, that
$$
n_{s-k-2}>f_{k+2}=f_{k+1}+f_{k}
$$
because
$$
n_{s-k-2} \geq n_{s-k-1}+n_{s-k}>f_{k+1}+f_{k}
$$
In particular, $n_{0}>f_{s}$. Therefore, $s<r$.
Remark: Intuitively, the number of recursive calls is at its largest, relative to the size of the numbers supplied as input, when the input supplied is two consecutive Fibonacci numbers, since then all the quotients are 1 , each remainder is the next lower Fibonacci number, and the numbers passed in the recursion are reduced as little as possible at each step. Since the growth of the Fibonacci sequence is exponential, as we proved in $\S 2.5$, we conclude that in this computationally "worst case", the number of recursive calls is proportional to the logarithm of the size of the input.

hbghlyj

如果换作求两个多项式A,B(degA=a$\geq$b=degB)的H.C.F，最坏需要做b次除法，这个数字很固定，同时说明多项式辗转相除法很低效。举两个三次多项式为例

2019-9-22 03:26

zhcosin

话说关于这个步数$E(a,b)$，有没有更细致的结果？

zhcosin

我想起来了，设$a>b$，有一连串等式
\begin{align*}
a & =  q_0b+r_1 \\
r & = q_1 r_1+r_2 \\
&\cdots \\
r_{k-1}&=q_k r_k + r_{k+1} \\
&\cdots \\
r_{n-2}&=q_{n-1}r_{n-1}+r_n
\end{align*}
最后一式中$r_n=0$，易知$r_i$依次递减，且相邻两个$r_i$至少相差1，所以
\[ r_{k-1}=q_k r_k + r_{k+1} \geqslant r_k + r_{k+1}  \]
联系到斐波那契数列，令$s_k=r_{n-k}$，则$s_0=r_n=0, s_1=r_{n-1} \geqslant 1,  s_2=r_{n-2} \geqslant 2$，且
\[ s_{n-k+1} \geqslant s_{n-k}+s_{n-k-1}   \]
即
\[ s_{k+1} \geqslant s_{k}+s_{k-1} \]
于是按照数学归纳法，易知$s_k \geqslant F_k(k \geqslant 1)$，这里$F_k$是第$k$个斐波那契数。

而$s_n=r_0=b$，所以$b \geqslant F_n$，所以得到结论：假如辗转相除法进行了$n$步除法后才得出余数为零，那么$\min\{a,b\} \geqslant F_n$.

又因为
\[ F_n = \frac{1}{\sqrt{5}} \left( (\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n \right) \]
所以
\[ F_n \sim \frac{1}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^n  \]
所以近似的得到
\[ n \leqslant \log_{\phi} (\sqrt{5}\min\{a,b\}) \]
其中$\phi=\frac{1+\sqrt{5}}{2}$.

abababa

回复 1# zhcosin

网友曾经给我讲过这个，不过用的是常用对数，以10为底的那个。最小的$x,y(x<y)$就是斐波那契数列里的第$n+1,n+2$项，如果在第n步停止，那么小的那个数$x\ge f_{n+1}$，最后用对数估计法得出$n$不超过$x$位数的5倍。所以对于100位的$x$，在500次以内必定停止。