Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Addition-chain_exponentiation> ?p ?o. }
Showing items 1 to 31 of
31
with 100 items per page.
- Addition-chain_exponentiation abstract "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 can be evaluated by multiplying two of the earlier exponentiation results. More generally, addition-chain exponentiation may also refer to exponentiation by non-minimal addition chains constructed by a variety of algorithms (since a shortest addition chain is very difficult to find).The shortest addition-chain algorithm requires no more multiplications than binary exponentiation and usually less. The first example of where it does better is for a15, where the binary method needs six multiplies but a shortest addition chain requires only five: (binary, 6 multiplications)(shortest addition chain, 5 multiplications).On the other hand, the addition-chain method is much more complicated, since the determination of a shortest addition chain seems quite difficult: no efficient optimal methods are currently known for arbitrary exponents, and the related problem of finding a shortest addition chain for a given set of exponents has been proven NP-complete. Even given a shortest chain, addition-chain exponentiation requires more memory than the binary method, because it must potentially store many previous exponents from the chain simultaneously. In practice, therefore, shortest addition-chain exponentiation is primarily used for small fixed exponents for which a shortest chain can be precomputed and is not too large.However, there are also several methods to approximate a shortest addition chain, and which often require fewer multiplications than binary exponentiation. Indeed, binary exponentiation itself is a suboptimal addition-chain algorithm. The optimal algorithm choice depends on the context (such as the relative cost of the multiplication and the number of times a given exponent is re-used).Note that the problem of finding the shortest addition chain cannot be solved by dynamic programming, because it does not satisfy the assumption of optimal substructure. That is, it is not sufficient to decompose the power into smaller powers, each of which is computed minimally, since the addition chains for the smaller powers may be related (to share computations). For example, in the shortest addition chain for a15 above, the subproblem for a6 must be computed as (a3)2 since a3 is re-used (as opposed to, say, a6 = a2(a2)2, which also requires three multiplies).".
- Addition-chain_exponentiation wikiPageExternalLink pippenger.pdf.
- Addition-chain_exponentiation wikiPageID "856356".
- Addition-chain_exponentiation wikiPageRevisionID "581190418".
- Addition-chain_exponentiation hasPhotoCollection Addition-chain_exponentiation.
- Addition-chain_exponentiation subject Category:Addition_chains.
- Addition-chain_exponentiation subject Category:Computer_arithmetic_algorithms.
- Addition-chain_exponentiation subject Category:Exponentials.
- Addition-chain_exponentiation type Abstraction100002137.
- Addition-chain_exponentiation type Act100030358.
- Addition-chain_exponentiation type Activity100407535.
- Addition-chain_exponentiation type Algorithm105847438.
- Addition-chain_exponentiation type ArbitraryPrecisionAlgorithms.
- Addition-chain_exponentiation type Event100029378.
- Addition-chain_exponentiation type Exponential113789462.
- Addition-chain_exponentiation type Exponentials.
- Addition-chain_exponentiation type Function113783816.
- Addition-chain_exponentiation type MathematicalRelation113783581.
- Addition-chain_exponentiation type Procedure101023820.
- Addition-chain_exponentiation type PsychologicalFeature100023100.
- Addition-chain_exponentiation type Relation100031921.
- Addition-chain_exponentiation type Rule105846932.
- Addition-chain_exponentiation type YagoPermanentlyLocatedEntity.
- Addition-chain_exponentiation comment "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 can be evaluated by multiplying two of the earlier exponentiation results.".
- Addition-chain_exponentiation label "Addition-chain exponentiation".
- Addition-chain_exponentiation sameAs m.03hp7p.
- Addition-chain_exponentiation sameAs Q4681307.
- Addition-chain_exponentiation sameAs Q4681307.
- Addition-chain_exponentiation sameAs Addition-chain_exponentiation.
- Addition-chain_exponentiation wasDerivedFrom Addition-chain_exponentiation?oldid=581190418.
- Addition-chain_exponentiation isPrimaryTopicOf Addition-chain_exponentiation.