关于欧几里德算法复杂性的一点注记

A Note on the Complexity of Euclidean Algorithm

摘要: 让l（a,b）表示用欧几里德算法求两个正整数a>b的最大公因子时的迭代次数,文献1给出上界l（a,b）≤log₂（ab）。本文指出这个上界估值与由Lamé定理得到的估值l（a,b）<1.441log₂b₁相比没有优越性。

Abstract: Let l（a, b） denote the number of iterations of execution of Euclidean algorithm upon input data a and b with a>b>0. Li Xiaomingtgives l（a, b）<log₂（ab）. We point out that in any case this evaluation is not better than that of G. Lamé: l（a, b）<1.441log₂b+1, moreover the Lamé's depends only on the smaller one of two input data.