Extended Canonical Recoding

ID
TR-2002-07
Authors
Nicholas Pippenger
Publishing date
September 05, 2002
Abstract
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 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, 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.