欧几里得算法就是求最大公约数的展转相除法。
用c语言描述如下：
int Euclid_Algorithm (int m, int n) {
int temp = m;
if (!m || !n) return 0;
if (m < n) {m = n; n = temp;
} while (1) {
if (!(m = m % n)) return n;
if (!(n = n % m)) return m; }
knuth说：当m,n取某两个巨大的数时，展转的次数超过百万次。
我开始还不相信，又翻了几页发现用fibonacci数就能找到展转次数最多的两个数，这两个数就是F[n]和F[n+1]^_^，很容易验证最大展转次数k = log
(n)，就是以黄金分割G为底n的对数。
写到这里就算完了，但还须证明一个先决条件，就是fibonacci相临两项互质。一个方法是利用这个性质：
F[n-1] * F[n+1] - F[n]^2 = (-1)^n
=>F[n-1]^2 + F[n-1] * F[n] - F[n]^2 = (-1)^n
说明F[n-1]与F[n]是互素的，因为其中任何公因子都将是(-1)^n的一个因子。
MK-TIANYI