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:

v =(v₀,...,v_s), with v₀ = 1 and v_s = n

for each 0< i ≤ s holds: v_i = v_j + v_k, with w_i=(j,k) and 0 ≤ j,k ≤ i − 1

Often only v is given since it is easy to extract w from v, but sometimes w is not uniquely reconstructible. An introduction is given in .

Examples

As an example: v = (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: so for example we only need 7 multiplications to calculate 5³¹:

5² = 5¹ × 5¹

5³ = 5² × 5¹

5⁶ = 5³ × 5³

5¹² = 5⁶ × 5⁶

5²⁴ = 5¹² × 5¹²

5³⁰ = 5²⁴ × 5⁶

5³¹ = 5³⁰ × 5¹

Methods for computing addition chains

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. 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 to calculate relatively short chains exist. One very well known technique to calculate relatively short addition chains is the binary method, similar to exponentiation by squaring. Other well-known methods are the factor method and window method.^{[citation needed]}

Notations

A Brauer chain or star addition chain is an addition chain in which one of the summands is always the previous chain: that is,

for each k>0: a_k = a_k-1 + a_j for some j < k.

Brauer number is one for which the Brauer chain is minimal.

Let $l(n)$ denote the smallest s so that there exists an addition chain of length s which computes n. It is known that

$\log(n)+ \log(\nu(n))-2.13\leq l(n) \leq \log(n) + \log(n)(1+o(1))/\log(\log(n))$,

where $\nu(n)$ is Hamming weight of binary expansion of n.

See also

• Addition chain exponentiation
• Addition-subtraction chain
• Vectorial addition chain
• Lucas chain
• Scholz conjecture

References

• Richard K. Guy (2004). Unsolved Problems in Number Theory. Springer-Verlag. ISBN 0-387-20860-7. OCLC 54611248.  Section C6.

External links

• http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html
• Sloane's A003313 : Length of shortest addition chain for n. The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
• F. Bergeron, J. Berstel. S. Brlek "Efficient computation of addition chains"