GNU Info

(gmp.info)Binary GCD

---

Next: Accelerated GCD Prev: Greatest Common Divisor Algorithms Up: Greatest Common Divisor Algorithms

---

Enter node , (file) or (file)node

Binary GCD
----------

   At small sizes GMP uses an O(N^2) binary style GCD.  This is
described in many textbooks, for example Knuth section 4.5.2 algorithm
B.  It simply consists of successively reducing operands a and b using
gcd(a,b) = gcd(min(a,b),abs(a-b)), and also that if a and b are first
made odd then abs(a-b) is even and factors of two can be discarded.

   Variants like letting a-b become negative and doing a different next
step are of interest only as far as they suit particular CPUs, since on
small operands it's machine dependent factors that determine
performance.

   The Euclidean GCD algorithm, as per Knuth algorithms E and A,
reduces using a mod b but this has so far been found to be slower
everywhere.  One reason the binary method does well is that the implied
quotient at each step is usually small, so often only one or two
subtractions are needed to get the same effect as a division.
Quotients 1, 2 and 3 for example occur 67.7% of the time, see Knuth
section 4.5.3 Theorem E.

   When the implied quotient is large, meaning b is much smaller than
a, then a division is worthwhile.  This is the basis for the initial a
mod b reductions in `mpn_gcd' and `mpn_gcd_1' (the latter for both Nx1
and 1x1 cases).  But after that initial reduction, big quotients occur
too rarely to make it worth checking for them.