Exponent recoding
Another approach to reducing the number of multiplications in the basic repeated square andmultiply algorithms (§14.6.1) is to replace the binary representation of the exponent e with a representation which has fewer nonzero terms. Since the binary representation is unique (Fact 14.1), finding a representation with fewer nonzero 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: signeddigit representation (§14.7.1) and stringreplacement representation (§14.7.2).
Signeddigit representation
14.120 Definition If e = X^i=o <^*2* where d, € {0,1, —1}, 0 < i < t, then (d_{t} ■ ■ ■ did_{0})sD is called a signeddigit representation with radix 2 for the integer e.
Unlike the binary representation, the signeddigit representation of an integer is not unique. The binary representation is an example of a signeddigit representation. Let e be a positive integer whose binary representation is (et+iete_{t}_i • • • eieo)2, withe_{t+}i = e_{t} = 0. Algorithm 14.121 constructs a signeddigit representation for e having at most t + 1 digits and the smallest possible number of nonzero terms.
14.121 Algorithm Signeddigit exponent recoding
INPUT: a positive integer e = (e_{t+}ie_{t}e_{t}. i ■ ■ ■ eieo)2 with e_{t+}i = e_{t} = 0.
OUTPUT: a signeddigit representation (d_{t} ■ ■ ■ did_{0})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, + ^{e}i_{+}i + c*)/2j, di<—ei + Ci — 2ci_{+}i.
 3. Retum((d_{t} • • • did_{0})sD)
 14.122 Example (signeddigit exponent recoding) Table 14.20 lists all possible inputs to the i^{th }iteration of step 2, and the corresponding outputs. If e = (1101110111)_{2}, then Algorithm 14.121 produces the signeddigit representation e = (IOOTOOOTOOT)sd where T = 1. Note that e = 2^{9} + 2^{8} + 2^{6} + 2^{5} + 2^{4} + 2^{2} + 2 + 1 = 2^{10}  2^{7}  2^{3}  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: Signeddigit exponent recoding (see Example 14.122).
 14.123 Definition A signeddigit representation of an integer e is said to be sparse if no two nonzero entries are adjacent in the representation.
 14.124 Fact (sparse signeddigit representation)
 (i) Ever}' integer e has a unique sparse signeddigit representation.
 (ii) A sparse signeddigit representation for e has the smallest number of nonzero entries among all signeddigit representations for e.
 (iii) The signeddigit representation produced by Algorithm 14.121 is sparse.
 14.125 Note (computational efficiency of signeddigit exponent recoding)
 (i) Signeddigit exponent recoding as per Algorithm 14.121 is very efficient, and can be done by table lookup (using Table 14.20).
 (ii) When e is given in a signeddigit representation, computing g^{e} 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 signeddigit representation may not be worthwhile.