Anonymous user
Talk:Addition-chain exponentiation: Difference between revisions
→Associativity
Line 130:
==Associativity==
Exponentiation is the obvious application for addition chains, but shouldn't they work for any associative binary operation? I expect exponentiation will make the best application for a task requirement, but we might mention associativity in the description. —[[User:Sonia|Sonia]] 23:08, 13 February 2012 (UTC)
:Actually, except for low exponent, I doubt any software would use optimal solution, since it's really a pain to find the solutions. Also, there is a more general solution allowing inverse operations. It is interesting for multiplication (if addition and subtraction have roughly the same cost), but probably not for exponentiation, where multiplication/division are usually not expected to have the same cost. Hence for really optimal use, one would have to analyze carefully the costs of each variant. However, the task is still theoreyically interesting, and fidning a good algorithm for large exponents is not so easy. A backtracking program I wrote some time ago in Fortran 77 took almost 24 hours to compute optimal solutions for all exponents up to 2048, I don't think it's fast enough, by far. [[User:Arbautjc|Arbautjc]] ([[User talk:Arbautjc|talk]]) 09:30, 30 April 2015 (UTC)
==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)
| |||