Addition-subtraction Chain

An addition-subtraction chain, a generalization of addition chains to include subtraction, is a sequence ''a''₀, ''a''₁, ''a''₂, ''a''₃, ... that satisfies

:$a_0 = 1, \,$
:$\textk > 0,\ a_k = a_i \pm a_j\text0 \leq 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''₋₁ = 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

*
*
*
* {{Cite OEIS, 1=A128998, 2=length of minimum addition-subtraction chain

Addition chains