免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

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

辗转相除法是用来求两个(正)整数的最大公因数的,给定两个正整数$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$的上限。
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友
数学暗恋者,程序员,喜欢古典文学/历史,个人主页: https://zhcosin.coding.me/

回复 1# zhcosin

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

TOP

本帖最后由 zhcosin 于 2017-10-31 15:42 编辑

我想起来了,设$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}$.
数学暗恋者,程序员,喜欢古典文学/历史,个人主页: https://zhcosin.coding.me/

TOP

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

TOP

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

TOP

回复 5# hbghlyj
最坏情况下(也是一般情况下)每次除法只能降一次。。。

TOP

返回列表 回复 发帖