Abstract:
Arithmetic operations such as addition and multiplication are usually performed in "batch" mode, with the inputs being available in their entirety before computation begins, and with no attempt being made to produce any output until computation ends. This mode of operation contrasts with "on-line" computation, in which inputs arrive incrementally as computation proceeds, and outputs are produced incrementally as well. We will examine the problem of performing arithmetic operations on-line. To do this we must first consider various input-output conventions and discuss alternative computational models. The seemingly mundane problem of "rounding" brings key issues into focus, giving rise to new open questions as well as new results.