Algorithms for Gaussian integer arithmetic

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Algorithms for Gaussian integer arithmetic

Full text

Pdf (752 KB)

Source

Symposium on Symbolic and Algebraic Manipulation archive
Proceedings of the third ACM symposium on Symbolic and algebraic computation table of contents

Yorktown Heights, New York, United States

Pages: 36 - 45

Year of Publication: 1976

Authors

B. F. Caviness
G. E. Collins

Sponsors

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation
SYMSAC : SYMSAC

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 40, Citation Count: 2

Additional Information:

abstract 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/800205.806321 What is a DOI?

ABSTRACT

In this paper new algorithms are given for Gaussian integer division and the calculation of the greatest common divisor of two Gaussian integers. Empirical tests show that the new gcd algorithm is up to 5.39 times as fast as a Euclidean algorithm using the new division algorithm.

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	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	B. F. Caviness, A Lehmer-Type Greatest Common Divisor Algorithm for Gaussian Integers, SIAM Review Vol. 15, No. 2, Part 1 (April 1973), 414.
	3	George E. Collins, The Calculation of Multivariate Polynomial Resultants, Journal of the ACM (JACM), v.18 n.4, p.515-532, Oct. 1971 [doi>10.1145/321662.321666]
	4	D. H. Lehmer, Euclid's Algorithm for Large Numbers, Amer. Math. Monthly Vol. 45, No. 4 (April 1938), 227-233.
	5	A Schönhage and V. Strassen, Schnelle Multiplikation Grosser Zahlen, Computing Vol. 7 (1971), 281-292.

CITED BY 2

	Erich Kaltofen , Michael B. Monagan, On the genericity of the modular polynomial GCD algorithm, Proceedings of the 1999 international symposium on Symbolic and algebraic computation, p.59-66, July 28-31, 1999, Vancouver, British Columbia, Canada
	George E. Collins, A fast Euclidean algorithm for Gaussian integers, Journal of Symbolic Computation, v.33 n.4, p.385-392, April 2002