Talk:Addition-chain exponentiation: Difference between revisions

: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. And usually heuristics only give suboptimal solutions. [[User:Arbautjc|Arbautjc]] ([[User talk:Arbautjc|talk]]) 09:30, 30 April 2015 (UTC)