Anonymous user
Talk:Addition-chain exponentiation: Difference between revisions
→Optimal solution, A003313, and κῦδος
Line 134:
==Optimal solution, A003313, and κῦδος==
Any technique that guarantees optimal solutions produces A003313 so if the task allows only optimal solutions, then 1) the task requires an expensive computation, and 2) κῦδος are cheap for any valid solution. I would like to see the task allow solutions that are not guaranteed to be optimal but which generally improve on binary solutions. This is arguing for the practical result of accelerating a computation as opposed to the mathematical result of finding a limit. The rich literature out there seems mostly focused on the practical application of finding near-optimal solutions (for the purpose of accelerating RSA encryption.) κῦδος could still go to the mathematical result of A003313, but it could be made more challenging by requiring later terms of the sequence. Terms 8190-8195, for example, which are verifiable from a link from the OEIS page. Actually I'd like to see κῦδος awarded for reproducing those terms using a near-optimal technique. —[[User:Sonia|Sonia]] 23:08, 13 February 2012 (UTC)
:It's another task then. I don't think it's a problem to ask for optimal solutions. Actually, it's even very interesting: among the 5 solutions so far, 4 are wrong. A good task to separate those who can read a question from those who can't. I didn't check the C one carefully though: it's certainly wrong in the sense that it does not compute matrix exponentiation, but this is really irrelevant, the interesting part is the computation of ''optimal'' addition chains. [[User:Arbautjc|Arbautjc]] ([[User talk:Arbautjc|talk]]) 17:19, 19 July 2015 (UTC)
== Montgomery reduction ==
| |||