Editing Greatest common divisor (section)

=== Binary GCD algorithm ===
{{Main|Binary GCD algorithm}}

The binary GCD algorithm is a variant of Euclid's algorithm that is specially adapted to the [[binary representation]] of the numbers, which is used in most [[computers]]. 

The binary GCD algorithm differs from Euclid's algorithm essentially by dividing by two every even number that is encountered during the computation. Its efficiency results from the fact that, in binary representation, testing parity consists of testing the right-most digit, and dividing by two consists of removing the right-most digit.

The method is as follows, starting with  {{math|''a''}} and {{math|''b''}} that are the two positive integers whose GCD is sought.
# If {{math|''a''}} and {{math|''b''}} are both even, then divide both by two until at least one of them becomes odd; let {{mvar|d}} be the number of these paired divisions.
# If {{math|''a''}} is even, then divide it by two until it becomes odd.
# If {{math|''b''}} is even, then divide it by two until it becomes odd.
#: Now, {{math|''a''}} and {{math|''b''}} are both odd and will remain odd until the end of the computation
# While {{math|''a'' ≠ ''b''}} do
#* If {{math|''a'' > ''b''}}, then replace  {{mvar|a}} with {{math|''a'' – ''b''}} and divide the result by two until {{mvar|a}} becomes odd (as {{math|''a''}} and {{math|''b''}} are both odd, there is, at least, one division by 2).
#* If {{math|''a'' < ''b''}}, then replace  {{mvar|b}} with {{math|''b'' – ''a''}} and divide the result by two until {{mvar|b}} becomes odd.
# Now, {{math|1=''a'' = ''b''}}, and the greatest common divisor is  <math>2^d a.</math>

Step 1 determines {{mvar|d}} as the highest power of {{math|2}} that divides {{math|''a''}} and {{math|''b''}}, and thus their greatest common divisor. None of the steps changes the set of the odd common divisors of {{math|''a''}} and {{math|''b''}}. This shows that when the algorithm stops, the result is correct. The algorithm stops eventually, since each steps divides at least one of the operands by at least {{math|2}}. Moreover, the number of divisions by {{math|2}} and thus the number of subtractions is at most the total number of digits.

Example: (''a'', ''b'', ''d'') = (48,  18, 0) → (24, 9, 1) → (12, 9, 1) → (6, 9, 1) → (3, 9, 1) → (3, 3, 1) ; the original GCD is thus the product 6 of {{math|1=2<sup>''d''</sup> = 2<sup>1</sup>}} and {{math|1=''a'' = ''b'' = 3}}.

The binary GCD algorithm is particularly easy to implement and particularly efficient on binary computers. Its [[computational complexity]] is
: <math>O((\log a + \log b)^2).</math>
The square in this complexity comes from the fact that division by {{math|2}} and subtraction take a time that is proportional to the number of [[bit]]s of the input.

The computational complexity is usually given in terms of the length {{math|''n''}} of the input. Here, this length is {{math|1=''n'' = log ''a'' + log ''b''}}, and the complexity is thus
: <math>O(n^2)</math>.