Talk:Addition-chain exponentiation: Difference between revisions
Talk:Addition-chain exponentiation (view source)
Revision as of 23:09, 13 February 2012
, 12 years agolots of thoughts after implementing a solution
(lots of thoughts after implementing a solution) |
|||
Line 44:
[[User:NevilleDNZ|NevilleDNZ]] 08:09, 27 August 2011 (UTC)
::I'd like to vote up modular exponentiation of integers. Poking around on the internet, there is lots of great research out there on addition chains and it seems to be largely motivated by RSA encryption. Exponentiation of matrices and complex numbers are fine, but as applications for addition chains I don't see them as any more compelling that exponentiation of simple floating point numbers. If we wanted to avoid big integers we could pick 16 bit numbers and still have an interesting example. —[[User:Sonia|Sonia]] 23:08, 13 February 2012 (UTC)
== Inefficient chain finding ==
Line 76 ⟶ 78:
::Computing optimal addition chains for a sequence of multiplications is harder than for a single multiplication. I believe I have an implementation for the simple case asked for here. --[[User:Rdm|Rdm]] 16:39, 27 August 2011 (UTC)
::That said, the requested matrix multiplications look to be producing ridiculously large results. When I tried using floating point, I got a result full of negative and positive infinities. So computing the result will require extended precision numbers and I expect the result will be quite verbose. --[[User:Rdm|Rdm]] 16:44, 27 August 2011 (UTC)
::::I got that at first too, but I had a typo. When I fixed it, my results agreed with those of the posted MATLAB solution. A^24 is an identity matrix, by the way, so A^31415 = A^23 and A^21718 = A^14. —[[User:Sonia|Sonia]] 23:08, 13 February 2012 (UTC)
:::Oh well, turns out that my approach is non-optimal in some cases. When I compare the first 100 exponents (1..100) with the A003313 values listed in the task description, I am using one multiplication too many for these cases: 23 31 33 43 46 47 49 59 61 62 65 66 69 77 79 83 86 92 93 94 98 99. Here are two of my cases where I should be doing better: <lang j> addch 31
A*B*C*D*D*D=:C*C=:B*B=:A*A
Line 117 ⟶ 120:
Knuth's programs: [[http://www-cs-faculty.stanford.edu/~knuth/programs/achain4.w]] and [[http://www-cs-faculty.stanford.edu/~knuth/programs/achain-all.w]]. Pretty fast, but doesn't explain the algorithm very well, maybe because the algorithm only appears complicated to mere mortals. --[[User:Ledrug|Ledrug]] 20:59, 31 August 2011 (UTC)
:in [http://www-cs-faculty.stanford.edu/~knuth/programs/achain4.w achain4] he asks people to first read [http://www-cs-faculty.stanford.edu/~knuth/programs/achain2.w achain2] and in achain2 he asks people to first read [http://www-cs-faculty.stanford.edu/~knuth/programs/achain1.w achain1] and in achain1 he asks people to first read [http://www-cs-faculty.stanford.edu/~knuth/programs/achain0.w achain0]. And these make frequent reference to Theorem 4.6.3C (which apparently is on page 469 of his Art of Computer Programming -- which I do not have access to right now). --[[User:Rdm|Rdm]] 21:29, 31 August 2011 (UTC)
==MATLAB non-solution==
An assumption that a language solves the task is not a solution to the task. —[[User:Sonia|Sonia]] 23:08, 13 February 2012 (UTC)
==Display count==
+1 for this requirement. Of course the number of multiplications is determined by the length of the chain, but it's a fun and simple little demonstration to actually count the multiplications that happen rather than report the number that should be required. —[[User:Sonia|Sonia]] 23:08, 13 February 2012 (UTC)
==Show chain==
The chains themselves are so interesting! It's interesting that a number can have different chains of the same length. I think we should add a requirement to show the chains. —[[User:Sonia|Sonia]] 23:08, 13 February 2012 (UTC)
==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)
==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)
| |||