Anonymous user
Talk:Addition-chain exponentiation: Difference between revisions
+article on a fast algorithm
m (→Associativity) |
(+article on a fast algorithm) |
||
Line 200:
::The task as it is right now is too complex for RC. However, addition chains are IMO perfectly fit to RC. Choose lower bounds and it's easily feasible. However, if you choose lower bounds, it is known that star chains are optimal (but it is known by comparison to an optimal algorithm, not by an independant proof, AFAIK). The lowest N for which they fail to be optimal is greater than 10000, far above what is reasonably feasible with a simple backtracking algorithm. Therefore, if lower bounds are chosen, you may as well give the possibility to use star chains. So far, I have not had much time to write a new task for this (I have never written a task on RC yet, by the way).
::[[User:Arbautjc|Arbautjc]] ([[User talk:Arbautjc|talk]]) 15:20, 17 August 2015 (UTC)
'''Update''' There is indeed a fast algorithm, much faster than the straightforward backtracking algorithm I used. See the following article:
Neill Michael Clift,
''"Calculating optimal addition chains"'',
'''Computing''', March 2011, Volume 91, Issue 3, pp 265–284,
[https://doi.org/10.1007/s00607-010-0118-8 DOI:10.1007/s00607-010-0118-8]
| |||