Talk:Addition-chain exponentiation: Difference between revisions
(→Alternative "special objects" to using Matrices: But maybe a better "special object" (for the sake of this task) is available, any suggestions?) |
(→Inefficient chain finding: new section) |
||
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>