 Exponent recoding

Another approach to reducing the number of multiplications in the basic repeated square- and-multiply algorithms (§14.6.1) is to replace the binary representation of the exponent e with a representation which has fewer non-zero terms. Since the binary representation is unique (Fact 14.1), finding a representation with fewer non-zero components necessitates the use of digits besides 0 and 1. Transforming an exponent from one representation to another is called exponent recoding. Many techniques for exponent recoding have been proposed in the literature. This section describes two possibilities: signed-digit representation (§14.7.1) and string-replacement representation (§14.7.2).

Signed-digit representation

14.120 Definition If e = X^i=o <^*2* where d,- € {0,1, —1}, 0 < i < t, then (dt ■ ■ ■ did0)sD is called a signed-digit representation with radix 2 for the integer e.

Unlike the binary representation, the signed-digit representation of an integer is not unique. The binary representation is an example of a signed-digit representation. Let e be a positive integer whose binary representation is (et+ietet_i • • • eieo)2, withet+i = et = 0. Algorithm 14.121 constructs a signed-digit representation for e having at most t + 1 digits and the smallest possible number of non-zero terms.

14.121 Algorithm Signed-digit exponent recoding

INPUT: a positive integer e = (et+ietet. i ■ ■ ■ eieo)2 with et+i = et = 0.

OUTPUT: a signed-digit representation (dt ■ ■ ■ did0)sD for e. (See Definition 14.120.)

• 1. co^—0.
• 2. For i from 0 to / do the following:
• 2.1 Ci+i<— L(e, + ei+i + c*)/2j, di<—ei + Ci — 2ci+i.
• 3. Retum((dt • • • did0)sD)-
• 14.122 Example (signed-digit exponent recoding) Table 14.20 lists all possible inputs to the ith iteration of step 2, and the corresponding outputs. If e = (1101110111)2, then Algorithm 14.121 produces the signed-digit representation e = (IOOTOOOTOOT)sd where T = -1. Note that e = 29 + 28 + 26 + 25 + 24 + 22 + 2 + 1 = 210 - 27 - 23 - 1. □
 inputs ei 0 0 0 0 1 1 1 1 d 0 0 1 1 0 0 1 1 e»+1 0 1 0 1 0 1 0 1 outputs Ci+l 0 0 0 1 0 1 1 1 di 0 0 1 -1 1 -1 0 0

Table 14.20: Signed-digit exponent recoding (see Example 14.122).

• 14.123 Definition A signed-digit representation of an integer e is said to be sparse if no two nonzero entries are adjacent in the representation.
• 14.124 Fact (sparse signed-digit representation)
• (i) Ever}' integer e has a unique sparse signed-digit representation.
• (ii) A sparse signed-digit representation for e has the smallest number of non-zero entries among all signed-digit representations for e.
• (iii) The signed-digit representation produced by Algorithm 14.121 is sparse.
• 14.125 Note (computational efficiency of signed-digit exponent recoding)
• (i) Signed-digit exponent recoding as per Algorithm 14.121 is very efficient, and can be done by table look-up (using Table 14.20).
• (ii) When e is given in a signed-digit representation, computing ge requires both g and g~ 1. If g is a fixed base, then g 1 can be precomputed. For a variable base g, unless g~l can be computed very quickly, recoding an exponent to signed-digit representation may not be worthwhile.