Talk:Addition-chain exponentiation

Incorrect

Note that the table displayed on the task page is incorrect. Currently for the exponent for a↑15 it has: (d←(b←a×a)×b)×d×d×a.

But this means b←a↑2 and d←a↑4 and the result calculated is a↑13 --Rdm 15:04, 27 August 2011 (UTC)

I think it should be: d×d×(d←a×b×(b←a×a)) or b×d×(d←b×(b←a×a×a)) but my preferred notation (where the operations are strictly right to left) conflicts with the format used in the table (where assignment is right to left but assignments get used left to right). --Rdm 15:16, 27 August 2011 (UTC)

Fixed. ThanX NevilleDNZ 05:39, 28 August 2011 (UTC)

Alternative "special objects" to using Matrices

I'm thinking that with matrices minimising multiplications is important, the other fields where this could be important (e.g. arbitrary length modulo arithmetic in cryptography) are rather abstract.

Note: I'd be pleased to allow arbitrary length modulo arithmetic (for cryptography) as an optional alternative to matrices.

Real and complex variables could be used, but in reality these can be done via calls to log and exp functions and to not provide any interesting test cases.

But maybe there is a better "special object" (for the sake of this task) is available, any suggestions?

NevilleDNZ 03:42, 27 August 2011 (UTC)

Maybe just drop the matrix part altogether? Finding shortest chains is enough of a problem in itself, plus it's not like we need even more matrix related tasks on RC. --Ledrug 05:05, 27 August 2011 (UTC)

I didn't immediately see this task as a finding the shortest chain kind of exercise. Basically I was looking at it from a practical point of view. In that here is a real problem, and have is a real application and/or test case. Hence a reason to solve it. Without a real problem, and a real test case the task would look naked.

Also it means that the test case can be described in the "present tense", rather then as an abstraction.

Having said all that... I also am nervous about the matrix manipulation as I think it is enough to scare off the majority of contributors. And (you are right) it isn't core to the task. Maybe the matrix exponentiation could be relegated to a Kudos as it is an important application of any such algorithm.

Maybe someone could reword the task as I am at a bit of a loss on exactly an alternative way of describing it.

BTW this problem is a nice (and at the same time nasty) little puzzle to work on.... ¢ Who needs Sudoku when you have rosettacode.org? Yay! Rack your brains, but possibly produce something beautiful & useful at the end. ¢

NevilleDNZ 06:11, 27 August 2011 (UTC)

A little puzzle is quite an understatement -- the task asks for the optimal chain of a 9 digit number, for which I don't know if there is a practical method (even though its factorization is known, it might not help: see 77 and 154). Secondly, matrix-related tasks show up a lot on RC, which is both tedious to do and difficult to do right. It also has another problem: binary expo requires fixed amount of storage for temp matrix result (the current square), while an optimal chain may require variable temp storage (chain for 9 requires saving result 3 or 4 for future use depending on the chain taken) which can be a pain for languages without GC. I think it's sufficient to just mention where addition chains can be useful, while the task only needs to implement the part of finding the chains for a given number. --Ledrug 06:34, 27 August 2011 (UTC)

OK. I will drop the use of matrices, I also find using libraries a pain as often the libraries are language release specific. As an alternative test case we can use the languages built in complex numbers type, and the test cases:

• 1.0000254989+0.0000577896i³¹⁴¹⁵ = 2
• 1.0000220632+0.0000500026i²⁷¹⁸² = 2.

And then only the chains for 31415 and 27182 are required.

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. —Sonia 23:08, 13 February 2012 (UTC)

Inefficient chain finding

As a reference to optimal chain length. Optimal addition chain is NP-complete. In other words, don't use the following for big numbers where "big" is "larger than a few tens, probably 20". <lang python>cache = {0: 0} def chain(maxn, r = (1,)): n, l = r[0], len(r) - 1 if n <= maxn and (not n in cache or l <= cache[n]): cache[n] = l for i in r: chain(maxn, (n + i,) + r)

xx = 200 chain(xx) for i in range(xx + 1): print(i, cache[i])</lang>--Ledrug 09:08, 27 August 2011 (UTC)

wikipedia content

Given that the bulk of the task was copied wholesale from the wikipedia page, perhaps the following paragraph should be included as well?

On the other hand, the addition-chain method is much more complicated, since the determination of a shortest addition chain seems quite difficult: no efficient optimal methods are currently known for arbitrary exponents, and the related problem of finding a shortest addition chain for a given set of exponents has been proven NP-complete. Even given a shortest chain, addition-chain exponentiation requires more memory than the binary method, because it must potentially store many previous exponents from the chain simultaneously. In practice, therefore, shortest addition-chain exponentiation is primarily used for small fixed exponents for which a shortest chain can be precomputed and is not too large.

And the following two paragraphs at wikipedia also look relevant.

--Rdm 14:51, 27 August 2011 (UTC)

This appears to be a really hard problem. Most relevant page on the web so far: [[1]], and in particular the paper [[2]]. I have doubts on the possibility of anyone implementing it on RC. --Ledrug 15:59, 27 August 2011 (UTC)

From the search tool on the page linked above:<lang>1 2 4 5 10 20 40 80 160 320 321 641 1282 1923 3846 7692 15384 15705 31410 31415

1 2 3 5 10 20 23 43 53 106 212 424 848 1696 3392 6784 13568 13591 27182</lang>

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. --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. --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. —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

  addch 33

D*D*D =:A*B*C*C=:B*B=:A*A</lang> It would be interesting to see the optimal solution for an exponent of 23 -- that's the first case where mine fails, and is the first prime exponent where binary chain is inadequate. --Rdm 17:06, 27 August 2011 (UTC)

<lang python>cache = [[(0,)], [(1,)]]

def chain(n): if len(cache) >= n + 1: return cache[n] v = [] for m in range((n + 1)//2, n): for r in chain(m): if len(v) and len(r) >= len(v[0]): break if not n - r[0] in r: continue

rr = (n,) + r if not len(v) or len(v[0]) > len(rr): v = [rr] elif len(v[0]) == len(rr): v.append(rr) cache.append(v) return v

print chain(23)</lang>--Ledrug 19:36, 27 August 2011 (UTC)

How does your notation work? In L*M*M=:L*L =:G*I*J*K*K*K=:J*J=:I*I=:H*H=:G*G =:A*B*C*F*F*F=:E*E=:D*D=:C*C=:B*B=:A*A, what does G=:A*B*C*... even mean? --Ledrug 20:09, 27 August 2011 (UTC)

=: is an assignment operation in J, and precedence is the same for multiplication and assignment, with long right scope. So that expression is equivalent to L*(M*(M=(L*(L=(G*(I*(J*(K*(K*(K=(J*(J=(I*(I=(H*(H=(G*(G=(A*(B*(C*(F*(F*(F=(E*(E=(D*(D=(C*(C=(B*(B=(A*A))))))))))))))))))))))))))))))))) in C-like languages. --Rdm 20:48, 27 August 2011 (UTC)

btw, I get an error from your python program: <lang python> File "<stdin>", line 17

   print chain(23)</lang> but I should have a chance to sit down and work out something soon.  --Rdm 20:52, 27 August 2011 (UTC)

Never seen that error before. Blame windows. Anyway, output is<lang>[(23, 13, 10, 5, 3, 2, 1), (23, 14, 9, 5, 4, 2, 1),

(23, 18, 9, 5, 4, 2, 1), (23, 20, 10, 5, 3, 2, 1)]</lang> --Ledrug 21:11, 27 August 2011 (UTC)

Ok... looking at the prime numbers less than 100 where my approach was inadequate (which was just binary chain for prime numbers), I can see a rapidly increasing problem: <lang j>23 6 4

31 7 42 43 7 4 47 8 63 59 8 24 61 8 72 79 9 185 83 8 4</lang> First column is the prime number, second column is sequence length, third column is the number of possibilities to compute that exponent in minimal length based on a minimal length chain. I just do not see any good way of managing the complexity of this system. --Rdm 22:43, 27 August 2011 (UTC)

I'm not sure why you think prime numbers are more troublesome than composites: if you are doing factorization, your method is doomed. Check the output for 77, none of the sequences contains either 7 or 11. --Ledrug 23:27, 27 August 2011 (UTC)

Yes, 33 was enough to show that factorization can be worse than addition chain (length binary chain for 3 + 1 + length binary chain 11 is longer than binary chain for 33). --Rdm 02:32, 28 August 2011 (UTC)

Knuth's programs: [[3]] and [[4]]. Pretty fast, but doesn't explain the algorithm very well, maybe because the algorithm only appears complicated to mere mortals. --Ledrug 20:59, 31 August 2011 (UTC)

in achain4 he asks people to first read achain2 and in achain2 he asks people to first read achain1 and in achain1 he asks people to first read 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). --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. —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. —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. —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. —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. —Sonia 23:08, 13 February 2012 (UTC)

Montgomery reduction

I just tried a fun experiment of combining this task with the Montgomery reduction task and it worked just fine. It's not that much of a stretch since Montgomery reduction is just another way to do multiplication, but still it was fun to see addition chain exponentiation work with this alternative operation and also see it work on some bigger numbers. The 100 bit exponents of my example there take about 150 multiplies using binary exponentiation but about 130 multiplies with the addition chains. —Sonia 01:59, 2 March 2012 (UTC)