我发现很难计算二进制GCD算法的时间复杂度，也称为Stein算法，它被给定为O（n^2），其中n是两个数字中较大的一个数字中的位数。不应该是O（n）吗算法如下：
1.gcd（0，v）=v，因为所有事物都除以零，而v是除以v的最大数。类似地，gcd（u，0）=u。gcd（0,0）通常没有定义，但设置gcd（0,0）=0很方便。
2.如果u和v都是偶数，那么gcd（u，v）=2·gcd（u/2，v/2），因为2是公约数。
3.如果u是偶数，v是奇数，那么gcd（u，v）=gcd（u/2，v），因为2不是公约数。类似地，如果u是奇数，v是偶数，则gcd（u，v）=gcd（u，v/2）。
4.如果u和v都是奇数，并且u≥v，则gcd（u，v）=gcd（（u−v）/2，v）。如果两者都是奇数并且u<v、 则gcd（u，v）=gcd（（v−u）/2，u）。这些是简单欧几里得算法的一个步骤的组合，该算法在每个步骤使用减法，以及上面步骤3的应用。除以2得到一个整数，因为两个奇数的差是偶数。[3]
5.重复步骤2-4，直到u=v，或（再重复一步）直到u=0。在任何一种情况下，GCD都是2kv，其中k是在步骤2中找到的2的公共因子的数量。
Knuth第2卷有一个非常复杂的分析，它似乎证实了一个明显的猜测，即步数在最坏情况下是输入位数的线性。然而，对于非常大的n，每个减法都需要单独记为O（n）（例如，由于多精度算术），在这种情况下，总账单为O（n^2）