Optimal Parameters for On-Line Arithmetic
Colin D. Walter
Computation Department, U.M.I.S.T.,
PO Box 88, Sackville Street, Manchester M60 1QD, U.K.
e-mail: C.Walter@umist.ac.uk

Abstract. Some general techniques are given for constructing divergent
examples for on-line arithmetic operations whose parameters are chosen
beyond the optimal ones which converge. They are applied in particular
to the cases of fully on-line multiplication, division and square root.
Index Terms: Computer arithmetic, multiplication, division, squareroot, on-line algorithms, redundant number systems, recurrence relations.

1

Introduction

The choice of best parameters in hardware algorithms often depends on theuse of continuous mathematics to deduce limiting situations, whereas parameters which must fail can be deduced by the application of information theoretic
methods. With algorithms that gain speed by performing only partial or approximate calculations at each step there is usually a gap between such setsof parameters, where behaviour is unknown. The discrete nature of hardware
arithmetic suggests that it may be impossible for the limiting cases used in thecontinuous arguments to arise in practice. This would mean that better parameters might be possible. Explicit counter-examples are then required to justify
rejecting some parameters choices in this gap, and more detailed, specific proofs
for accepting other choices. We develop some techniques for this, considering
the cases of fully on-line algorithms for multiplication, division and square root
where the iterative step is as simple as possible to gain speed.
Fully on-line algorithms consume all their inputs and generate all outputs
digit serially at the same rate, most significant bit first. Multiplication, divisionand square root have been extensively studied in the literature, using either asimple addition for the iterative step (see [4], [7], [8], [2], [5]), or a fuller, moreaccurate computation (see [1], [6]), and sometimes with not all inputs being online (see [3], [9]). However, a redundant number system must always be used toenable digit parallel addition, and to enable some freedom in the choice of theoutput digits. There is a natural, fixed time delay δ between input and output
of corresponding digits: the output digit of index j depends solely on the input
digits of index j+δ or less. Here the output digit depends on an approximation,
down to digits of index ε, of a partial remainder, which is basically the difference2Internat. J. of Computer Mathematics 56 (1995), pp. 11-18

between the function on the inputs so far and the output so far. The best choiceof the parameters δ and ε is to minimise them.

2

The Algorithms

Uppercase characters are used to denote real numbers and lowercase charactersto denote digits. We consider
P∞ real inputs and outputs M with |M | < 1 and radix
2 representations M ≡ t=1 mt 2−t , where the digit mt lies in the redundantsigned digit set {−1, 0, +1}. At time j ≥ 0, the first j digits provide the inputs
Pj
M [j] ≡ t=1 mt 2−t from which the output digit of index j−δ is formed. The
difference between the function on such inputs and the previous output yields ascaled residual error or partial remainder, here defined by:
W [j] = 2j {X[j]×Y [j] − P [j−1−δ]}W [j] = 2j {X[j] − Q[j−1−δ]×Y [j]}W [j] = 2j {X[j] − S[j−1−δ]2 }√for product P = X×Y , quotient Q = X/Y and square root S = X. The output
digit of index j−δ is chosen to approximately minimise this if it were includedin the definition. To guarantee outputs in the interval (−1, +1) we require also
|X| < 1/2 ≤ |Y | for division and X ≥ 1/4 for square root. The partial remainder
definitions give the recurrence relations
W [j+1] = 2W [j] + yj+1 X[j] + xj+1 Y [j] + 2−1−j xj+1 yj+1 − 21+δ pj−δW [j+1] = 2W [j] + xj+1 − yj+1 Q[j−1−δ] − 21+δ qj−δ Y [j+1]W [j+1] = 2W [j] + xj+1 − 22+δ sj−δ ×S[j−1−δ] − 21+2δ−j sj−δ 2with initial value W [0] = 0. So the output digits are chosen close to 2−δ W [j],2−δ W [j]/Y [j] and 2−1−δ /S[j−1−δ] respectively. Speed is gained by considering
just W [j]0 , given by truncating all digits in W [j] after that of index ε. This iscompared with a fixed integer i (depending on the algorithm) and the output
digit rj−δ is then defined byrj−δ = +1 if 2ε W [j]0 ≥ i
0 if |2ε W [j]0 | < i−1 if 2ε W [j]0 ≤ −i

3

Convergence

Convergence of the algorithms depends entirely on stopping W [j] from overflowing its register. It must be bounded. Define Z ≡ 0.111... to have all its digits
equal to 1. By taking representations M ≡ M [j]+2−j mZ for each input andM ≡ M [j−1−δ]+21+δ−j mZ for each output and obtaining an expression forColin D. Walter, On-Line Arithmetic3

W [j+k] in terms of W [j], it is possible to observe the worst case behaviour as
k → ∞. In the case of multiplication,
W [j+k] = W [j] + (2k − 1)(W [j]+yX[j]+xY [j]+21+δ p+2−j xyZ[k])Take x = sY and y = sX where sM is the sign of M . Then choosing p = −1 givesa lower bound on the maximum value of W [j+k]. So W [j+k] is only bounded
above as k → ∞ if W [j] is bounded above by
U [j] = 21+δ −|X[j]|−|Y [j]|−2−j .
Similarly, for the other two algorithms, there are upper bounds
U [j] = 21+δ |Y [j]| − 1 − |Q[j−1−δ]| − 21+δ−j sY sQ
U [j] = 22+δ |S[j−1−δ]| + 22+2δ−j − 1
for j > δ in each case. Lower bounds are essentially identical with opposite signs.
These bounds are very tight in practice, and so aid in the generation of divergent
examples since, when they are exceeded, an appropriate choice of repeated digit
for the inputs will result in the partial remainder becoming arbitrarily large.
Also, an easy consequence is that the hardware register for W is bounded by|W | < 21+δ for multiplication and division, and by |W | < 3.21+δ for square root.
Though tricky at some points, it is now possible to show by induction onj that these bounds do hold, subject to certain restrictions which are sufficient
to make the induction step work. The base case of j = 1+δ holds because theintegral part of the output is set to 0. As an example of the induction step, takemultiplication when pj−1−δ = 0. For convenience, assume also that ε < δ. Then
W [j−1] has at most j−1 digits after the point. So W [j−1]+21−j ≤ W [j−1]0 +2−ε
≤ 2−ε i, andW [j] = 2W [j−1] + yj X[j−1] + xj Y [j−1] + 2−j xj yj − 21+δ pj−1−δ≤ 2(2−ε i−21−j ) + 2≤ 21−ε i − 22−j + 4 − |X[j]| − |Y [j]|This is at most U [j] whenever 21−ε i+4 ≤ 21+δ +21−j , and so the step holds forall j > δ if21−ε i + 4 ≤ 21+δSimilarly, the case pj−1−δ = −1 holds if
21−ε (1−i) + 4 ≤ 0
For division and square root convergence is guaranteed when21−ε i + 4≤ 2δ
−ε2 (1−i) + 2 ≤ 0and21−ε i + 2≤ 21+δ
21−ε (1−i) + 2 ≤ 0

hold respectively. The best choices of parameters which satisfy these have (δ, ε)equal to (3, −1), (4, −1) and (2, 0), respectively, with i equal to 2 or 3 in each
case.

4

4

Internat. J. of Computer Mathematics 56 (1995), pp. 11-18

Stable Number Representations

Our main question now is, are these conditions necessary for convergence? It isclear by exhaustive testing of all possible inputs that if word length is limited
some better choices for ε and δ can be found. (Just consider a word length of
one digit after the point to see that δ could then be reduced to 1 with ε = 1.)
We will not try to establish at what word length the values of δ and ε need to
be incremented, although some upper limits can be deduced from the examples
below. However, it will be shown from examples which diverge, that the values
obtained in the previous section are indeed the best ones when word length isunbounded or unspecified.
Divergence depends on certain choices of output digit, and therefore on the
representation of the partial remainder, which in turn depends on the choice ofhardware adder used in the iterative cycle. Prediction of representations is easiest
when we have a stable representation, i.e. one that is invariant as it goes throughthe adder with the other inputs being identically 0. If we consider common hardware for the algorithms, then we need an adder for 3 redundant numbers, which
we now define. For convenience, assume all digit positions behave identically,
although any hardware is allowable for the un-truncated part of interest in W .
First, the addition of three corresponding digits gives a total t which generates asum digit (|t|mod2)×sign(t) and a carry digit (|t|div2)×sign(t). Secondly, corresponding sum and carry digits are added to yield a total t0 . This is split in thesame way again unless both it and the next digit total down are non-zero withthe same sign, in which case the new sum digit is −t0 and the new carry is t0 .
Lastly, these second sum and carry results are added to give a final digit sum inthe range [−1..+1]. This is the adder output.
Lemma 1.
i) Every number has a stable representation.
ii) A representation is stable if, and only if, it contains no pair of digits
11 or 1̄1̄.
iii) The largest stable fraction is 0.1010... = 2/3.
iv) The largest fraction none of whose stable representations has nonzero integral part is 0.01010... = 1/3.
v) If the binary representation of V has most significant digit corresponding to 2n then stable representations have most significant
digits corresponding to 2n , 2n+1 or 2n+2 .
vi) A finite representation of V whose binary representation has v digits becomes stable after at most v+1 passes through the adder, andcannot grow in length except from v to v+1 digits.
Lemma 2. For the truncation function 0 and a stable representation V ,i) If V 0 > 0 then 0 ≤ (V /2)0 ≤ V 0 ;ii) If V 0 = (V /2)0 > 0 then V 0 ≡ 11̄×2−ε .

Colin D. Walter, On-Line Arithmetic

5

5

Values for the Partial Remainder

Assume each algorithm converges. The examples we now construct to obtain acontradiction to this assumption employ inputs which are are close to the points
at which the induction argument above was most difficult to close, namely where
the input digits have the greatest effect, and the output digit the least effect,on the value of the partial remainder. To obtain known output, we exploit thefact that if some choice of output were to yield |W | < 1 then any other choiceof output would make W exceed its bounds. Hence the algorithm must makethat first choice. Moreover, by Lemma 1(vi), inputs can be chosen to force stable
representations of W .
Let = denote equality of value between two possibly different representationsand ≡ equality of representation. As above, take Z ≡ 0.111... and suppose V isthe representation of some number to be chosen later, with most significant digitof index not above −δ and least significant digit of index v ≥ 0.
For multiplication, takeX

≡ Z[t] + 2−u V + 2−r−u Z

andY≡ Z[t] + 2−r + 2−r−u Z

where u > t+1+2δ and r > u+v. For these inputs, if the expected value for
P [r+u−2−2δ] is chosen then |W [r+u−1−δ]| = |2−1−δ V | < 1. Since any otherchoice for P would exceed the convergence bounds, this must indeed be the value
for P [r+u−2−2δ]. So, if V is initially stable and not large enough to generate
earlier non-zero output digits, we obtain it as the value and representation ofW [r+u].
For division, takeX

≡ 2−1 Z[t] − 2−u−1 V + 2−r−u Z

andY≡ 2−1 + 2−r − 2−r−u Z

where u > t+v+2δ and r > u+v. A similar argument shows that Q[r+t−1] =1−2−t + 2−u V −21−r +21−r−t , which yields W [r+t+δ] = 2t+δ−u V + 2t+1+δ−r+ 21+δ−r . There are sufficient further iterations for the adder to turn V intoa stable form when it appears in W [r+u] = V +2u+1−r +2u+1−r−t , subject tobeing sufficiently small not to generate earlier non-zero output digits.
For the square root, takeX

≡ 2−2 + 2−t + 2−2t − 2−u V + 21−u−t Z

where t > 2(v+1+δ) and u > 2t+2+2δ. As before, S[u+v] = 2−1 +2−t −2−u V
must hold, giving W [u+t−1] = V +2t−u−1 V 2 where the representation of V has
become stable, and we assume it is sufficiently small not to generate earlier
output digits.
In general, it is thus possible to obtain any number as the value of the partial
remainder subject to certain conditions about one or all of its stable representations not generating earlier output digits.

66Internat. J. of Computer Mathematics 56 (1995), pp. 11-18

Examples of DivergenceTwo values for V are now chosen to make the value of W as close as possible
to the points at which the output digit changes from 0 to +1 and from −1 to 0.
These are where the induction step was hardest to establish. In particular, for i
as in the definition of the output digit, we takeV0 = 2−ε (i−1+α)V−1 = 2−ε (β−i)
00where α and β are fractions such that V0 = 2−ε (i−1) and V−1 = −2−ε i for the
representations of V which might turn up in W . This will guarantee the output
digits 0 and −1 respectively when desired, without 2−j V (j > 0) generating0≡ 11̄×2−ε when i = 1. With that
non-zero output integers unless we obtain V−1
exception, running through the induction step argument again, we find that thebound is not met if either of the following holds:
21−ε (i−1+α) + 4 > 2δ21−ε (β−i)
+4>0
or

or

21−ε (i−1+α) + 4 > 2δ−121−ε (β−i)+4>021−ε (i−1+α) + 2 > 2δ21−ε (β−i)+2>0respectively for the three algorithms.
The best choice of α and β here would be to take them both equal to 1.
However, some separation is needed between them and the “integer” part of
V in order to ensure that the truncation function generates the right output
digit. For multiplication, the initial representation of V is stable (avoiding theexceptional case) and, according to Lemma 1, α and β can be 1/3 or 2/3 (orrather the first v digits of their stable binary representations) depending onwhether the integer part is odd or even respectively. Immediately, one of theinequalities is satisfied when δ = 2, so that the multiplication algorithm must
diverge. For δ = 3, apart from the convergent cases we already know, the threecases (ε, i) = (−3, 1), (−2, 1), or (−2, 2) are not shown to be divergent by theabove, but then divergence happens for
X ≡ Y ≡ Z[t] + 2−t−1 Z= 1 − 2−t−1

with t > 2.
For division, we do not know which stable representation of V will appear in
W . To guarantee the right output digits, a zero must be placed between any stable representations of the integer and fractional parts to prevent any interchange
between them. So we may only choose α and β to be 1/6 or 1/3 depending onColin D. Walter, On-Line Arithmetic

7

whether the integer part is odd or even respectively. Then with several exceptions, one of the inequalities is satisfied whenever δ ≤ 4, so that the divisionalgorithm must diverge. Apart from the known convergent cases, the remaining undetermined exceptions are (ε, i) = (−2, 1) for δ = 3, and (ε, i) = (−4, 1),(−3, 1), (−2, 1), or (−2, 2) for δ = 4. For these, modify the standard construction
to takeX ≡ 2−1 Z[t] − 2−u−1 V + 21−r−u Z
with Y as before. The best β now works for the δ = 3 case, whereas in theother cases, taking V = 1+2−a for some a > 2 produces an excessive W after an
extra two or three iterations (or earlier in the case of the first exception). If the
exception noted in Lemma 2 arises, then Y should be modified toY≡ 2−1 + 2−r−1 − 2−r−u Z

With the square root, the same choice of α and β is made as similar circumstances arise to those of division. With a few exceptions, one of the inequalities isthen satisfied whenever δ ≤ 2, so that the division algorithm must diverge. Other
than the known convergent cases, the exceptions are (ε, i) = (−1, 1) for δ = 1,
and (ε, i) = (−2, 1), (−1, 1) or (−1, 2) for δ = 3. For both the cases (−1, 1) the
usual inequality will hold by choosing V ≡ 1̄+2−a , with a not too small, unless
the Lemma 2 exception arises, in which case V ≡ 1̄0+2−a will work. For the lastcase, (−1, 2), consider W [u+3] whenX

≡ 2−2 + 2−t + 2−2t − 2−u + 2−1−u Z

for t and u > 2t large enough, say t = 6 and u = 27. The most interestingcase is the second one, (−2, 1), where all 15 digit inputs except one are calculated properly. The unique exception is X ≡ 0.010101̄01̄1̄1̄1̄1̄1̄1̄1̄+2−15 Z forwhich the first incorrect digit has index 22. Divergence becomes guaranteed
since W [25] > U [25]. Thus, this set of parameters is acceptable for all inputs up
to at least 15 and perhaps up to as many as 21 digits.

7

Conclusion

We have investigated the optimality of the best parameters generated by analytic
arguments for some on-line algorithms, and given techniques and general constructions for examples of divergence for other parameter choices. This shows theanalytic results are indeed optimal. However, for the square root algorithm thisis only just the case. Indeed, for limited precision square root better parameters
can be chosen. Moreover, there seems no theoretical barrier to the existence of
on-line functions for which the analytic results provide only strictly suboptimal
parameters.
Two final remarks: shifting of difficult inputs can allow improved parameters,
and, although the proofs become more complex, all the results hold when the
inputs lie in the closure of the (half-open) intervals on which they are usually
defined.

8Internat. J. of Computer Mathematics 56 (1995), pp. 11-18

References[1] Jean Duprat, Yvan Herreros & Jean-Michel Muller, “Some results about on-line
computation of functions”, Proc. 9th Symposium on Computer Arithmetic, Santa
Monica CA, 6-8 Sept ’89, IEEE Comp. Soc. Press, 1989, pp. 112-118.
[2] Milos D. Ercegovac, “An On-Line Square Rooting Algorithm”, Proc. 4th IEEE
Symposium on Computer Arithmetic, Santa Monica, CA, 1978, pp. 183-189.
[3] Milos D. Ercegovac & Tomas Lang, “Implementation of Module combining Multiplication, Division and Square Root”, Proc. IEEE Intern. Symp. on Circuits andSystems, 1989, pp. 150-153.
[4] Milos D. Ercegovac & Tomas Lang, “On-Line Arithmetic: A Design Methodology
and Applications in Digital Signal Processing”, VLSI Signal Processing III, R. W.
Brodersen, H. S. Moscovitz eds., IEEE Press, New York, 1988, pp. 252-263.
[5] V. G. Oklobdzija & Milos D. Ercegovac, “An On-Line Square Root Algorithm”,
IEEE Trans. Comput., vol. C-31, Jan. 1982, pp. 70-75.
[6] H. J. Sips & H. X. Lin, “ A New Model for On-Line Arithmetic with an Application
to the Reciprocal Calculation”, J. Parallel & Distrib. Comp. vol. 8, 1990, pp. 218230.
[7] Kishor S. Trivedi & Milos D. Ercegovac, “On-Line Algorithms for Division andMultiplication”, IEEE Trans. Comput., vol. C-26, No 7, July 1977, pp. 681-687.
[8] Paul K.-G. Tu & Milos D. Ercegovac, “Design of On-Line Division Unit”, Proc.
9th Symposium on Computer Arithmetic, Santa Monica CA, 6-8 Sept ’89, IEEE
Comp. Soc. Press, 1989.
[9] J. H. Zurawski & J. B. Gosling, “Design of a high-speed square root, multiply anddivide unit”, IEEE Trans. Comput., vol. C-36, 1987, pp. 13-23.