Anonymous user
Talk:Addition-chain exponentiation: Difference between revisions
→Should this task be deleted?
Line 183:
:Many tasks are only suited to a few languages, it's the very purpose of having so many languages: if one could handle all tasks as well or better than any other, there would be no point in programming in any other language. We know it's not the case.
:Furthermore, this is an old problem, described in Knuth's TAOCP. I think it's still a good candidate for RC, but maybe it should be amended to use much lower exponents: in the 200-600 range, it should be reasonably fast.
:However, it should then still be clearly stated whether star chains are accepted or not: I don't think it's a good idea since the algorithm provides no guarantee that the result is optimal, it's only an observation made by comparing with the true optimal solution. This would encourage solving a problem with the wrong tool, just because it happens to give the right answer by chance (and it does not with 12509, as explained above). It's also possible to state explicitly that star chains are accepted because we know by other means that the answer is right in the asked cases (but then one has to choose exponents for which it is really known, of course, and give proper references).
:On the other hand, it would also be doable with the current exponents, but then the task should mention a reference to an efficient algorithm.
:For low exponents, I can give a backtracking algorithm relatively easy to adapt: in Frotran 77, thus only ''if'' and ''goto'' are really needed, and it can be translated to a recursive algorithm, hence most language families can do it.
:Another remark: I don't see much point in asking for matrix exponentiation since the core problem is in optimizing addition chains. That's adding a mostly trivial task, but which may require much code in some languages, for no benefit as there are already tasks about this.
:[[User:Arbautjc|Arbautjc]] ([[User talk:Arbautjc|talk]]) 08:15, 21 July 2015 (UTC)
| |||