Technical Reports

The ICICS/CS Reading Room


UBC CS TR-2002-07 Summary

Extended Canonical Recoding, September 05, 2002 Nicholas Pippenger

Canonical recoding transforms a sequence of bits into a sequence of signed digits, preserving the numerical value of the sequence while reducing the number of non-zero digits. It is used to reduce the number of additions and subtractions when performing multiplication (or equivalently, the number of multiplications and divisions when performing exponentiation). Standard canonical recoding uses the digits 0, 1 and -1. Any two non-zero digits are separated by at least one zero, so in the worst case n/2 + O(1) non-zero digits are used to recode an n-bit sequence; in the average case n/3 + O(1) non-zero digits are used. We introduce extended canonical recoding, which uses the digits 0, 1, -1, 3 and -3. Any two non-zero digits are separated by at least two zeroes, so at most n/3 + O(1) non-zero digits are used in the worst case. We show that the scheme is uniquely determined by this condition, and that it is optimal among schemes using the same set of signed digits. Finally, we show that in the average case, extended canonical recoding uses n/4 + O(1) non-zero digits.


If you have any questions or comments regarding this page please send mail to help@cs.ubc.ca.