Talk:Addition-chain exponentiation: Difference between revisions
Content added Content deleted
m (→Inefficient chain finding: oops) |
(→wikipedia content: new section) |
||
| Line 48: | Line 48: | ||
for i in range(xx + 1): |
for i in range(xx + 1): |
||
print(i, cache[i])</lang>--[[User:Ledrug|Ledrug]] 09:08, 27 August 2011 (UTC) |
print(i, cache[i])</lang>--[[User:Ledrug|Ledrug]] 09:08, 27 August 2011 (UTC) |
||
== wikipedia content == |
|||
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. |
|||
--[[User:Rdm|Rdm]] 14:51, 27 August 2011 (UTC) |
|||