The Time Required for Group Multiplication

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The Time Required for Group Multiplication

Full text

Pdf (490 KB)

Source

Journal of the ACM (JACM) archive
Volume 16 , Issue 2 (April 1969) table of contents

Pages: 235 - 243

Year of Publication: 1969

ISSN:0004-5411

Author

Philip M. Spira

Stanford University, Department of Electrical Engineering, Stanford, California

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 25, Citation Count: 3

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	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/321510.321515 What is a DOI?

ABSTRACT

Winograd has considered the time necessary to perform numerical addition and multiplication and to perform group multiplication by means of logical circuits consisting of elements each having a limited number of input lines and unit delay in computing their outputs. In this paper the same model as he employed is adopted, but a new lower bound is derived for group multiplication—the same as Winograd's for an Abelian group but in general stronger. Also a circuit is given to compute the multiplication which, in contrast to Winograd's, can be used for non-Abelian groups. When the group of interest is Abelian the circuit is at least as fast as his. By paralleling his method of application of his Abelian group circuit, it is possible also to lower the time necessary for numerical addition and multiplication.

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	S. Winograd, On the Time Required to Perform Addition, Journal of the ACM (JACM), v.12 n.2, p.277-285, April 1965 [doi>10.1145/321264.321279]
	2	S. Winograd, On the Time Required to Perform Multiplication, Journal of the ACM (JACM), v.14 n.4, p.793-802, Oct. 1967 [doi>10.1145/321420.321438]
	3	OFMAN YU. Oil the algorithmic complexity of discrete fuilctions. Dokl. Akad. Nauk SSSR 155, 1 (1962), 48-51.
	4	HALL, M., JR. The Theory of Groups. Macmillan Co., New York, 1959.

CITED BY 3

	Philip M. Spira, On the computation time of certain classes of boolean functions, Proceedings of the first annual ACM symposium on Theory of computing, p.271-272, May 05-07, 1969, Marina del Rey, California, United States
	James R. Armstrong, The relationship between computational circuit complexity and radix, Proceedings of the sixth international symposium on Multiple-valued logic, p.175-178, May 25-28, 1976, Logan, Utah, United States
	Barry S. Fagin, Fast Addition of Large Integers, IEEE Transactions on Computers, v.41 n.9, p.1069-1077, September 1992