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.
 
Source
< Prev   CONTENTS   Source   Next >