Addition chain

Addition chain

In mathematics, an addition chain is a sequence "a"0, "a"1, "a"2, "a"3, ... that satisfies

:"a"0 = 1, and :for each "k">0: "a""k" = "a""i" + "a""j" for some "i", "j" < "k".

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: so for example we only need 7 multiplications to calculate 531: :52 = 51 × 51:53 = 52 × 51:56 = 53 × 53:512 = 56 × 56:524 = 512 × 512:530 = 524 × 56:531 = 530 × 51

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 single addition chain 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 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".

References

External links

* http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html
* [http://www.research.att.com/~njas/sequences/A003313 Sequence A003313] , length of the shortest addition chain for "n", "The On-Line Encyclopedia of Integer Sequences".
* [http://www.few.vu.nl/~skn410/bp/AdditionChains.pdf Addition Chains, efficient computing of powers] , General introduction on addition chains, including a comparison of several algorithms for calculating them.

ee also

* Addition chain exponentiation
* Addition-subtraction chain
* Lucas chain
* Scholz conjecture


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • 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 minimal length addition chain that… …   Wikipedia

  • Addition-subtraction chain — An addition subtraction chain, a generalization of addition chains to include subtraction, is a sequence a 0, a 1, a 2, a 3, ... that satisfies:a 0 = 1, ,: ext{for }k > 0, a k = a i pm a j ext{ for some }0 leq i,j < k.An addition subtraction… …   Wikipedia

  • Chain transfer — is a polymerization reaction by which the activity of a growing polymer chain is transferred to another molecule.[1][2] P• + XR → PX + R • Chain transfer reactions reduce the average molecular weight of the final polymer. Chain transfer can be… …   Wikipedia

  • Chain Reaction (John Farnham album) — Chain Reaction Studio album by John Farnham Released …   Wikipedia

  • Addition — is the mathematical process of putting things together. The plus sign + means that two numbers are added together. For example, in the picture on the right, there are 3 + 2 apples meaning three apples and two other apples which is the same as… …   Wikipedia

  • Chain pulling — is the act of pulling a cord that activates the train s emergency brakes to stop a train, whether for a genuine emergency or (often) illegally for someone to get on or off the train on the Indian Railway network. [cite… …   Wikipedia

  • Chain Lakes Provincial Park — Chain Lakes Provincial Park …   Wikipedia

  • Chain growth polymerisation — Chain growth polymerization is a polymerization technique where unsaturated monomer molecules add on to a growing polymer chain one at a time [1]. It can be represented with the chemical equation: where n is the …   Wikipedia

  • Addition polymerization — nM (monomer) ightarrow ( M ) n (polymer)where n is the degree of polymerization.CharacteristicsThe main characteristics are:* polymerisation process takes place in three distinct steps: # chain initiation, usually by means of an initiator which… …   Wikipedia

  • Chain of survival — The chain of survival refers to a series of actions that, when put into motion, reduce the mortality associated with cardiac arrest.[1][2] Like any chain, the chain of survival is only as strong as its weakest link.[1][2] The four interdependent… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”