| 前言 |
| 数学是科学的“皇后” |
次数n = (12 * ln2 * lnN) / π ^ 2 + 1.47 (N为其中较小的那个数)所以后面就只是考虑一个最坏的情况：M、N（M > N）是两个相邻的斐波那契数，程序是这样的（来源于该书）：
long gcd( long m, long n) {
while(n != 0) {
long rem = m %n;
m = n;
n = rem
}return m;
}- 假设M ≥ N ≥ 1（如果M < N，在第一次循环后，它们就会相互交换）;
- 定义一个数列{Remn}: Rem0 = M，Rem1 = N，Remn = Remn - 2 mod Remn - 1（n >= 2）;
- 如果算法需要进行n次迭代，则有Remn = gcd(M, N)，Remn + 1 = 0；
- 将数列{Remn}对比于斐波那契数列{Fbn}：Fb0 = 0 ≤ Remn，Fb1 = 1 ≤ Remn - 1；
- 由Remk mod Remk + 1 = Remk + 2 => Remk ≥ Remk + 1 + Remk + 2；
- 由数学归纳法可证明：Remk ≥ Fbn - k;
- 故：Rem1 = N ≥ Fbn - 1，表明如果需要做n次模运算，N必定不小于Fbn - 1；
- 由斐波那契数列通项公式（图片来源于这里，关于第一项为0还是1没有严格的限定）：
文章图片
可得N ≥ 1 / √5(((1 + √5) / 2) ^ (n - 1) - ((1- √5) / 2) ^ (n - 1)) => 次数n = O(log(N))。
最后一步的推理显得不是那么严谨，但大体的规律能够表现出来。其实对于这种最坏的情况，拉梅定理就给出了步数的计算公式。
| 总结 |
