Addition-subtraction chain explained

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

a _{0} = 1 , for k > 0 , a _{k} = a _{i} \pm a _{jforsome0} \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

• Hugo . Volger . Some results on addition/subtraction chains . Information Processing Letters . 20 . 3 . 155–160 . 8 April 1985 . 10.1016/0020-0190(85)90085-7.
• François . Morain . Jorge . Olivos . Speeding up the computations on an elliptic curve using addition-subtraction chains . Informatique théorique et applications . 24 . 6 . 1990 . 531– 543 . 10.1.1.56.347.
• Peter J. . Downey . Benton L. . Leong . Ravi . Sethi . Ravi Sethi . Computing sequences with addition chains . . 10 . 3 . 638–646 . 1981 . 10.1137/0210047.
• A128998. length of minimum addition-subtraction chain.