MSB-First Digit Serial Arithmetic

Asger Munk Nielsen (Dept. of Mathematics and Computer Science, Odense University, Denmark)

Peter Kornerup (Dept. of Mathematics and Computer Science, Odense University, Denmark)

Abstract: We develop a formal account of digit serial number representations by describing them as strings from a language. A prefix of a string represents an int erval approximating a number by enclosure. Standard on-line representations are shown to be a special case of the general digit serial representations. Matrices are introd uced as representations of intervals and a finite-state transducer is used for mapping str ings into intervals. Homographic and bi-homographic functions are used for representing basi c arithmetic operations on digit serial numbers, and finally a digit serial represen tation of floating point numbers is introduced.

Keywords: Computer Arithmetic, Continued Fractions, Intervals, Number Representations, On-line Computation, Redundant Digit sets

Categories: B.2