Title :
A feasibility analysis of fixed-slash rational arithmetic
Author :
Kornerup, Peter ; Matula, David W l
Author_Institution :
Comput. Sci. Dept., Aarhus Univ., Aarhus, Denmark
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;
Conference_Titel :
Computer Arithmetic (ARITH), 1978 IEEE 4th Symposium on
Conference_Location :
Santa Monica, CA
DOI :
10.1109/ARITH.1978.6155784
