An analysis of Lehmer's Euclidean GCD algorithm

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An analysis of Lehmer's Euclidean GCD algorithm

Full text

Pdf (510 KB)

Source

International Conference on Symbolic and Algebraic Computation archive
Proceedings of the 1995 international symposium on Symbolic and algebraic computation table of contents

Montreal, Quebec, Canada

Pages: 254 - 258

Year of Publication: 1995

ISBN:0-89791-699-9

Author

Jonathan Sorenson

Department of Mathematics and Computer Science, Butler University, 4600 Sunset Ave., Indianapolis, Indiana

Sponsors

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation
SIGNUM: ACM Special Interest Group on Numerical Mathematics

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 52, Citation Count: 5

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/220346.220378 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	R. P. Brent. Analysis of the binary Euclidean algorithm. In J. F. Traub, editor, Algorithms and Complexity, pages 321-355, Academic Press, 1976.
	2	J. L. Brown and R. L. Duncan. The least remainder algorithm. Fibonacci Quarterly, 9(4):347-350, 1971.
	3	G. E. Collins. The computing time of the Euclidean algorithm. SIAM Journal on Computing, 3(1):1-10, 1974.
	4	J. Dixon. The number of steps in the Euclidean algorithm. Journal of Number Theory, 2:414-422, 1970.
	5	A. W. Goodman and W. M. Zaring. Euclid's algorithm and the least-remainder algorithm. American Mathematical Monthly, 59:156-159, 1952.
	6	G. H. Hardy and E. M. Wright. An Introduction to the Theory of Numbers. Oxford University Press, 5th edition, 1979.
	7	T. Jebelean. Comparing several GCD algorithms. In 11th IEEE Symposium on Computer Arithmetic, Windsor, Ontario, 1993.
	8	T. Jebelean, A generalization of the binary GCD algorithm, Proceedings of the 1993 international symposium on Symbolic and algebraic computation, p.111-116, July 06-08, 1993, Kiev, Ukraine [doi>10.1145/164081.164102]
	9	Tudor Jebelean, Improving the Multiprecision Euclidian Algorithm, Proceedings of the International Symposium on Design and Implementation of Symbolic Computation Systems, p.45-58, September 15-17, 1993
	10	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	11	D. H. Lehmer. Euclid's algorithm for large numbers. American Mathematical Monthly, 45:227-233, 1938.
	12	Graham H. Norton, Extending the Binary GCD Algorithm, Proceedings of the 3rd International Conference on Algebraic Algorithms and Error-Correcting Codes, p.363-372, July 15-19, 1985
	13	G. H. Norton, On the asymptotic analysis of the Euclidean algorithm, Journal of Symbolic Computation, v.10 n.1, p.53-58, July 1990 [doi>10.1016/S0747-7171(08)80036-3]
	14	G. Norton, A shift-remainder GCD algorithm, Proceedings of the 5th international conference, AAECC-5 on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.350-356, June 1987, Menorca, Spain
	15	G. B. Purdy. A carry-free algorithm for finding the greatest common divisor of two integers. Computers eJ Mathematics with Applications, 9(2):311-316, 1983.
	16	A. Sch5nhage. Schnelle Berechnung yon Kettenbruchentwicklungen. Acta Informatica, 1:139-144, 1971.
	17	Jeffrey Shallit , Jonathan Sorenson, Analysis of a left-shift binary GCD algorithm, Journal of Symbolic Computation, v.17 n.6, p.473-486, June 1994 [doi>10.1006/jsco.1994.1030]
	18	Jonathan Sorenson, Two fast GCD algorithms, Journal of Algorithms, v.16 n.1, p.110-144, Jan. 1994 [doi>10.1006/jagm.1994.1006]
	19	J. Stein. Computational problems associated with Racah algebra. Journal of Computational Physics, 1:397-405, 1967.
	20	K. Weber. The Accelerated Integer GCD Algorithm. Technical Report ICM-9307-55, Institute for Computational Mathematics, Kent State University, July 1993.

CITED BY 5

	Sidi Mohammed Sedjelmaci, On a parallel Lehmer-Euclid GCD algorithm, Proceedings of the 2001 international symposium on Symbolic and algebraic computation, p.303-308, July 2001, London, Ontario, Canada
	Sidi Mohammed Sedjelmaci, A modular reduction for GCD computation, Journal of Computational and Applied Mathematics, v.162 n.1, p.17-31, 1 January 2004
	Sidi Mohamed Sedjelmaci, Jebelean--Weber's algorithm without spurious factors, Information Processing Letters, v.102 n.6, p.247-252, June, 2007
	Benoît Daireaux , Brigitte Vallée, Dynamical Analysis of the Parametrized Lehmer–Euclid Algorithm, Combinatorics, Probability and Computing, v.13 n.4-5, p.499-536, July 2004
	Sidi Mohamed Sedjelmaci, A parallel extended GCD algorithm, Journal of Discrete Algorithms, v.6 n.3, p.526-538, September, 2008