Talk:Addition-chain exponentiation: Difference between revisions
Content added Content deleted
m (Make consistency among section headers.) |
m (→wikipedia content: Cannot call Wikipedia's template from here.) |
||
| Line 63: | 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? |
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>{{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}}</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. |
: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/> |
<references/> |
||