Addition-subtraction chain

An addition-subtraction chain, a generalization of addition chains to include subtraction, is a sequence a₀, a₁, a₂, a₃, . In Mathematics, an addition chain is a Sequence a 0 a 1 a 2 a 3. In Mathematics, a sequence is an ordered list of objects (or events . . 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. In Computational complexity theory, the Complexity class NP-complete (abbreviated NP-C or NPC) is a class of problems having two properties , 1981), but it is not known for certain whether finding optimal addition or addition-subtraction chains is NP-hard. NP-hard (nondeterministic Polynomial-time hard in Computational complexity theory, is a class of problems informally "at least as hard as the hardest problems

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. In Mathematics and Computer science, optimal addition-chain exponentiation is a method of Exponentiation by positive Integer powers that requires 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). In Mathematics, an elliptic curve is a smooth, projective Algebraic curve of genus one on which there is a specified point O

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 A128998, length of minimum addition-subtraction chain, The On-Line Encyclopedia of Integer Sequences. The On-Line Encyclopedia of Integer Sequences ( OEIS) also cited simply as Sloane's, is an extensive searchable Database of Integer sequences

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
network: | |