A double-digit Lehmer-Euclid algorithm for finding the GCD of long integers
type: Item
instance of: scholarly article
title: A double-digit Lehmer-Euclid algorithm for finding the GCD of long integers
zbMATH Open document ID: 0832.11046
author: Tudor Jebelean
published in: Journal of Symbolic Computation
publication date: 1996-03-07T00:00:00Z
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)].
reviewed by: Jonathan P. Sorenson
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 11A05
Mathematics Subject Classification ID: 68W30
zbMATH DE Number: 786280
zbMATH Keywords: Euclidean algorithm
zbMATH Keywords: number-theoretic algorithms
zbMATH Keywords: greatest common divisors
zbMATH Keywords: double digits
zbMATH Keywords: partial cosequence computation
zbMATH Keywords: approximative GCD computation
MaRDI profile type: Publication
full work available at URL: jsco.1995.1009
OpenAlex ID: W2063001983
DOI: 10.1006/JSCO.1995.1009
description: scientific article; zbMATH DE number 786280