图灵机上欧几里得最大公约数算法的复杂性

Question

考虑Euclid算法的实现：

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

Wikipedia上的一个很好的证据表明，算法"总是需要小于O（H）部门，其中H是较小数字B中的数字数"。

但是，在图灵机上，计算A 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零位。
3. 让S = min（S1，S2）
4. 现在A和B都是奇怪的。如果B＆lt;一个然后交换A和b。
5. b> = a。集b = b - a，然后从b中删除所有最低的零位。
6. 如果b！= 0，goto 4。
7. 将s零位添加到a的末端。这是结果。