survey

Finite Precision Rational Arithmetic: An Arithmetic Unit

Authors:

P. Kornerup,

D. W. MatulaAuthors Info & Claims

IEEE Transactions on Computers, Volume 32, Issue 4

Pages 378 - 388

https://doi.org/10.1109/TC.1983.1676239

Published: 01 April 1983 Publication History

Publisher Site

Abstract

The foundations of an arithmetic unit performing the add, subtract, multiply, and divide operations on rational operands are developed. The unit uses the classical Euclidean algorithm as one unified algorithm for all the arithmetic operations, including rounding. Binary implementations are discussed, based on techniques known from SRT division, and utilizing ripple-free borrow-save and carry-save addition. Average time behavior is investigated.

References

[1]

A. Avizienis, "Signed-digit number representations for fast parallel arithmetic," IRE Trans., Electron. Comput., vol. 10, pp. 389-400, 1961.

Crossref

Google Scholar

[2]

C. V. Freiman, "Statistical analysis of certain binary division algorithms," Proc. IRE, vol. 49, pp. 91-103, 1961.

Crossref

Google Scholar

[3]

G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 4th ed. Oxford, England: Clarendon Press, 1959.

Google Scholar

[4]

A. Y. Khintchin, Continued Fractions, translated from Russian by P. Wynn. Grooningen: P. Noordhoff Ltd., 1969.

Google Scholar

[5]

D. E. Knuth, The Art of Computer Programming, Volume 2: Seminumerical Algorithms. Reading, MA. Addison-Wesley, 1981.

Google Scholar

[6]

P. Kornerup and D. W. Matula, "A feasibility analysis of fixed-slash rational arithmetic," in Proc. 4th. IEEE Symp. Comput. Arith., 1978, pp.39-47.

Google Scholar

[7]

P. Kornerup and D. W. Matula, "An integrated rational arithmetic unit," in Proc. 5th. IEEE Symp. Comput. Arith. 1981, pp. 233-240.

Google Scholar

[8]

U. Kulish, "An axiomatic approach to rounded computations," Numerische Mathematik, vol. 18, pp. 1-7, 1971.

Digital Library

Google Scholar

[9]

D. W. Matula and P. Kornerup, "Foundations of finite precision rational arithmetic," in Computing, Suppl. 2. New York: Springer-Verlag, 1980, pp. 85-111.

Google Scholar

[10]

D. W. Matula and P. Kornerup, "On'minimum weight binary representations of integers and continued fractions," Dep. Comput. Sci., Aarhus Univ., DAIMI PB-130, 1981.

Google Scholar

[11]

D. W. Matula and P. Kornerup, "An order preserving finite binary encoding of the rationals," Proc. 6th IEEE Symp. Comput. Arith., 1983, to be published.

Google Scholar

[12]

G. Metze and J. E. Robertson, "Elimination of carry-propagation in digital computers," in Proc. IFIP Conf., 1959, pp. 39-396.

Google Scholar

[13]

J. W. Porter, "On a theorem of Heilbronn," Mathematika, vol. 22, pp. 20-28, 1975.

Crossref

Google Scholar

[14]

G. W. Reitwiesner, "Binary arithmetic," in Advances in Computers vol. I, F. L. Alt, Ed. New York: Academic, 1960.

Google Scholar

Cited By

View all

Mora HMora-Pascual JGarcía-Chamizo JSignes-Pont M(2017)Mathematical model and implementation of rational processingJournal of Computational and Applied Mathematics10.1016/j.cam.2016.05.001309:C(575-586)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1016/j.cam.2016.05.001
Cotelo Lema JGüting R(2002)Dual GridGeoinformatica10.1023/A:10137681149096:1(57-76)Online publication date: 1-Mar-2002
https://dl.acm.org/doi/10.1023/A%3A1013768114909
Schulte MSwartzlander E(2000)A Family of Variable-Precision Interval Arithmetic ProcessorsIEEE Transactions on Computers10.1109/12.85953549:5(387-397)Online publication date: 1-May-2000
https://dl.acm.org/doi/10.1109/12.859535
Show More Cited By

Recommendations

Design of a systolic coprocessor for rational addition
ASAP '95: Proceedings of the IEEE International Conference on Application Specific Array Processors

We design a systolic coprocessor for the addition of signed normalized rational numbers. This is the most complicated rational operation: it involves GCD, exact division, multiplication and addition/subtraction. In particular the implementation of GCD ...
On Circuits and Numbers

We establish new, yet intimate relationships between the 2-adic integers /sub 2/Z from arithmetics and digital circuits, both finite and infinite, from electronics. 1) Rational numbers with an odd denominator correspond to output only synchronous ...
A variable-precision, interval arithmetic processor

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Computers

IEEE Transactions on Computers Volume 32, Issue 4

April 1983

103 pages

ISSN:0018-9340

Issue’s Table of Contents

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 April 1983

Author Tags

Qualifiers

Survey

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Mora HMora-Pascual JGarcía-Chamizo JSignes-Pont M(2017)Mathematical model and implementation of rational processingJournal of Computational and Applied Mathematics10.1016/j.cam.2016.05.001309:C(575-586)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1016/j.cam.2016.05.001
Cotelo Lema JGüting R(2002)Dual GridGeoinformatica10.1023/A:10137681149096:1(57-76)Online publication date: 1-Mar-2002
https://dl.acm.org/doi/10.1023/A%3A1013768114909
Schulte MSwartzlander E(2000)A Family of Variable-Precision Interval Arithmetic ProcessorsIEEE Transactions on Computers10.1109/12.85953549:5(387-397)Online publication date: 1-May-2000
https://dl.acm.org/doi/10.1109/12.859535
Michelucci DMoreau J(1997)Lazy ArithmeticIEEE Transactions on Computers10.1109/12.62047846:9(961-975)Online publication date: 1-Sep-1997
https://dl.acm.org/doi/10.1109/12.620478
Rao THelber LKwasny SBuck J(1993)An implementation of multiple modulus arithmetic and its comparison to floating point arithmeticProceedings of the 1993 ACM conference on Computer science10.1145/170791.170881(398-403)Online publication date: 1-Mar-1993
https://dl.acm.org/doi/10.1145/170791.170881

Abstract

References

Cited By

Recommendations

Design of a systolic coprocessor for rational addition

On Circuits and Numbers

A variable-precision, interval arithmetic processor

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations