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)) 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 are used left to right).

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)