A generalization of the binary GCD algorithm

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A generalization of the binary GCD algorithm

Full text

Pdf (416 KB)

Source

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

Kiev, Ukraine

Pages: 111 - 116

Year of Publication: 1993

ISBN:0-89791-604-2

Author

T. Jebelean

Sponsor

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 55, Citation Count: 9

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/164081.164102 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	A. j. Atrubin, "A one-dimensional iterative multiplier", IEEE Trans. Computers, Vol C-14, pp. 394- 399, 1965.
	2	R. P. Brent, H. T. Kung, "Systolic VLSI arrays for linear-time GCD computation", in F. Anceau, E. J. Aas (eds.), VLSI'83, Elsevier (North-Holland), pp. 145 - 154, 1983.
	3	R. P. Brent, " Analysis of the binary Euclidean algorithm", in J. F. Traub (ed.), New directions and recent results in algorithms and complexity, Academic Press, pp. 321- 355, 1976.
	4	B. Buchberger, "Gr6bner Bases: An Algorithmic Method in Polynomial Ideal Theory", in N. K. Bose (ed.), Multidimensional Systems Theory, D. Reidel Publishing Co., 1985.
	5	B. Buchberger, T. Jebelean, "Parallel Rational Arithmetic for Computer Algebra systems: Motivating Experiments", RISC-Linz Report 92-29, May 1992.
	6	G. E. Collins, "Lecture notes on arithmetic algorithms", Univ. of Wiscousin, 1980.
	7	T. Granlund, "GNU MP: The GNU multiple precision arithmetic library", Free Software Foundation, 1991.
	8	Tudor Jebelean, An algorithm for exact division, Journal of Symbolic Computation, v.15 n.2, p.169-180, Feb. 1993 [doi>10.1006/jsco.1993.1012]
	9	T. Jebelean, "Systolic algorithms for exact division", PARS Workshop (Dresden, April 1993).
	10	T. :lebelean, "Comparing several GCD algorithms", ARITH-11 (Windsor, June 1993).
	11	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	12	D. H. Lehmer, "Euclid's algorithm for large numbers", Am. Math. Mon., Vol. 45, pp. 227-233, 1938.
	13	R. T. Moenck, Fast computation of GCDs, Proceedings of the fifth annual ACM symposium on Theory of computing, p.142-151, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804045]
	14	A. SchSnhage, "Schnelle Berechung yon Kettenbruchentwicklugen", Acla Informatica, Vol. 1, pp. 139- 144, 1971.
	15	:I. Stein, "Computational problems associated with Racah algebra", Jr. Comp. Phys., Vol. 1, pp. 397- 4O5, 1967.
	16	Paul S. Wang, A p-adic algorithm for univariate partial fractions, Proceedings of the fourth ACM symposium on Symbolic and algebraic computation, p.212-217, August 05-07, 1981, Snowbird, Utah, United States [doi>10.1145/800206.806398]

CITED BY 9

	Masayuki Noro , John McKay, Computation of replicable functions on Risa/Asir, Proceedings of the second international symposium on Parallel symbolic computation, p.130-138, July 20-22, 1997, Maui, Hawaii, United States
	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
	Jonathan Sorenson, An analysis of Lehmer's Euclidean GCD algorithm, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.254-258, July 10-12, 1995, Montreal, Quebec, Canada
	Kenneth Weber, The accelerated integer GCD algorithm, ACM Transactions on Mathematical Software (TOMS), v.21 n.1, p.111-122, March 1995
	Tudor Jebelean, Practical integer division with Karatsuba complexity, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.339-341, July 21-23, 1997, Kihei, Maui, Hawaii, United States
	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
	Kenneth Weber , Vilmar Trevisan , Luiz Felipe Martins, A modular integer GCD algorithm, Journal of Algorithms, v.54 n.2, p.152-167, February 2005
	Sidi Mohamed Sedjelmaci, Jebelean--Weber's algorithm without spurious factors, Information Processing Letters, v.102 n.6, p.247-252, June, 2007
	Sidi Mohamed Sedjelmaci, A parallel extended GCD algorithm, Journal of Discrete Algorithms, v.6 n.3, p.526-538, September, 2008