Anonymous user
Talk:Addition-chain exponentiation: Difference between revisions
Talk:Addition-chain exponentiation (view source)
Revision as of 22:13, 29 August 2011
, 12 years ago→wikipedia content: Cannot call Wikipedia's template from here.
m (Make consistency among section headers.) |
m (→wikipedia content: Cannot call Wikipedia's template from here.) |
||
Line 63:
Given that the bulk of the task was copied wholesale from the wikipedia page, perhaps the following paragraph should be included as well?
: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 [[wp:NP-complete|NP-complete]].<ref><nowiki>{{Cite journal|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}}</nowiki></ref> 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.
<references/>
| |||