A new on-the-fly summation algorithm

Abstract

Digit recurrence operations mainly use redundant representation, mostly in signed-digit format. These operations generate results one digit per iteration from left to right. Since the final result has to be converted into 2s complement format, to eliminate the end of operation conversion delay, on-the-fly algorithms are employed. These algorithms, with no use of carry propagating adders, convert the result into the conventional format as the signed-digits are generated. Some applications like rounding non-normalized results, positive or negative offsetting, coding and cryptography require not only the original result in 2s complement format, but also to generate the original result summed with (n)ulp 1, where n is an integer, in the ordinary representation. This paper proposes a new algorithm applying to digit recurrence operations to generate that value on-the-fly.