欧几里德的最大公约数算法对图灵机的复杂性(The complexity of Euclid'

考虑这个执行欧几里德算法：

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

上一个很好的证明维基百科表明该算法“总是需要小于O（1H）分裂，其中，h是在更小的数B的数字位数”。

然而，在一个图灵机，计算一个模B A过程为O的时间复杂度（A + B）。 我的直觉和一些大型的测试告诉我，对欧几里德算法复杂度仍然是一个图灵机O（B A +）。

任何思考如何证明？

Answer 1:

如果我是一个图灵机上实现对二进制数GCD，我会执行下面的算法。 我看不出怎么会是为O较小（（LN A + LN B）^ 2）虽然。 最有效的表现，我认为会按位第2步后，这两个值交错。

1. 让S1 =零的a的至少显著位的数量。 删除这些底部S1零位。
2. 让S2 =零的b中的至少显著位的数量。 删除这些底部S2零位。
3. 令s =分钟（S1，S2）
4. 现在，A和B都是奇数。 如果B <然后交换a和b。
5. B> =α。 集B = B - A，然后删除所有的最显著零从B位。
6. 若b！= 0，转到4。
7. 加s零位输出到的末尾。 这是结果。

文章来源: The complexity of Euclid's greatest common divisor algorithm on a Turing Machine