HTML Microdata document

This HTML5 document contains 65 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

Prefix	IRI
dcterms	http://purl.org/dc/terms/
yago-res	http://yago-knowledge.org/resource/
dbo	http://dbpedia.org/ontology/
foaf	http://xmlns.com/foaf/0.1/
n18	https://global.dbpedia.org/id/
yago	http://dbpedia.org/class/yago/
dbt	http://dbpedia.org/resource/Template:
rdfs	http://www.w3.org/2000/01/rdf-schema#
freebase	http://rdf.freebase.com/ns/
rdf	http://www.w3.org/1999/02/22-rdf-syntax-ns#
owl	http://www.w3.org/2002/07/owl#
wikipedia-en	http://en.wikipedia.org/wiki/
prov	http://www.w3.org/ns/prov#
dbc	http://dbpedia.org/resource/Category:
dbp	http://dbpedia.org/property/
xsdh	http://www.w3.org/2001/XMLSchema#
wikidata	http://www.wikidata.org/entity/
dbr	http://dbpedia.org/resource/
n8	https://cr.yp.to/papers/

Statements

Subject Item: dbr:List_of_algorithms
dbo:wikiPageWikiLink: dbr:Addition-chain_exponentiation

Subject Item: dbr:List_of_numerical_analysis_topics
dbo:wikiPageWikiLink: dbr:Addition-chain_exponentiation

Subject Item: dbr:Vectorial_addition_chain
dbo:wikiPageWikiLink: dbr:Addition-chain_exponentiation

Subject Item: dbr:Optimal_substructure
dbo:wikiPageWikiLink: dbr:Addition-chain_exponentiation

Subject Item: dbr:Addition-chain_exponentiation
rdf:type: yago:Activity100407535 yago:Algorithm105847438 yago:WikicatComputerArithmeticAlgorithms yago:Rule105846932 yago:Relation100031921 yago:YagoPermanentlyLocatedEntity yago:Event100029378 yago:MathematicalRelation113783581 yago:Function113783816 yago:Procedure101023820 yago:Exponential113789462 yago:Act100030358 yago:WikicatExponentials yago:PsychologicalFeature100023100 yago:Abstraction100002137
rdfs:label: Addition-chain exponentiation
rdfs:comment: In mathematics and computer science, optimal addition-chain exponentiation is a method of exponentiation by a positive integer power that requires a minimal number of multiplications. Using the form of the shortest addition chain, with multiplication instead of addition, computes the desired exponent (instead of multiple) of the base. (This corresponds to OEIS sequence A003313 (Length of shortest addition chain for n).) 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).
dcterms:subject: dbc:Computer_arithmetic_algorithms dbc:Addition_chains dbc:Exponentials
dbo:wikiPageID: 856356
dbo:wikiPageRevisionID: 1111586064
dbo:wikiPageWikiLink: dbc:Exponentials dbr:Integer dbr:Mathematics dbr:Dynamic_programming dbr:Binary_exponentiation dbr:NP-complete dbr:Optimal_substructure dbr:Computer_science dbr:Elliptic_curve dbr:Algorithm dbr:Addition-subtraction_chain dbr:Exponentiation dbr:Addition_chain dbc:Addition_chains dbr:Base_(exponentiation) dbc:Computer_arithmetic_algorithms dbr:Donald_E._Knuth dbr:Negative_number
dbo:wikiPageExternalLink: n8:pippenger.pdf
owl:sameAs: freebase:m.03hp7p wikidata:Q4681307 yago-res:Addition-chain_exponentiation n18:4LbHi
dbp:wikiPageUsesTemplate: dbt:Reflist dbt:OEIS_el
dbo:abstract: In mathematics and computer science, optimal addition-chain exponentiation is a method of exponentiation by a positive integer power that requires a minimal number of multiplications. Using the form of the shortest addition chain, with multiplication instead of addition, computes the desired exponent (instead of multiple) of the base. (This corresponds to OEIS sequence A003313 (Length of shortest addition chain for n).) 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 multiplications but the shortest addition chain requires only five: (binary, 6 multiplications) (shortest addition chain, 5 multiplications). (also shortest addition chain, 5 multiplications). On the other hand, the determination of a shortest addition chain is hard: 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. So in practice, shortest addition-chain exponentiation is primarily used for small fixed exponents for which a shortest chain can be pre-computed and is not too large. There are also several methods to approximate a shortest addition chain, and which often require fewer multiplications than binary exponentiation; 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). 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).
prov:wasDerivedFrom: wikipedia-en:Addition-chain_exponentiation?oldid=1111586064&ns=0
dbo:wikiPageLength: 6465
foaf:isPrimaryTopicOf: wikipedia-en:Addition-chain_exponentiation

Subject Item: dbr:Addition-subtraction_chain
dbo:wikiPageWikiLink: dbr:Addition-chain_exponentiation

Subject Item: dbr:Addition_chain
dbo:wikiPageWikiLink: dbr:Addition-chain_exponentiation

Subject Item: dbr:Exponentiation
dbo:wikiPageWikiLink: dbr:Addition-chain_exponentiation

Subject Item: dbr:Exponentiation_by_squaring
dbo:wikiPageWikiLink: dbr:Addition-chain_exponentiation

Subject Item: dbr:Lucas_primality_test
dbo:wikiPageWikiLink: dbr:Addition-chain_exponentiation

Subject Item: dbr:The_Art_of_Computer_Programming
dbo:wikiPageWikiLink: dbr:Addition-chain_exponentiation

Subject Item: dbr:Schmidt-Samoa_cryptosystem
dbo:wikiPageWikiLink: dbr:Addition-chain_exponentiation

Subject Item: dbr:Addition_chain_exponentiation
dbo:wikiPageWikiLink: dbr:Addition-chain_exponentiation
dbo:wikiPageRedirects: dbr:Addition-chain_exponentiation

Subject Item: wikipedia-en:Addition-chain_exponentiation
foaf:primaryTopic: dbr:Addition-chain_exponentiation