Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Addition-subtraction_chain> ?p ?o. }
Showing items 1 to 24 of
24
with 100 items per page.
- Addition-subtraction_chain abstract "An addition-subtraction chain, a generalization of addition chains to include subtraction, is a sequence a0, a1, a2, a3, ... that satisfiesAn addition-subtraction chain for n, of length L, is an addition-subtraction chain such that . That is, one can thereby compute n by L additions and/or subtractions. (Note that n need not be positive. In this case, one may also include a-1=0 in the sequence, so that n=-1 can be obtained by a chain of length 1.)By definition, every addition chain is also an addition-subtraction chain, but not vice-versa. Therefore, the length of the shortest addition-subtraction chain for n is bounded above by the length of the shortest addition chain for n. In general, however, the determination of a minimal addition-subtraction chain (like the problem of determining a minimum addition chain) is a difficult problem for which no efficient algorithms are currently known. The related problem of finding an optimal addition sequence is NP-complete (Downey et al., 1981), but it is not known for certain whether finding optimal addition or addition-subtraction chains is NP-hard.For example, one addition-subtraction chain is: , , , . This is not a minimal addition-subtraction chain for n=3, however, because we could instead have chosen . The smallest n for which an addition-subtraction chain is shorter than the minimal addition chain is n=31, which can be computed in only 6 additions (rather than 7 for the minimal addition chain):Like an addition chain, an addition-subtraction chain can be used for addition-chain exponentiation: given the addition-subtraction chain of length L for n, the power can be computed by multiplying or dividing by x L times, where the subtractions correspond to divisions. This is potentially efficient in problems where division is an inexpensive operation, most notably for exponentiation on elliptic curves where division corresponds to a mere sign change (as proposed by Morain and Olivos, 1990).Some hardware multipliers multiply by n using an addition chain described by n in binary: n = 31 = 0 0 0 1 1 1 1 1 (binary).Other hardware multipliers multiply by n using an addition-subtraction chain described by n in Booth encoding: n = 31 = 0 0 1 0 0 0 0 -1 (Booth encoding).".
- Addition-subtraction_chain wikiPageExternalLink ch4.ps.
- Addition-subtraction_chain wikiPageID "11042759".
- Addition-subtraction_chain wikiPageRevisionID "482748925".
- Addition-subtraction_chain hasPhotoCollection Addition-subtraction_chain.
- Addition-subtraction_chain subject Category:Addition_chains.
- Addition-subtraction_chain type Abstraction100002137.
- Addition-subtraction_chain type AdditionChains.
- Addition-subtraction_chain type Company108058098.
- Addition-subtraction_chain type Group100031264.
- Addition-subtraction_chain type Institution108053576.
- Addition-subtraction_chain type Organization108008335.
- Addition-subtraction_chain type SocialGroup107950920.
- Addition-subtraction_chain type YagoLegalActor.
- Addition-subtraction_chain type YagoLegalActorGeo.
- Addition-subtraction_chain type YagoPermanentlyLocatedEntity.
- Addition-subtraction_chain comment "An addition-subtraction chain, a generalization of addition chains to include subtraction, is a sequence a0, a1, a2, a3, ... that satisfiesAn addition-subtraction chain for n, of length L, is an addition-subtraction chain such that . That is, one can thereby compute n by L additions and/or subtractions. (Note that n need not be positive.".
- Addition-subtraction_chain label "Addition-subtraction chain".
- Addition-subtraction_chain sameAs m.02qz160.
- Addition-subtraction_chain sameAs Q4681308.
- Addition-subtraction_chain sameAs Q4681308.
- Addition-subtraction_chain sameAs Addition-subtraction_chain.
- Addition-subtraction_chain wasDerivedFrom Addition-subtraction_chain?oldid=482748925.
- Addition-subtraction_chain isPrimaryTopicOf Addition-subtraction_chain.