On Producing Exactly Rounded Results in Digit-Serial on-Line Arithmetic

The input and output of an on-line computation involving redundant numbers must generally be compatible with standard nonredundant formats. When rounding of a result is required in the last computation step, the process can be combined with on-the-fly conversion of the redundant output into nonredundant form and thus introduces no extra delay. However, if multiple on-line operations are to be performed before obtaining a final result, the preceding method would be inapplicable to the intermediate results. We present a solution scheme where rounding (subtraction of ulp, no action, addition of ulp) is represented by an additional digit attached to the number, thus obviating the need for modifying any of the previously produced digits. This added digit forms a second least-significant digit (LSD), leading to the designation "double-LSD numbers" for the resulting representation. We show that on-line arithmetic with double-LSD numbers is only slightly more complex than with ordinary signed-digit numbers