GNU Info

(gmp.info)Accelerated GCD

---

Next: Extended GCD Prev: Binary GCD Up: Greatest Common Divisor Algorithms

---

Enter node , (file) or (file)node

Accelerated GCD
---------------

   For sizes above `GCD_ACCEL_THRESHOLD', GMP uses the Accelerated GCD
algorithm described independently by Weber and Jebelean (the latter as
the "Generalized Binary" algorithm), Note: References.  This
algorithm is still O(N^2), but is much faster than the binary algorithm
since it does fewer multi-precision operations.  It consists of
alternating the k-ary reduction by Sorenson, and a "dmod" exact
remainder reduction.

   For operands u and v the k-ary reduction replaces u with n*v-d*u
where n and d are single limb values chosen to give two trailing zero
limbs on that value, which can be stripped.  n and d are calculated
using an algorithm similar to half of a two limb GCD (see `find_a' in
`mpn/generic/gcd.c').

   When u and v differ in size by more than a certain number of bits, a
dmod is performed to zero out bits at the low end of the larger.  It
consists of an exact remainder style division applied to an appropriate
number of bits (Note: Exact Division, and Note: Exact Remainder).
This is faster than a k-ary reduction but useful only when the operands
differ in size.  There's a dmod after each k-ary reduction, and if the
dmod leaves the operands still differing in size then it's repeated.

   The k-ary reduction step can introduce spurious factors into the GCD
calculated, and these are eliminated at the end by taking GCDs with the
original inputs gcd(u,gcd(v,g)) using the binary algorithm.  Since g is
almost always small this takes very little time.

   At small sizes the algorithm needs a good implementation of
`find_a'.  At larger sizes it's dominated by `mpn_addmul_1' applying n
and d.