Editing Binary GCD algorithm (section)

==Complexity==
[[Big O notation|Asymptotically]], the algorithm requires <math>O(n)</math> steps, where <math>n</math> is the number of bits in the larger of the two numbers, as every two steps reduce at least one of the operands by at least a factor of <math>2</math>.  Each step involves only a few arithmetic operations (<math>O(1)</math> with a small constant); when working with [[Word (computer architecture)|word-sized]] numbers, each arithmetic operation translates to a single machine operation, so the number of machine operations is on the order of <math>n</math>, i.e. <math>\log_{2}(\max(u, v))</math>.

For arbitrarily large numbers, the [[asymptotic notation|asymptotic complexity]] of this algorithm is <math>O(n^2)</math>,<ref name="gmplib"/> as each arithmetic operation (subtract and shift) involves a linear number of machine operations (one per word in the numbers' binary representation).
If the numbers can be represented in the machine's memory, ''i.e.'' each number's ''size'' can be represented by a single machine word, this bound is reduced to:
<math display="block">
O\left(\frac{n^2}{\log_2 n}\right)
</math>

This is the same as for the Euclidean algorithm, though a more precise analysis by Akhavi and Vallée proved that binary GCD uses about 60% fewer bit operations.<ref name="bit-complexity"/>