Anonymous user
Talk:Addition-chain exponentiation: Difference between revisions
Talk:Addition-chain exponentiation (view source)
Revision as of 19:36, 27 August 2011
, 12 years ago→wikipedia content
Line 76:
addch 33
D*D*D =:A*B*C*C=:B*B=:A*A</lang> It would be interesting to see the optimal solution for an exponent of 23 -- that's the first case where mine fails, and is the first prime exponent where binary chain is inadequate. --[[User:Rdm|Rdm]] 17:06, 27 August 2011 (UTC)
::::<lang python>cache = [[(0,)], [(1,)]]
def chain(n):
if len(cache) >= n + 1: return cache[n]
v = []
for m in range((n + 1)//2, n):
for r in chain(m):
if len(v) and len(r) >= len(v[0]): break
if not n - r[0] in r: continue
rr = (n,) + r
if not len(v) or len(v[0]) > len(rr):
v = [rr]
elif len(v[0]) == len(rr):
v.append(rr)
cache.append(v)
return v
print chain(23)</lang>--[[User:Ledrug|Ledrug]] 19:36, 27 August 2011 (UTC)
| |||