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)

Maybe just drop the matrix part altogether? Finding shortest chains is enough of a problem in itself, plus it's not like we need even more matrix related tasks on RC. --Ledrug 05:05, 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>