Addition-subtraction chain

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

${\displaystyle a_{0}=1,\,}$

${\displaystyle {\text{for }}k>0,\ a_{k}=a_{i}\pm a_{j}{\text{ for some }}0\leq i,j<k.}$

An addition-subtraction chain for n, of length L, is an addition-subtraction chain such that ${\displaystyle 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: ${\displaystyle a_{0}=1}$, ${\displaystyle a_{1}=2=1+1}$, ${\displaystyle a_{2}=4=2+2}$, ${\displaystyle a_{3}=3=4-1}$. This is not a minimal addition-subtraction chain for n=3, however, because we could instead have chosen ${\displaystyle 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):

${\displaystyle 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 ${\displaystyle x^{n}}$ can be computed by multiplying or dividing by xL 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

• Volger, Hugo (8 April 1985). "Some results on addition/subtraction chains". Information Processing Letters. 20 (3): 155–160. doi:10.1016/0020-0190(85)90085-7.
• Morain, François; Olivos, Jorge (1990). "Speeding up the computations on an elliptic curve using addition-subtraction chains" (PDF). Informatique théorique et applications. 24 (6): 531–543. CiteSeerX   10.1.1.56.347 .
• Downey, Peter J.; Leong, Benton L.; Sethi, Ravi (1981). "Computing sequences with addition chains". SIAM J. Comput. 10 (3): 638–646. doi:10.1137/0210047.
• Sloane, N. J. A. (ed.). "SequenceA128998(length of minimum addition-subtraction chain)". The On-Line Encyclopedia of Integer Sequences . OEIS Foundation.