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*_{0},...,*v*_{s}), with*v*_{0}= 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 by Knuth.

Read more about Addition Chain: Examples, Methods For Computing Addition Chains, Chain Length, Brauer Chain, Scholz Conjecture

### Other articles related to "addition, addition chain, chains":

... Exponentiation by squaring can be viewed as a suboptimal

**addition**-chain exponentiation algorithm it computes the exponent via an

**addition chain**consisting of ... this occurs is for n=15 (squaring, 6 multiplies) (optimal

**addition chain**, 5 multiplies if x3 is re-used) In general, finding the optimal

**addition chain**for a given exponent is a ... in compilers where the

**chains**for small powers have been pre-tabulated) ...

### Famous quotes containing the words chain and/or addition:

“It could not have come down to us so far,

Through the interstices of things ajar

On the long bead *chain* of repeated birth,

To be a bird while we are men on earth,”

—Robert Frost (1874–1963)

“As easy mayst thou fall

A drop of water in the breaking gulf,

And take unmingled thence that drop again,

Without *addition* or diminishing,

As take from me thyself and not me too.”

—William Shakespeare (1564–1616)