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,\; ,$:

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\_2=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).

References

* Hugo Volger, "Some results on addition/subtraction chains," "Information Processing Letters" 20, pp. 155-160 (1985).
* François Morain and Jorge Olivos, " [ftp://ftp.inria.fr/INRIA/publication/Theses/TU-0144/ch4.ps 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).
* [http://www.research.att.com/~njas/sequences/A128998 Sequence A128998] , length of minimum addition-subtraction chain, "The On-Line Encyclopedia of Integer Sequences".