歐幾里得算法就是求最大公約數(shù)的展轉(zhuǎn)相除法。
用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說：當(dāng)m,n取某兩個巨大的數(shù)時，展轉(zhuǎn)的次數(shù)超過百萬次。
我開始還不相信，又翻了幾頁發(fā)現(xiàn)用fibonacci數(shù)就能找到展轉(zhuǎn)次數(shù)最多的兩個數(shù)，這兩個數(shù)就是F[n]和F[n+1]^_^，很容易驗(yàn)證最大展轉(zhuǎn)次數(shù)k = log
(n)，就是以黃金分割G為底n的對數(shù)。
寫到這里就算完了，但還須證明一個先決條件，就是fibonacci相臨兩項(xiàng)互質(zhì)。一個方法是利用這個性質(zhì)：
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]是互素的，因?yàn)槠渲腥魏喂蜃佣紝⑹?-1)^n的一個因子。
MK-TIANYI