Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Disclaimer: I have no idea what I'm talking about. Would that be related to Kolmogorov complexity? –  user2468 Mar 31 '12 at 3:41

2 Answers 2

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.

share|improve this answer
    
I guess efficient was implied, but have edited question to make it explicit. If the problem were restricted to addition it would be trivial to solve (keep adding 9 and on the last addition add the appropriate value). One algorithm is to find the closest value reachable by a power, then recurse finding a solution for the difference between this value and the target value. –  Derek Jones Mar 31 '12 at 10:02

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).

share|improve this answer
    
Without subtract 101 requires at least four operations, e.g., ((2*7)+9)*4+9, and with subtract can it be done in three, (8+9)*6-1. This is the smallest value that requires a subtract to get a minimum solution. –  Derek Jones Mar 31 '12 at 21:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.