On the Time Required to Perform Addition

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the Time Required to Perform Addition

Full text

Pdf (637 KB)

Source

Journal of the ACM (JACM) archive
Volume 12 , Issue 2 (April 1965) table of contents

Pages: 277 - 285

Year of Publication: 1965

ISSN:0004-5411

Author

S. Winograd

Thomas J. Watson Research Center, IBM Corporation, Yorktown Heights, New York

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 27, Citation Count: 26

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/321264.321279 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	0FMAN, If. On the algorithmle complexity of disevete functions. Dokladi 145, I (1962). 48-051.
	2	MACSOtmLY, O. I,. High speed arithmetic in binary computers. Proc. IRE, 1961, 67-91.
	3	GAINEa, It. L. The residue number system. IRE Trans. EC-8, (June 1959), 140-147.
	4	AFIzIENIS, A. Signed sigit, number representation for fast parallel arithmetic. IRE Trans. EC-IO (Sept. 1961), 389-400.
	5	GILCHRIST, B., POMEIENE, J. t, AND WONG, S.Y. Fast carry logic of digital computers. IRE Trans. EC-4, 4 (l)ec. 1955), 133-136.
	6	SKIANSKY, J. An evaluation of several two-summand bimtry adders. IRE Trans. EC-9 (June 1960), 213 226.

CITED BY 28

	Robert K. Montoye, Area-time efficient addition in charge based technology, Proceedings of the 18th conference on Design automation, p.862-872, June 29-July 01, 1981, Nashville, Tennessee, United States
	R. P. Brent , H. T. Kung, The Area-Time Complexity of Binary Multiplication, Journal of the ACM (JACM), v.28 n.3, p.521-534, July 1981
	R. P. Brent , H. T. Kung, The chip complexity of binary arithmetic, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.190-200, April 28-30, 1980, Los Angeles, California, United States
	Jacob T. Schwartz, Ultracomputers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.4, p.484-521, Oct. 1980
	P. Montuschi , L. Ciminiera, Reducing Iteration Time When Result Digit is Zero for Radix 2 SRT Division and Square Root with Redundant Remainders, IEEE Transactions on Computers, v.42 n.2, p.239-246, February 1993
	S. Winograd, On the Time Required to Perform Multiplication, Journal of the ACM (JACM), v.14 n.4, p.793-802, Oct. 1967
	Michael O. Rabin, Complexity of computations, Communications of the ACM, v.20 n.9, p.625-633, Sept. 1977
	Rajit Manohar , José A. Tierno, Asynchronous Parallel Prefix Computation, IEEE Transactions on Computers, v.47 n.11, p.1244-1252, November 1998
	J. E. Savage, Computational Work and Time on Finite Machines, Journal of the ACM (JACM), v.19 n.4, p.660-674, Oct. 1972
	David J. Kuck, A Survey of Parallel Machine Organization and Programming, ACM Computing Surveys (CSUR), v.9 n.1, p.29-59, March 1977
	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
	Algirdas Avižienis, On the problem of computational time and complexity of arithmetic functions, Proceedings of the first annual ACM symposium on Theory of computing, p.255-258, May 05-07, 1969, Marina del Rey, California, United States
	P. Montuschi , L. Ciminiera, Over-Redundant Digit Sets and the Design of Digit-By-Digit Division Units, IEEE Transactions on Computers, v.43 n.3, p.269-277, March 1994
	Nicholas Pippenger, The complexity of computations by networks, IBM Journal of Research and Development, v.31 n.2, p.235-243, March 1987
	Barry S. Fagin, Fast Addition of Large Integers, IEEE Transactions on Computers, v.41 n.9, p.1069-1077, September 1992
	T. P. Kelliher , R. M. Owens , M. J. Irwin , T.-T. Hwang, ELM-A Fast Addition Algorithm Discovered by a Program, IEEE Transactions on Computers, v.41 n.9, p.1181-1184, September 1992
	Tomás Lang , Paolo Montuschi, Higher Radix Square Root with Prescaling, IEEE Transactions on Computers, v.41 n.8, p.996-1009, August 1992
	Philip M. Spira, The Time Required for Group Multiplication, Journal of the ACM (JACM), v.16 n.2, p.235-243, April 1969
	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
	Dieter Rautenbach , Christian Szegedy , Jürgen Werber, Delay optimization of linear depth boolean circuits with prescribed input arrival times, Journal of Discrete Algorithms, v.4 n.4, p.526-537, December, 2006
	Dieter Rautenbach , Christian Szegedy , Jürgen Werber, The delay of circuits whose inputs have specified arrival times, Discrete Applied Mathematics, v.155 n.10, p.1233-1243, May, 2007
	Michael O. Rabin, Complexity of computations, ACM Turing award lectures, ACM, New York, NY, 2007
	Patrick C. Fischer, Theory of computing in computer science education, Proceedings of the November 16-18, 1971, fall joint computer conference, November 16-18, 1971, Las Vegas, Nevada
	D. N. Senzig, Observations on high-performance machines, Proceedings of the November 14-16, 1967, fall joint computer conference, November 14-16, 1967, Anaheim, California
	M. Lehman , D. Senzig , J. Lee, Serial arithmetic techniques, Proceedings of the November 30--December 1, 1965, fall joint computer conference, part I, November 30-December 01, 1965, Las Vegas, Nevada
	E. M. Reingold, Establishing lower bounds on algorithms: a survey, Proceedings of the November 16-18, 1971, fall joint computer conference, November 16-18, 1971, Las Vegas, Nevada
	R. K. Montoye , E. Hokenek , S. L. Runyon, Design of the IBM RISC System/6000 floating-point execution unit, IBM Journal of Research and Development, v.34 n.1, p.59-70, Jan. 1990
	E. Hokenek , R. K. Montoye, Leading-zero anticipator (LZA) in the IBM RISC System/6000 floating-point execution unit, IBM Journal of Research and Development, v.34 n.1, p.71-77, Jan. 1990