Harman Patil (Editor)

Addition subtraction chain

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

An addition-subtraction chain, a generalization of addition chains to include subtraction, is a sequence a0, a1, a2, a3, ... that satisfies

a 0 = 1 , for  k > 0 ,   a k = a i ± a j  for some  0 i , j < k .

An addition-subtraction chain for n, of length L, is an addition-subtraction chain such that a L = n . That is, one can thereby compute n by L additions and/or subtractions. (Note that n need not be positive. In this case, one may also include a−1 = 0 in the sequence, so that n = −1 can be obtained by a chain of length 1.)

By definition, every addition chain is also an addition-subtraction chain, but not vice versa. Therefore, the length of the shortest addition-subtraction chain for n is bounded above by the length of the shortest addition chain for n. In general, however, the determination of a minimal addition-subtraction chain (like the problem of determining a minimum addition chain) is a difficult problem for which no efficient algorithms are currently known. The related problem of finding an optimal addition sequence is NP-complete (Downey et al., 1981), but it is not known for certain whether finding optimal addition or addition-subtraction chains is NP-hard.

For example, one addition-subtraction chain is: a 0 = 1 , a 1 = 2 = 1 + 1 , a 2 = 4 = 2 + 2 , a 3 = 3 = 4 1 . This is not a minimal addition-subtraction chain for n=3, however, because we could instead have chosen a 2 = 3 = 2 + 1 . The smallest n for which an addition-subtraction chain is shorter than the minimal addition chain is n=31, which can be computed in only 6 additions (rather than 7 for the minimal addition chain):

a 0 = 1 ,   a 1 = 2 = 1 + 1 ,   a 2 = 4 = 2 + 2 ,   a 3 = 8 = 4 + 4 ,   a 4 = 16 = 8 + 8 ,   a 5 = 32 = 16 + 16 ,   a 6 = 31 = 32 1.

Like an addition chain, an addition-subtraction chain can be used for addition-chain exponentiation: given the addition-subtraction chain of length L for n, the power x n can be computed by multiplying or dividing by x L times, where the subtractions correspond to divisions. This is potentially efficient in problems where division is an inexpensive operation, most notably for exponentiation on elliptic curves where division corresponds to a mere sign change (as proposed by Morain and Olivos, 1990).

Some hardware multipliers multiply by n using an addition chain described by n in binary:

n = 31 = 0 0 0 1 1 1 1 1 (binary).

Other hardware multipliers multiply by n using an addition-subtraction chain described by n in Booth encoding:

n = 31 = 0 0 1 0 0 0 0 -1 (Booth encoding).

References

Addition-subtraction chain Wikipedia