歐幾里得算法就是求最大公約數的展轉相除法。
用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取某兩個巨大的數時，展轉的次數超過百萬次。
我開始還不相信，又翻了幾頁發(fā)現用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