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)

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)

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)

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)