Anonymous user
Talk:Addition-chain exponentiation: Difference between revisions
Talk:Addition-chain exponentiation (view source)
Revision as of 04:32, 27 August 2011
, 12 years ago→Inefficient chain finding: new section
(→Alternative "special objects" to using Matrices: But maybe a better "special object" (for the sake of this task) is available, any suggestions?) |
(→Inefficient chain finding: new section) |
||
Line 10:
[[User:NevilleDNZ|NevilleDNZ]] 03:42, 27 August 2011 (UTC)
== Inefficient chain finding ==
Optimal addition chain is NP-complete. In other words, don't use the following for big numbers where "big" is "larger than a few tens, probably 20".
<lang python>def chain(n, l=(1,)):
if n in l: return [l]
r = []
for i in l:
x = i + l[-1]
if x > n: continue
v = chain(n, l + (x,))
if not len(r) or len(r[0]) > len(v[0]):
r = v
elif len(r[0]) == len(v[0]):
r += v
return r
for i in range(20): print(i, chain(i))</lang>
| |||