next up previous contents
Next: Multiplication Up: Average Previous: Dyadic Stream Average

Signed Binary Stream Average

  The algorithm for computing the average of two signed binary streams (section 4.3.1) theoretically requires (n+1) input digits to generate n output digits, although in certain cases (when the combination of input and carry digits allow the algorithm to determine the required output digit without examining further input), only n input digits will be required to generate n output digits. The algorithm does not branch as it proceeds.

Martin Escardo