How can you compute a shortest addition chain for an arbitrary n <= 600 within one second?

Question

How can you compute a shortest addition chain (sac) for an arbitrary n <= 600 within one second?

Notes

This is the programming competition on codility for this month.

Addition chains are numerically very important, since they are the most economical way to compute x^n (by consecutive multiplications).

Knuth's Art of Computer Programming, Volume 2, Seminumerical Algorithms has a nice introduction to addition chains and some interesting properties, but I didn't find anything that enabled me to fulfill the strict performance requirements.

What I've tried (spoiler alert)

Firstly, I constructed a (highly branching) tree (with the start 1-> 2 -> ( 3 -> ..., 4 -> ...)) such that for each node n, the path from the root to n is a sac for n. But for values >400, the runtime is about the same as for making a coffee.

Then I used that program to find some useful properties for reducing the search space. With that, I'm able to build all solutions up to 600 while making a coffee. But for n, I need to compute all solutions up to n. Unfortunately, codility measures the class initialization's runtime, too...

Since the problem is probably NP-hard, I ended up hard-coding a lookup table. But since codility asked to construct the sac, I don't know if they had a lookup table in mind, so I feel dirty and like a cheater. Hence this question.

Update

If you think a hard-coded, full lookup table is the way to go, can you give an argument why you think a full computation/partly computed solutions/heuristics won't work?

Answer 1

I have just got my Golden Certificate for this problem. I will not provide a full solution because the problem is still available on the site.I will instead give you some hints:

1. You might consider doing a deep-first search.
2. There exists a minimal star-chain for each n < 12509
3. You need to know how prune your search space.
4. You need a good lower bound for the length of the chain you are looking for.
5. Remember that you need just one solution, not all.

Good luck.

Answer 2

Addition chains are numerically very important, since they are the most economical way to compute x^n (by consecutive multiplications).

This is not true. They are not always the most economical way to compute x^n. Graham et. all proved that:

If each step in addition chain is assigned a cost equal to the product of the numbers at that step, "binary" addition chains are shown to minimize the cost.

Situation changes dramatically when we compute x^n (mod m), which is a common case, for example in cryptography.

Now, to answer your question. Apart from hard-coding a table with answers, you could try a Brauer chain.

A Brauer chain (aka star-chain) is an addition chain where each new element is formed as the sum of the previous element and some element (possibly the same). Brauer chain is a sac for n < 12509. Quoting Daniel. J. Bernstein:

Brauer's algorithm is often called "the left-to-right 2^k-ary method", or simply "2^k-ary method". It is extremely popular. It is easy to implement; constructing the chain for n is a simple matter of inspecting the bits of n. It does not require much storage.

BTW. Does anybody know a decent C/C++ implementation of Brauer's chain computation? I'm working partially on a comparison of exponentiation times using binary and Brauer's chains for both cases: x^n and x^n (mod m).