Talk:Addition-chain exponentiation: Difference between revisions

From Rosetta Code
Content added Content deleted
(→‎Alternative "special objects" to using Matrices: But maybe a better "special object" (for the sake of this task) is available, any suggestions?)
 
Line 10: Line 10:


[[User:NevilleDNZ|NevilleDNZ]] 03:42, 27 August 2011 (UTC)
[[User:NevilleDNZ|NevilleDNZ]] 03:42, 27 August 2011 (UTC)

== Inefficient chain finding ==

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

Revision as of 04:32, 27 August 2011

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

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