Minimal addition-chain exponentiation

Question

I know it has been proven NP-complete, and that's ok. I'm currently solving it with branch and bound where I set the initial upper limit at the number of multiplications it would take the normal binary square/multiply algorithm, and it does give the right answers, but I'm not satisfied with the running time (it can take several seconds for numbers around 200). This being an NP-complete problem, I'm not expecting anything spectacular; but there are often tricks to get the Actual Time under control somewhat.

Are there faster ways to do this in practice? If so, what are they?

Estrogen

Answer 1

This looks like section 4.6.3 "Evaluation of Powers" in Knuth Vol 2 Seminumerical Algorithms. This goes into considerable detail to give various approaches, which look much quicker than branch and bound but do not all provide the absolutely best solution.

Knuth states in the discussion after Theorem F that he uses backtrack search to prove that l(191) = 11, so I doubt if you will find a short-cut answer for this. He defers explanation of the backtrack search to section 7.2.2, which is I think still unpublished, although there are traces of work on this at http://www-cs-faculty.stanford.edu/~uno/programs.html.

Tani

Thanks, at the very least I'll be able to set a better initial bound with these - waiting for chapter 7 now – Estrogen

Answer 2

Metaheuristics algorithms will scale far better. They include Tabu search, Genetic algorithms, Simulated Annealing, ...

There's a couple of free books and free software out there.

Orvie

I'm not sure if the OP is willing to give up the exact best solution in exchange for better speed. At least he didn't say it explicitely in his question. – Coleslaw

I didn't say so explicitly, but it has to be actually minimal, not some local minimum. So I'm really just looking for an other exponential time algorithm that performs better for this problem in terms of real life time. – Estrogen

Answer 3

I'm late to the party but in Handbook of Elliptic and Hyperelliptic Curve Cryptography there is a chapter "9.2 Fixed exponent" which also discusses various kinds addition chains.

Pak