addition chain

As an example: (1,2,3,6,12,24,30,31) is an addition chain for 31 of length 7, since

:2 = 1 + 1

:3 = 2 + 1

:6 = 3 + 3

:12 = 6 + 6

:24 = 12 + 12

:30 = 24 + 6

:31 = 30 + 1

Addition chains can be used for addition-chain exponentiation. This method allows exponentiation with integer exponents to be performed using a number of multiplications equal to the length of an addition chain for the exponent. For instance, the addition chain for 31 leads to a method for computing the 31st power of any number {{mvar|n}} using only seven multiplications, instead of the 30 multiplications that one would get from repeated multiplication, and eight multiplications with exponentiation by squaring:

:{{mvar|n}}² = {{mvar|n}} × {{mvar|n}}

:{{mvar|n}}³ = {{mvar|n}}² × {{mvar|n}}

:{{mvar|n}}⁶ = {{mvar|n}}³ × {{mvar|n}}³

:{{mvar|n}}¹² = {{mvar|n}}⁶ × {{mvar|n}}⁶

:{{mvar|n}}²⁴ = {{mvar|n}}¹² × {{mvar|n}}¹²

:{{mvar|n}}³⁰ = {{mvar|n}}²⁴ × {{mvar|n}}⁶

:{{mvar|n}}³¹ = {{mvar|n}}³⁰ × {{mvar|n}}

Calculating an addition chain of minimal length is not easy; a generalized version of the problem, in which one must find a chain that simultaneously forms each of a sequence of values, is NP-complete.{{citation|first1=Peter|last1=Downey|first2=Benton|last2=Leong|first3=Ravi|last3=Sethi|title=Computing sequences with addition chains|journal=SIAM Journal on Computing|volume=10|issue=3|year=1981|pages=638–646|doi=10.1137/0210047}}. A number of other papers state that finding a shortest addition chain for a single number is NP-complete, citing this paper, but it does not claim or prove such a result. There is no known algorithm which can calculate a minimal addition chain for a given number with any guarantees of reasonable timing or small memory usage. However, several techniques are known to calculate relatively short chains that are not always optimal.{{citation|url=http://math-www.uni-paderborn.de/~aggathen/Publications/ott01.pdf|series=Diplomarbeit|title=Brauer addition-subtraction chains|last=Otto|first=Martin|year=2001|publisher=University of Paderborn|access-date=2013-10-19|archive-url=https://web.archive.org/web/20131019165828/http://math-www.uni-paderborn.de/~aggathen/Publications/ott01.pdf|archive-date=2013-10-19|url-status=dead}}.

One very well known technique to calculate relatively short addition chains is the binary method, similar to exponentiation by squaring. In this method, an addition chain for the number $n$ is obtained recursively, from an addition chain for $n\text{'}=\backslash lfloor\; n/2\backslash rfloor$. If $n$ is even, it can be obtained in a single additional sum, as $n=n\text{'}+n\text{'}$. If $n$ is odd, this method uses two sums to obtain it, by computing $n-1=n\text{'}+n\text{'}$ and then adding one.

The factor method for finding addition chains is based on the prime factorization of the number $n$ to be represented. If $n$ has a number $p$ as one of its prime factors, then an addition chain for $n$ can be obtained by starting with a chain for $n/p$, and then concatenating onto it a chain for $p$, modified by multiplying each of its numbers by $n/p$. The ideas of the factor method and binary method can be combined into Brauer's m-ary method by choosing any number $m$ (regardless of whether it divides $n$), recursively constructing a chain for $\backslash lfloor\; n/m\backslash rfloor$, concatenating a chain for $m$ (modified in the same way as above) to obtain $m\backslash lfloor\; n/m\backslash rfloor$, and then adding the remainder. Additional refinements of these ideas lead to a family of methods called sliding window methods.

Let $l(n)$ denote the smallest $s$ so that there exists an addition chain

of length $s$ which computes $n$.

It is known that

$$\backslash log\_2\; n+\; \backslash log\_2\; \backslash nu(n)-2.13\backslash leq\; l(n)\; \backslash leq\; \backslash log\_2\; n+\; \backslash nu(n)-1,$$

$$l(n)\; \backslash leq\; \backslash log\_2\; n\; +\; \backslash bigl(1+o(1)\backslash bigr)\backslash frac\{\backslash log\_2\; n\}\{\backslash log\_2\; \backslash log\_2\; n\},$$

where $\backslash nu(n)$ is the Hamming weight (the number of ones) of the binary expansion of $n$.{{citation|last=Schönhage|first=Arnold|authorlink=Arnold Schönhage|doi=10.1016/0304-3975(75)90008-0|issue=1|journal=Theoretical Computer Science|pages=1–12|title=A Lower Bound for the Length of Addition Chains|volume=1|year=1975|doi-access=}}

One can obtain an addition chain for $2n$ from an addition chain for $n$ by including one additional sum $2n=n+n$, from which follows the inequality $l(2n)\backslash le\; l(n)+1$ on the lengths of the chains for $n$ and $2n$. However, this is not always an equality,

as in some cases $2n$ may have a shorter chain than the one obtained in this way. For instance, $l(382)=l(191)=11$, observed by Knuth. It is even possible for $2n$ to have a shorter chain than $n$, so that ; the smallest $n$ for which this happens is $n=375494703$, which is followed by $602641031$, $619418303$, and so on {{OEIS|A230528}}.

A Brauer chain or star addition chain is an addition chain in which each of the sums used to calculate its numbers uses the immediately previous number. A Brauer number is a number for which a Brauer chain is optimal.

Brauer proved that

:{{math|l^*(2ⁿ−1) ≤ n − 1 + l^*(n)}}

where {{tmath|l^*}} is the length of the shortest star chain.{{cite journal | last1=Brauer | first1=Alfred | title=On addition chains | doi=10.1090/S0002-9904-1939-07068-7 | mr=0000245 | year=1939 | journal=Bulletin of the American Mathematical Society | issn=0002-9904 | volume=45 | issue=10 | pages=736–739| doi-access=free }} For many values of $n$, and in particular for , they are equal:Achim Flammenkamp, [http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html Shortest Addition Chains] {{math|1=l(n) = l^*(n)}}. But Hansen showed that there are some values of n for which {{math|l(n) ≠ l^*(n)}}, such as {{math|1=n = 2⁶¹⁰⁶ + 2³⁰⁴⁸ + 2²⁰³² + 2²⁰¹⁶ + 1}} which has {{math|1=l^*(n) = 6110, l(n) ≤ 6109}}. The smallest such n is 12509.

{{main|Scholz conjecture}}

The Scholz conjecture (sometimes called the Scholz–Brauer or Brauer–Scholz conjecture), named after Arnold Scholz and Alfred T. Brauer), is a conjecture from 1937 stating that

:$l(2^n-1)\; \backslash le\; n\; -\; 1\; +\; l(n).$

This inequality is known to hold for all Hansen numbers, a generalization of Brauer numbers; Neill Clift checked by computer that all $n\; \backslash le\; 5784688$ are Hansen (while 5784689 is not).{{cite journal |first=Neill Michael |last=Clift |year=2011 |title=Calculating optimal addition chains |journal=Computing |volume=91 |issue=3 |pages=265–284 |doi=10.1007/s00607-010-0118-8 |url=https://link.springer.com/content/pdf/10.1007%2Fs00607-010-0118-8.pdf|doi-access=free }} Clift further verified that in fact $l(2^n-1)\; =\; n\; -\; 1\; +\; l(n)$ for all $n\; \backslash le\; 64$.{{cite book|author=Richard K. Guy|authorlink=Richard K. Guy|title=Unsolved Problems in Number Theory|publisher=Springer-Verlag|year=2004|isbn=978-0-387-20860-2|oclc=54611248 | zbl=1058.11001}} Section C6, p.169.

• Addition-subtraction chain
• Vectorial addition chain
• Lucas chain

{{reflist}}

• {{OEIS el|sequencenumber=A003313|name=Length of shortest addition chain for n}}. Note that the initial "1" is not counted (so element #1 in the sequence is 0).
• [http://www.numdam.org/item?id=JTNB_1994__6_1_21_0 F. Bergeron, J. Berstel. S. Brlek "Efficient computation of addition chains"]

{{DEFAULTSORT:Addition Chain}}

*

Category:NP-complete problems