2.2 Binary GCD algorithm

Using the idea that division and multiplication by powers of two is a ``quick'' operation for computers (based on binary arithmetic) and the fact that the difference between two odd numbers is even, we can write an algorithm for GCD that does not use division (except by 2) at all.

First of all we find the 2-adic values (say m and n) of a and b and also replace a and b by a/2^m and b/2ⁿ respectively. As we saw above this can be done in time that is linear in the size of a and b. Let k denote the minimum of m and n. We now begin the iterative step.

For this iteration a and b will always be odd. First we compute c - $\rho$ ^. M^p = a - b (where $\rho$ is the ``borrow''). If $\rho$ = 1, then we replace c by its bitwise negation $\tt bneg$ (c) and then add 1 (this replaces c by M^p - c; the sign of c is then (- 1)^$\rho$). If c is zero then the GCD is 2^{k .} a. Otherwise, we calculate the 2-adic value l of c and replace c by c/2^l so that c is odd once more. Since l is usually a smaller than log(M) this step is linear in the size of c. Now if $\rho$ = 1 then we replace b by c and if $\rho$ = 0 then we replace a by c and iterate. (Thus we replace a if it is larger and b if it is larger).

Note that this involves no divisions at all. Thus it can be very fast in principle. Each iteration reduces the size of the largest of a and b by at least one bit. Thus there are at most as many steps as log₂(a). Moreover, if a = 2^N - 1 and b = 1, then we can see that the process takes exactly N steps. Thus, quite often an initial division is performed in order to ensure that a and b have roughly the same size (this condition reduces the number of iterations for all GCD algorithms).