Improving Average Delay for On-LineArithmetic Algorithms
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. Using normalised input directly for on-line arithmetic does
not always lead to minimal on-line delay. Shifting some inputs can reduce
the average delay.
Index Terms: Computer arithmetic, multiplication, on-line delay, online algorithms, redundant number systems, recurrence relations.

1Introduction

On-line algorithms consume their inputs and generate output digit serially at
the same rate, most significant bit first. So 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. Such algorithms for
multiplication, division and square root have been extensively studied in theliterature, usually using a simple addition for the iterative step (see [2], [4], [1]),but sometimes using a fuller, more accurate computation (see [3]), or without
all inputs being on-line (see [5]). However, it is invariably the case that only normalised or pseudo-normalised input is allowed (i.e. that in the half-open intervals[1/2, 1) or [1/4, 1)), and this rarely fits well with an optimal choice for δ: δ could
be reduced by changing the input interval. In practice, it is more convenient toretain the usual input intervals, but shift those inputs for which the reduced
value of δ fails. The input conditions necessary for the reduced delay need to beestablished, and a procedure given for deciding which inputs should be shifted.
They are considered here in the case of multiplication where, because of thesmall value of δ, the detail is at one time more significant and less obscured by
the algorithm.

2The Notation

We start with a definition of the multiplication algorithm. We consider mainly
mantissas M of real numbers with redundant radix 2 representations M ≡2Electronics Letters 30 (1994), No. 23, pp. 1925-1926

P∞−tdigit set {−1, 0, +1}. At time
t=1 mt 2 , where the digit mt lies in the signedPjPjj ≥ 0, the first j digits provide inputs X[j] ≡ t=1 xt 2−t and Y [j] ≡ t=1 yt 2−t .

The output digit pj−δ of the product P is formed using the scaled partial remainder
W [j] = 2j {X[j]×Y [j] − P [j−1−δ]}which is calculated using the recurrence relation
W [j+1] = 2W [j] + yj+1 X[j] + xj+1 Y [j] + 2−1−j xj+1 yj+1 − 21+δ pj−δwith initial value W [0] = 0. The digit pj−δ is chosen to minimise W [j] if it wereincluded in its definition, but speed is gained by using just the approximation
W [j]0 , which is given by truncating all digits after that of index ε. So, for somefixed integer i, we definepj−δ = +1 if 2ε W [j]0 ≥ i
0 if |2ε W [j]0 | < i−1 if 2ε W [j]0 ≤ −i
It is fairly straightforward to show by induction on j that
B[j] = 21+δ −|X[j]|−|Y [j]|−2−j
is a bound on the absolute value of W [j] for j > δ when both21−ε i+ 4 ≤ 21+δ and1−ε
2 (1−i) + 4 ≤ 0
hold. This is optimally the case for δ = 3, ε = −1 and i = 2 or 3.

3

Input Bounds.

Redoing the proof of the algorithm for fixed δ, ε and i enables conditions on theinputs to be derived for which the algorithm will work. For the base case of theinduction argument we require |W [δ]| ≤ |B[δ]|. This certainly holds for |X| < 1and |Y | < 1 since |X[t]| ≤ 1 − 2−t and |Y [t]| ≤ 1 − 2−t for all t ≥ 0.
Now assume W [j] ≤ B[j] where j ≥ δ. For convenience, suppose X > 0,Y > 0 and ε < δ. The induction step for pj−δ = 1 is easy to verify because
the bounds B[j] are chosen precisely so that it does work. So suppose pj−δ = 0.
As W [j] has at most j digits after the point, W [j]+2−j ≤ W [j]0 +2−ε ≤ 2−ε i.
Hence, from the definition of W [j+1],
W [j+1] ≤ 21−ε i − 21−j + X[j+1] + Y [j+1] − 2−1−jwhich is at most B[j+1] when21−ε i + 2X + 2Y ≤ 21+δ

C. D. Walter, On-Line Arithmetic Algorithms

3Now suppose pj−δ = −1. Then, W [j]+2−j ≤ W [j]0 +2−ε ≤ 2−ε (1−i), and so,
W [j+1] ≤ 21−ε (1−i) − 21−j + X[j+1] + Y [j+1] − 2−1−j + 21+δThis is at most B[j+1] if21−ε (1−i) + 2X + 2Y ≤ 0
Combining these two inequalities, we obtain convergence of the algorithm when
|X| + |Y | ≤ min{2−ε (i−1), 2δ −2−ε i}Clearly, as |X|+|Y | < 2, this holds for the original choice of parameters.

4

Fractional Delays

An improved delay is obtained by the choice δ = 2, ε = 1 and i = 4 or 5, for
inputs satisfying |X|+|Y | < 3/2. If the multiplier receives normalised input, thenover-large inputs must be shifted down until they are small enough to satisfy theinitial conditions. A fractional average delay results which is an improvement on
the earlier δ = 3. The cost of this is i) not all output shows the same time delay,ii) the initial bound checking, and iii) the extra digit used in W 0 for computing
the output digit.
Suppose the two inputs are uniformly and independently distributed over theinterval [1/2, 1). Half the inputs satisfy the bound and theoretically for them we
could have just 2 cycles delay between input and output. For the other inputs,
the larger input must be divided by 2 before the multiplication, resulting in
3 cycles delay. This apparently yields an improved average delay of 2.5 cycles.
However, the exact test to see if the bound is met requires the examination ofarbitrarily many digits, and so is not feasible since it must be completed before
the output digits start to be generated. Thus any required action needs to bebased on the first δ input digits. Already x1 = y1 = 1 because of the assumptions
on the input range. Without looking at further digits, only when x2 = y2 = 0
is the input bound now guaranteed. Otherwise, just in case, either input, say
X, must be halved to guarantee the condition holds. This can be done withoutchanging the already processed first digit by inserting 1̄ for x2 and delaying
the actual x2 and subsequent digits by one cycle. In consequence the output isgenerated one cycle later, i.e. as if δ were 3. Three quarters of all inputs aredelayed in this way by one cycle. But, overall, an improved average delay δ of2.75 is thus obtained.

5Conclusion.

We have shown how to reduce the average delay for on-line algorithms at minor
hardware cost, illustrating the ideas using the example of multiplication.

4Electronics Letters 30 (1994), No. 23, pp. 1925-1926

References[1] Milos D. Ercegovac, “An On-Line Square Rooting Algorithm”, Proc. 4th IEEE
Symposium on Computer Arithmetic, Santa Monica, CA, 1978, pp. 183-189.
[2] Milos D. Ercegovac & Tomas Lang, “On-Line Arithmetic: A Design Methodologyand Applications in Digital Signal Processing”, VLSI Signal Processing III, R. W.
Brodersen, H. S. Moscovitz eds., IEEE Press, New York, 1988, pp. 252-263.
[3] 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.
[4] 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.
[5] 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.