Talk:Addition-chain exponentiation

Alternative "special objects" to using Matrices

I'm thinking that with matrices minimising multiplications is important, the other fields where this could be important (e.g. arbitrary length modulo arithmetic in cryptography) are rather abstract.

Note: I'd be pleased to allow arbitrary length modulo arithmetic (for cryptography) as an optional alternative to matrices.

Real and complex variables could be used, but in reality these can be done via calls to log and exp functions and to not provide any interesting test cases.

But maybe there is a better "special object" (for the sake of this task) is available, any suggestions?

NevilleDNZ 03:42, 27 August 2011 (UTC)

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". <lang python>maxn = 200

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]

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))

r = expo() for i in range(maxn): print(i, r[i])</lang>