In mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, an addition chain for computing a positive integer n can be given by 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...

 of natural number

Natural number

In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...

s 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

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...

: so for example we only need 7 multiplication

Multiplication

Multiplication is the mathematical operation of scaling one number by another. It is one of the four basic operations in elementary arithmetic ....

s 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

Exponentiation by squaring

Exponentiating by squaring is a general method for fast computation of large integer powers of a number. Some variants are commonly referred to as square-and-multiply algorithms or binary exponentiation. In additive notation the appropriate term is double-and-add...

. Other well-known methods are the factor method and window method.

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 denote the smallest s so that there exists an addition chain
of length s which computes n.
It is known that ,
where is Hamming weight

Hamming weight

The Hamming weight of a string is the number of symbols that are different from the zero-symbol of the alphabet used. It is thus equivalent to the Hamming distance from the all-zero string of the same length. For the most typical case, a string of bits, this is the number of 1's in the string...

 of binary expansion of n.

See also

• Addition chain exponentiation
• Addition-subtraction chain
• Vectorial addition chain
  Vectorial addition chain
  In mathematics, for positive integers k and s, a vectorial addition chain is a sequence V of k-dimensional vectors of nonnegative integers vi for −k + 1 ≤ i ≤ s together with a sequence w,such that*Addition chain...
  
  
• Lucas chain
  Lucas chain
  In mathematics, a Lucas chain is a restricted type of addition chain, named for the French mathematician Édouard Lucas. It is a sequencethat satisfies...
  
  
• Scholz conjecture
  Scholz conjecture
  In mathematics, the Scholz conjecture sometimes called the Scholz–Brauer conjecture or the Brauer–Scholz conjecture In mathematics, the Scholz conjecture sometimes called the Scholz–Brauer conjecture or the Brauer–Scholz conjecture In mathematics, the Scholz conjecture sometimes called the...
  
  

External links

• http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html
• Sequence , length of the shortest addition chain for n, The On-Line Encyclopedia of Integer Sequences.

• F. Bergeron, J. Berstel. S. Brlek "Efficient computation of addition chains"