Limit comparison test

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

$a_0=1,$

$\text{for }k>0,a_k=a_i\pm a_j\text{ for some }0\le 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

• Hugo Volger, "Some results on addition/subtraction chains," Information Processing Letters 20, pp. 155-160 (1985).
• François Morain and Jorge Olivos, "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).
• Sequence Physiotherapist Rave from Cobden, has hobbies and interests which includes skateboarding, commercial property for sale developers in singapore and coin collecting. May be a travel freak and in recent years made a journey to Wet Tropics of Queensland., length of minimum addition-subtraction chain, The On-Line Encyclopedia of Integer Sequences.