主題
Search

歐幾里得演算法

下載 Mathematica 筆記本下載 Wolfram 筆記本

歐幾里得演算法，也稱為歐幾里得輾轉相除法，是用於查詢兩個數 a 和 b 的最大公約數的演算法。該演算法也可以為比整數 Z 更一般的環定義。甚至存在不是歐幾里得環的主環，但可以在其中定義等效於歐幾里得演算法的演算法。有理數演算法在歐幾里得《幾何原本》的第七卷中給出。實數演算法出現在第十卷中，使其成為最早的整數關係演算法示例（Ferguson等人1999）。

歐幾里得演算法是一個P問題的例子，其時間複雜度受輸入值長度的二次函式限制（Bach 和 Shallit 1996）。

設 a=bq+r，然後找到一個數 u，它整除 a 和 b （因此 a=su 和 b=tu），那麼 u 也整除 r，因為

r=a-bq=su-qtu=(s-qt)u.
(1)

類似地，找到一個數 v，它整除 b 和 r （因此 b=s^'v 和 r=t^'v），那麼 v 也整除 a，因為

a=bq+r=s^'vq+t^'v=(s^'q+t^')v.
(2)

因此，a 和 b 的每個公約數也是 b 和 r 的公約數，因此該過程可以迭代如下

q_1=|_a/b_| a=bq_1+r_1 r_1=a-bq_1 ; q_2=|_b/(r_1)_| b=q_2r_1+r_2 r_2=b-q_2r_1 ; q_3=|_(r_1)/(r_2)_| r_1=q_3r_2+r_3 r_3=r_1-q_3r_2 ; q_4=|_(r_2)/(r_3)_| r_2=q_4r_3+r_4 r_4=r_2-q_4r_3 ; q_n=|_(r_(n-2))/(r_(n-1))_| r_(n-2)=q_nr_(n-1)+r_n r_n=r_(n-2) ; -q_nr_(n-1); q_(n+1)=|_(r_(n-1))/(r_n)_| r_(n-1)=q_(n+1)r_n+0 r_n=r_(n-1)/q_(n+1)
(3)

對於整數，當 q_(n+1) 恰好整除 r_(n-1) 時，演算法終止，此時 r_n 對應於 a 和 b 的最大公約數，GCD(a,b)=r_n。對於實數，該演算法產生精確關係或近似關係的無限序列（Ferguson等人1999）。

歐幾里得演算法的一個重要結果是找到整數 x 和 y，使得

ax+by=GCD(a,b).
(4)

這可以透過從 r_n 的方程開始，從前一個方程代入 r_(n-1)，並向上遍歷方程來完成。

請注意，r_i 只是餘數，因此可以透過手動重複計算以兩個感興趣的數字（較大的數字寫在前面）開始的連續項的餘數來輕鬆應用該演算法。例如，考慮將該演算法應用於 (a,b)=(42,30)。這給出 42, 30, 12, 6, 0，因此 GCD(42,30)=6。類似地，將該演算法應用於 (144, 55) 得到 144, 55, 34, 21, 13, 8, 5, 3, 2, 1, 0，因此 GCD(144,55)=1，並且 144 和 55 是互質的。

一個簡潔的 Wolfram 語言 實現可以如下給出。

  Remainder[a_, b_] := Mod[a, b]
  Remainder[a_, 0] := 0
  EuclideanAlgorithmGCD[a_, b_] := FixedPointList[
    {Last[#], Remainder @@ #}&, {a, b}][[-3, 1]]

拉梅證明，對於小於 n 的兩個數，到達最大公約數所需的步數為

steps<=(lnn)/(lnphi)+(lnsqrt(5))/(lnphi)
(5)

其中 phi 是黃金比例。在數值上，拉梅的表示式評估為

steps<=4.785log_(10)n+1.6723,
(6)

對於 n>=1，總是小於等於較小數的位數的 <=5 倍（Wells 1986，第 59 頁）。正如拉梅定理所示，最壞情況發生在將演算法應用於兩個連續的斐波那契數時。海爾布朗證明，對於所有對 (n,b)，其中 b<n，平均步數為 12ln2/pi^2lnn=0.843lnn。克羅內克證明，演算法的最短應用使用最小絕對餘數。獲得的商的分佈如下表所示（Wagon 1991）。

商%
141.5
217.0
39.3

設 T(m,n) 為使用歐幾里得演算法計算 GCD(m,n) 所需的除法次數，並定義 T(m,0)=0 如果 m>=0。那麼函式 T(m,n) 由遞推關係給出

T(m,n)={1+T(n,m mod n) for m>=n; 1+T(n,m) for m<n.
(7)

對於 0<=m<n，製表此函式得到

0 ; 0 1 ; 0 1 2 ; 0 1 1 2 ; 0 1 2 3 2 ; 0 1 1 1 2 2
(8)

（OEIS A051010）。給定 n=1、2、3、... 的最大步數為 1、2、2、3、2、3、4、3、3、4、4、5、... （OEIS A034883）。

EuclideanAlgorithmT

考慮函式

T(n)=1/nsum_(0<=m<n)T(m,n)
(9)

給出當 n 固定且 m 隨機選擇時的平均步數（Knuth 1998，第 344 頁和 353-357 頁）。T(n) 的前幾個值為 0, 1/2, 1, 1, 8/5, 7/6, 13/7, 7/4, ... （OEIS A051011 和 A051012）。Norton (1990) 表明

T(n)=(12ln2)/(pi^2)[lnn-sum_(d|n)(Lambda(d))/d]+C+1/nsum_(d|n)phi(d)O(d^(-1/6+epsilon)),
(10)

其中 Lambda(d) 是芒戈爾特函式，C 是波特常數（Knuth 1998，第 355-356 頁）。

EuclideanAlgorithmTau

相關函式

tau(n)=1/(phi(n))sum_(0<=m<n; GCD(m,n)=1)T(m,n)
(11)

其中 phi(n) 是尤拉總計函式，給出當 n 固定且 m 是與 n 互質的隨機數時的平均除法次數。Porter (1975) 表明

tau(n)=(12ln2)/(pi^2)lnn+C+O(n^(-1/6)+epsilon)
(12)

（Knuth 1998，第 354-355 頁）。

最後，定義

A(N)=1/(N^2)sum_(1<=m<=N; 1<=n<=N)T(m,n),
(13)

作為當 m 和 n 都在 [1,N] 中隨機選擇時的平均除法次數。Norton (1990) 證明

A(N)=(12ln2)/(pi^2)[lnN-1/2+6/(pi^2)zeta^'(2)]+C-1/2+O(N^(-1/6+epsilon)),
(14)

其中 zeta^'(z) 是黎曼 zeta 函式的導數。

存在 21 個二次域，其中存在歐幾里得演算法（Inkeri 1947，Barnes 和 Swinnerton-Dyer 1952）。

有關更多詳細資訊，請參見 Uspensky 和 Heaslet (1939) 以及 Knuth (1998)。

儘管為推廣演算法以找到 n>=3 個變數之間的整數關係做出了各種嘗試，但在Ferguson-Forcade 演算法被發現之前，沒有一個成功（Ferguson等人1999）。現在已經發現了其他幾種整數關係演算法。

另請參閱

Blankinship 演算法，歐幾里得環，Ferguson-Forcade 演算法，半 GCD，整數關係，二次域 在 課堂中探索此主題

使用 探索

參考文獻

Bach, E. 和 Shallit, J. 演算法數論，第 1 卷：高效演算法。 Cambridge, MA: MIT Press, 1996.Barnes, E. S. 和 Swinnerton-Dyer, H. P. F. "二元二次型的非齊次極小值。I." Acta Math 87, 259-323, 1952.Chabert, J.-L. (Ed.). "歐幾里得演算法。" 第 4 章，演算法的歷史：從卵石到微晶片。 New York: Springer-Verlag, pp. 113-138, 1999.Cohen, H. 計算代數數論課程。 New York: Springer-Verlag, 1993.Courant, R. 和 Robbins, H. "歐幾里得演算法。" 第 2.4 節，第 1 章的補充，什麼是數學？：思想和方法的初等方法，第 2 版。 Oxford, England: Oxford University Press, pp. 42-51, 1996.Dunham, W. 天才之旅：數學的偉大定理。 New York: Wiley, pp. 69-70, 1990.Ferguson, H. R. P.; Bailey, D. H.; 和 Arno, S. "PSLQ 的分析，一種整數關係查詢演算法。" Math. Comput. 68, 351-369, 1999.Finch, S. R. "波特-漢斯利常數。" 第 2.18 節，數學常數。 Cambridge, England: Cambridge University Press, pp. 156-160, 2003.Inkeri, K. "關於二次數域中的歐幾里得演算法。" Ann. Acad. Sci. Fennicae. Ser. A. I. Math.-Phys. 1947, 1-35, 1947.Knuth, D. E. 計算機程式設計藝術，第 1 卷：基本演算法，第 3 版。 Reading, MA: Addison-Wesley, 1997.Knuth, D. E. 計算機程式設計藝術，第 2 卷：半數值演算法，第 3 版。 Reading, MA: Addison-Wesley, 1998.Motzkin, T. "歐幾里得演算法。" Bull. Amer. Math. Soc. 55, 1142-1146, 1949.Nagell, T. "歐幾里得演算法。" 第 7 節，數論導論。 New York: Wiley, pp. 21-23, 1951.Norton, G. H. "關於歐幾里得演算法的漸近分析。" J. Symb. Comput. 10, 53-58, 1990.Porter, J. W. "關於海爾布朗定理。" Mathematika 22, 20-28, 1975.Séroul, R. "歐幾里得除法" 和 "歐幾里得演算法。" 第 2.1 節和 8.1 節，程式設計師數學。 Berlin: Springer-Verlag, pp. 5 和 169-161, 2000.Sloane, N. J. A. 序列 A034883, A051010, A051011, 和 A051012，在 "整數序列線上百科全書" 中。Uspensky, J. V. 和 Heaslet, M. A. 初等數論。 New York: McGraw-Hill, 1939.Wagon, S. "古老而現代的歐幾里得演算法" 和 "擴充套件歐幾里得演算法。" 第 8.1 節和 8.2 節，Mathematica 在行動。 New York: W. H. Freeman, pp. 247-252 和 252-256, 1991.Wells, D. 好奇和有趣的數字企鵝詞典。 Middlesex, England: Penguin Books, p. 59, 1986.

請引用為

Weisstein, Eric W. "歐幾里得演算法。" 來自 Web 資源。 https://mathworld.tw/EuclideanAlgorithm.html

學科分類