Implementation of GCD for small integers

ecir hana ecir.hana at
Sun Oct 23 12:00:32 UTC 2016

Dear list!

While trying to implement (faster) GCD for integers I found vast amount of
literature and algorithms, and so I was wondering if someone could please
help me to sort out the basics.

- Somewhere between GMP 4.1 and 5.0 the algorithm for finding the divisor
of integers smaller than GCD_ACCEL_THRESHOLD/GCD_DC_THRESHOLD changed from
"Generalized Binary" algorithm to the "A Double-Digit Lehmer-Euclid
Algorithm". Why? I presume because it was faster but by how much? Are there
any references documenting the reasoning behind the change?

- Does anyone know of a recent comparison between the various kinds of
binary and Lehmer's algorithms? I'm asking because apparently GMP uses "A
Double-Digit Lehmer-Euclid Algorithm" but for instance Jebelean describes
other fast algorithms in "Comparing Several GCD Algorithms" so I was
wondering whether there are other comparatively fast (or faster) algorithms
than the once GMP currently uses?

- I guess my main problem is how to choose from the many variants of GCD
algorithm for "small" integers: which exact paper should I follow for
Lehmer's algorithm? Isn't the "k-ary" method, or some variation of it, by
Sorenson, or others, faster? What about the one Weber ("The accelerated GCD

Thank you very much in advance, I would be grateful for any information,
link, paper, comparison, ...

Ecir Hana

More information about the gmp-discuss mailing list