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

DOI10.1006/JSCO.1995.1009MaRDI QIDQ1895406zbMATH OpenOpenAlexFDO

Authors Tudor Jebelean

Publication date 7 March 1996

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jsco.1995.1009

zbMATH Keywords

approximative GCD computationdouble digitsEuclidean algorithmgreatest common divisorsnumber-theoretic algorithmspartial cosequence computation

Mathematics Subject Classification ID

Multiplicative structure; Euclidean algorithm; greatest common divisors (11A05) Number-theoretic algorithms; complexity (11Y16) Symbolic computation and algebraic computation (68W30)

Review text

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)].

Recommendations

• scientific article; zbMATH DE number 1254258
• Two Fast GCD Algorithms
• A Greatest Common Divisor Algorithm
• A modular integer GCD algorithm
• Fast computation of GCDs

Cited in

(4)

• Regularity of the Euclid algorithm; application to the analysis of fast GCD algorithms
• scientific article; zbMATH DE number 1254258 (Why is no real title available?)
• A Greatest Common Divisor Algorithm
• On Schönhage's algorithm and subquadratic integer gcd computation

This page was built for publication: A double-digit Lehmer-Euclid algorithm for finding the GCD of long integers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1895406)