next up previous contents
Next: Signed Binary Multiplication Up: Experimental Analysis Previous: Timing

Lookahead Results

  In general, the lookahead experiments performed confirm the predictions made in section 7.1. When analysing the algorithms for dyadic stream average and multiplication, we observe that the lookahead is constant, and this was reflected in the results of the experimentation. The algorithms for signed binary average and multiplication and the division algorithm are more interesting because the lower and upper bounds on lookahead are not the same.

We show the results of experimentation with the lookahead of the signed binary multiplication and the division algorithms. These show how the average lookahead required might be related to the predicted lower and upper bounds. To illustrate the results we use two streams a and b are defined as follows:

a = [1, 0, -1, 0, 0, -1, 1, 0, 0, -1, 0, 1, 0, 1, 0, 1, -1, 0, 1, 0, 0, -1, 0, 1, 0,
     -1, 1, 0, -1, 0, 0, 0, 0, 0, 0, 1, 0, -1, 1, 0, -1, 0, 0, 0, 0, -1] ++ a

b = [1, 1, 0, -1, 0, -1, 0, 1, 0, 1, 0, -1, 0, 0, 1, -1, 0, 0, 0, 1, 0, 0, 0, 0, 0, -1,
     1, 0, -1, 0, -1, -1, 1, 0, -1, 1, -1, 0, 0, 0, -1, 0, 1, 0, 0, 0, 1, 0] ++ b

These numerals are random, have a roughly even mix of signed binary digits, and cycle with (different) periods of roughly 50 digits. The experimentation is not extensive or systematic, and only two of the results are given here.



 

Martin Escardo
5/11/2000