Addition-subtraction chain
Encyclopedia
An addition-subtraction chain, a generalization of addition chain
s to include subtraction, is a sequence
a0, a1, a2, a3, ... that satisfies
An addition-subtraction chain for n, of length L, is an addition-subtraction chain such that
. 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:
, 
, 
, 
. This is not a minimal addition-subtraction chain for n=3, however, because we could instead have chosen 
. 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):
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
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 curve
s 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:
Other hardware multipliers multiply by n using an addition-subtraction chain described by n in Booth encoding:
Addition chain
In mathematics, an addition chain for computing a positive integer n can be given by a sequence of natural numbers v and a sequence of index pairs w such that each term in v is the sum of two previous terms, the indices of those terms being specified by w:Often only v is given since it is easy to...
s to include subtraction, is a sequence
Sequence
In mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the sequence...
a0, a1, a2, a3, ... that satisfies
An addition-subtraction chain for n, of length L, is an addition-subtraction chain such that
. 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
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
(Downey et al., 1981), but it is not known for certain whether finding optimal addition or addition-subtraction chains is NP-hard
NP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
.
For example, one addition-subtraction chain is:
, , , . This is not a minimal addition-subtraction chain for n=3, however, because we could instead have chosen . 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):Like an addition chain, an addition-subtraction chain can be used for addition-chain exponentiation
Addition-chain exponentiation
In mathematics and computer science, optimal addition-chain exponentiation is a method of exponentiation by positive integer powers that requires a minimal number of multiplications. It works by creating a shortest addition chain that generates the desired exponent. Each exponentiation in the chain...
: given the addition-subtraction chain of length L for n, the power
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 curveElliptic curve
In mathematics, an elliptic curve is a smooth, projective algebraic curve of genus one, on which there is a specified point O. An elliptic curve is in fact an abelian variety — that is, it has a multiplication defined algebraically with respect to which it is a group — and O serves as the identity...
s 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).