Anonymous user
Talk:Addition-chain exponentiation: Difference between revisions
Talk:Addition-chain exponentiation (view source)
Revision as of 04:39, 27 August 2011
, 12 years ago→Inefficient chain finding: reference lengths in case useful
(→Inefficient chain finding: new section) |
(→Inefficient chain finding: reference lengths in case useful) |
||
Line 12:
== Inefficient chain finding ==
As a reference to optimal chain length. 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".▼
def expo(r = [0] + [100000] * maxn, s = (1,)):
▲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".
l, f = len(s), s[0]
▲<lang python>def chain(n, l=(1,)):
if f < len(r) and l - 1 <= r[f]:
r[f] = l - 1
for i in s:
expo(r, (f + i,) + s)
return r
def chain(n, l=(1,)):
if n in l: return [l]
Line 30 ⟶ 39:
return r
for i in range(20): print(i, chain(i))
r = expo()
for i in range(maxn): print(i, r[i])</lang>
| |||