Calculate constant using minimum number of operations on single digit constants

Question

I have a machine that supports the arithmetic operations plus, minus (unary and binary), multiply, divide and exponent and can load single digit integer constants. Arithmetic operations are performed using floating-point, e.g., 3/2 returns 1.5.

Given an integer constant, X, is there an efficient algorithm that will return an expression containing the minimum number of operators needed to calculate this value?

For instance, the constant 123 can be calculated using three operators as (2+9)^2+2, but there is a two operator solution 5^3-2.

I have a blog post providing more background and some numbers.

Answer 1

Of course there is such an algorithm. There is certainly an algorithm using fewer than $X$ operators to calculate $X$ by just doing $1+1+\cdots+1$, so an algorithm could look at all the finitely many expressions using fewer than $X$ operators and pick out one using the fewest operators.

So perhaps what you are really asking is what's the most efficient algorithm for accomplishing the goal, and how efficient is it as a function of $X$. That's likely to be a very hard question. There are unsolved questions about something as simple as "addition chains" (look it up!). There are unsolved questions about how close together exact powers can be. You are asking something far more complicated than either of these problems.

Answer 2

You can trivially bound the number by $2\log_2 n$ operations: just use binary number representation and Horner's method. On the other hand, you for some of the inputs you can't do better, i.e. you have to get at least $\Omega(\log_2 n)$ steps, otherwise you won't be able to represent all the numbers. I have no idea if you can do better that something that resembles Dijkstra's algorithm, and the graph will be huge (in each step you can possibly get $5K^2$ new numbers where $K$ is the previous number count).

$$ K_1 = \mathrm{O}(1), K_{k+1} = \mathrm{O}(K_{k}^2), K_k = O(K_1^{(2^k)})$$ $$ K_{log_2 n} = \mathrm{O}(K_1^n) $$

So this would be like 2-EXP-TIME algorithm (remember the input size is $\log n$). It would be much easier if you wouldn't have division or subtraction, then as the number can only go up, you can disregard anything greater than $n$ (and you could do EXP-TIME by dynamic programming and method similar to change-making algorithm, but right now I don't know if it can or can't be better).