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 =(v0,...,vs), with v0 = 1 and vs = n
for each 0< is holds: vi = vj + vk, with wi=(j,k) and 0 ≤ j,ki − 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 - Alternatives and Generalizations
... 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)