addition-subtraction chain

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

:a_0 = 1, \,

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

  • {{cite journal |first=Hugo |last=Volger |title=Some results on addition/subtraction chains |journal=Information Processing Letters |volume=20 |issue=3 |pages=155–160 |date=8 April 1985 |doi=10.1016/0020-0190(85)90085-7}}
  • {{cite journal |first1=François |last1=Morain |first2=Jorge |last2=Olivos |url=https://www.rairo-ita.org/articles/ita/pdf/1990/06/ita1990240605311.pdf |title=Speeding up the computations on an elliptic curve using addition-subtraction chains |journal=Informatique théorique et applications |volume=24 |issue=6 |year=1990 |pages=531–543 |doi=10.1051/ita/1990240605311 |citeseerx=10.1.1.56.347}}
  • {{cite journal |first1=Peter J. |last1=Downey |first2=Benton L. |last2=Leong |first3=Ravi |last3=Sethi | authorlink3=Ravi Sethi |title=Computing sequences with addition chains |journal=SIAM J. Comput. |volume=10 |issue=3 |pages=638–646 |year=1981 |doi=10.1137/0210047}}
  • {{Cite OEIS|1=A128998|2=length of minimum addition-subtraction chain}}

Category:Addition chains