# Addition-subtraction chain

An **addition-subtraction chain**, a generalization of addition chains to include subtraction, is a sequence *a*_{0}, *a*_{1}, *a*_{2}, *a*_{3}, ... that satisfies

An addition-subtraction chain for *n*, of length *L*, is an addition-subtraction chain such that . 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: , , , . This is not a *minimal* addition-subtraction chain for *n*=3, however, because we could instead have chosen . 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):

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 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

- Hugo Volger, "Some results on addition/subtraction chains,"
*Information Processing Letters***20**, pp. 155-160 (1985). - François Morain and Jorge Olivos, "Speeding up the computations on an elliptic curve using addition-subtraction chains,"
*RAIRO Informatique théoretique et application***24**, pp. 531-543 (1990). - Peter Downey, Benton Leong, and Ravi Sethi, "Computing sequences with addition chains,"
*SIAM J. Computing***10**(3), 638-646 (1981). - Sequence A128998, length of minimum addition-subtraction chain,
*The On-Line Encyclopedia of Integer Sequences*.