A feasibility analysis of fixed-slash rational arithmetic

Author

Kornerup, Peter ; Matula, David W l

Author_Institution

Comput. Sci. Dept., Aarhus Univ., Aarhus, Denmark

fYear

1978

fDate

25-27 Oct. 1978

Firstpage

39

Lastpage

47

Abstract

An investigation of the feasibility of a finite precision approximate rational arithmetic based on fixed-slash representation of rational numbers is presented. Worst-case and average-case complexity analyses of the involved rounding algorithm (an extended shift-subtract gcd algorithm) are presented. The results are applied to a proposed hardware realization of a fixed-slash arithmetic unit.

Keywords

adders; computational complexity; fixed point arithmetic; logic design; number theory; average-case complexity analysis; feasibility analysis; finite precision approximate rational arithmetics; fixed-slash rational arithmetic unit; fixed-slash rational number representation; rounding algorithm; worst-case complexity analysis; Algorithm design and analysis; Approximation algorithms; Approximation methods; Complexity theory; Computers; Convergence; Hardware; Arithmetic unit design; Average-case complexity analysis; Continued fractions; Convergents; Finite precision; Fixed-slash arithmetic; GCD Algorithm; Rational arithmetic; Rounding; Worst-case complexity analysis;

fLanguage

English

Publisher

ieee

Conference_Titel

Computer Arithmetic (ARITH), 1978 IEEE 4th Symposium on

Conference_Location

Santa Monica, CA

Type

conf

DOI

10.1109/ARITH.1978.6155784

Filename

6155784