Addition-subtraction chain


An addition-subtraction chain, a generalization of addition chains to include subtraction, is a sequence a0, a1, a2, a3,... 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.
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 is a difficult problem for which no efficient algorithms are currently known. The related problem of finding an optimal addition sequence is NP-complete, 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 :
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.
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.

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.