Towards a fourth attempt

It is natural to wonder whether there exist algorithms that compute most significant digits first. Let's begin by considering multiplication by three. Assume that we want to multiply a decimal numeral by three, and suppose that, at some stage, the scanned part of the input is ``4#4''. The first output digit can be either 0 or 1. If we eventually scan an input digit <3then it has to be 0, and if we eventually scan a digit >3 then it has to be 1. Thus, while the next scanned digit is 3, we can't determine the first output digit. Therefore, to get the first digit of

5#5

we are forced to compute all the 43 digits of the input.

A solution to this problem, first proposed by Cauchy [16] in 1840, is the use of negative digits. For example

6#6

where we have written the negation symbol on the top of negative digits for clarity. Intuitively, in order to compute a function,

1.

we estimate an output digit (after reading some input digits),

2.

if it turns out to be not quite correct (after reading more input digits), we can use a negative digit to adjust the estimate.

For example, let's consider multiplication by three again. Suppose that ``0.3'' is an initial prefix of the input. Then we can safely produce ``1.'' as an initial prefix of the output. In fact, if we later read a digit 0, discovering that the numeral has ``0.30'' as an initial prefix, we can now output a negative digit 7#7, having produced ``8#8'' up to this point, which is the same as ``0.9''. A mathematical discussion of these issues is the subject of Chapter 6 below.