上圖靈機

Question

歐幾里得最大公約數算法的複雜性考慮這個執行歐幾里德算法：

function gcd(a, b) 
    while b ≠ 0 
     t := b 
     b := a mod b 
     a := t 
    return a 

上wikipedia一個很好的證據表明，該算法「總是需要小於O（1H）部門，其中h是較小數字b「中的位數。

但是，在圖靈機上，計算mod b的過程的時間複雜度爲O（a + b）。我的直覺和一些大的測試告訴我，在圖靈機上，歐幾里德算法的複雜性仍然是O（a + b）。

有關如何證明這一點的任何想法？

Answer 1

如果我在一個圖靈機上的二進制數上實現GCD，我會實現以下算法。我看不出它會如何小於O（（ln a + ln b）^ 2）。我認爲最有效的表示方法是在步驟2之後按位交替兩個值。

1. 設s1 = a的最低有效位中的零的數量。刪除這些底部的s1零位。
2. 設s2 = b的最低有效位中的零的數量。刪除這些底部的s2零位。設定s = min（s1，s2）
3. 現在a和b都是奇數。如果b < a則交換a和b。
4. b> = a。設置b = b - a，然後從b中刪除所有最低有效的零位。
5. 如果b！= 0，轉到4.
6. 將零位添加到a的末尾。這是結果。