Talk:Addition-chain exponentiation: Difference between revisions

← Older edit

Talk:Addition-chain exponentiation (view source)

Revision as of 21:27, 16 December 2017

4,974 bytes added , 6 years ago

→‎Should this task be deleted?

Eoraptor

1,336

edits

Revision as of 06:58, 21 July 2015 (view source) rosettacode>Paddy3118 (→‎Should this task be deleted?: +1 with reasons.) ← Older edit		Latest revision as of 21:27, 16 December 2017 (view source) Eoraptor (talk \| contribs) (→‎Should this task be deleted?)
(14 intermediate revisions by 4 users not shown)
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~~theoretically interesting, and ~~fidning~~finding 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) ==Optimal solution, A003313, and κῦδος== Line 181: RC is about comparing languages not about original research in a proven difficult area. In the life of this task we have only a few examples and more comment on their correctness. I too think that the task is not written for an RC audience. It could be improved/saved if a particular algorithm or set of algorithms are approved in the task description and pseudo code given otherwise the task is too broad and contentious. <br> --[[User:Paddy3118\|Paddy3118]] ([[User talk:Paddy3118\|talk]]) 06:58, 21 July 2015 (UTC) :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 is already a task about this: [[Matrix-exponentiation operator]]. :[[User:Arbautjc\|Arbautjc]] ([[User talk:Arbautjc\|talk]]) 08:15, 21 July 2015 (UTC) ::Hi Arbautjc, if you see a way to tackle: ::# Giving an algorithm (in an accessible manner). ::# Excessive run times. ::# Matrices? (Possibly remove)? ::Then you could probably turn around the task and get more examples I think. --[[User:Paddy3118\|Paddy3118]] ([[User talk:Paddy3118\|talk]]) 09:22, 21 July 2015 (UTC) :Should this task be deleted? As it is, I would say yes. It has many problems. It's current advocate, Arbautjc, feels optimal solutions should be required yet there no implementations of optimal chain algorithms (#include is not an implemenation) and people have cited reasons why optimal chain algorithms are not likely to be a good fit for RC. —[[User:Sonia\|Sonia]] ([[User talk:Sonia\|talk]]) 02:09, 10 August 2015 (UTC) ::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) As is, this page should be deleted. It is an exercise of the mind until shown that it has significance in daily computing. In general, one should be able to find existing open source code as a working example that passes a test, such as from Perl's cpan for example. If this page is to be kept, the esoteric math symbols and terms should be translated. [[User:tekbasse] ([[User talk:tekbasse\|talk]]) 5:46, 1 March 2017 (UTC) :Ridiculous. Is there a rule requiring that Rosetta Code tasks be useful in daily computing? Of course not. Esoteric math symbols? Maybe you think computer science has nothing to do with math. But this is also blatantly wrong. This problem has been the subject of several research articles, and good algorithms exist, period. That you may be unable to implement them is nobody's concern. There are other more or less difficult algorithms on RC, and I have no problem with that. RC is not limited to "Hello World" and "How do I write a for loop?", thankfully. [[User:Eoraptor\|Eoraptor]] ([[User talk:Eoraptor\|talk]]) 21:27, 16 December 2017 (UTC) == Fast algorithm == 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] [[User:Arbautjc\|Arbautjc]] ([[User talk:Arbautjc\|talk]]) 11:45, 29 August 2016 (UTC)