A double-digit Lehmer-Euclid algorithm for finding the GCD of long integers (Q1895406)

This paper discusses several useful techniques for improving the performance of \textit{D. H. Lehmer}'s multiprecision algorithm for computing greatest common divisors [Am. Math. Mon. 45, 227--233 (1938; Zbl 0018.29204)]. The result is an algorithm that is approximately twice as fast as the original on inputs of 100 32-bit words in length, a significant improvement. The techniques developed include using double digits, using a new, exact condition for the partial cosequence computation, and an approximative GCD computation. Jebelean's exact condition was subsequently used by the reviewer [Proc. ISSAC '95, 254--258 (1995)].