Talk:Addition-chain exponentiation: Difference between revisions
Content added Content deleted
(→Inefficient chain finding: new section) |
(→Inefficient chain finding: reference lengths in case useful) |
||
Line 12: | Line 12: | ||
== Inefficient chain finding == |
== Inefficient chain finding == |
||
⚫ | |||
⚫ | |||
def expo(r = [0] + [100000] * maxn, s = (1,)): |
|||
⚫ | |||
l, f = len(s), s[0] |
|||
⚫ | |||
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] |
if n in l: return [l] |
||
Line 30: | Line 39: | ||
return r |
return r |
||
for i in range(20): print(i, chain(i)) |
for i in range(20): print(i, chain(i)) |
||
r = expo() |
|||
for i in range(maxn): print(i, r[i])</lang> |