Fast algorithm to optimize a sequence of arithmetic expression

Question

EDIT: clarified description of problem

Is there a fast algorithm solving following problem? And, is also for extendend version of this problem that is replaced natural numbers to Z/(2^n Z)?(This problem was too complex to add more quesion in one place, IMO.)

Problem:

For a given set of natural numbers like {7, 20, 17, 100}, required algorithm returns the shortest sequence of additions, mutliplications and powers compute all of given numbers. Each item of sequence are (correct) equation that matches following pattern:

<number> = <number> <op> <number>

where <number> is a natual number, <op> is one of {+, *, ^}.

In the sequence, each operand of <op> should be one of

• 1
• numbers which are already appeared in the left-hand-side of equal.

Example:

Input: {7, 20, 17, 100}
Output:
2 = 1 + 1
3 = 1 + 2
6 = 2 * 3
7 = 1 + 6
10 = 3 + 7
17 = 7 + 10
20 = 2 * 10
100 = 10 ^ 2

---

I wrote backtracking algorithm in Haskell. it works for small input like above, but my real query is randomly distributed ~30 numbers in [0,255]. for real query, following code takes 2~10 minutes in my PC.

(Actual code, very simple test)

My current (Pseudo)code:

-- generate set of sets required to compute n.
-- operater (+) on set is set union.
requiredNumbers 0 = { {} }
requiredNumbers 1 = { {} }
requiredNumbers n =
      { {j, k} | j^k == n, j >= 2, k >= 2 }
    + { {j, k} | j*k == n, j >= 2, k >= 2 }
    + { {j, k} | j+k == n, j >= 1, k >= 1 }

-- remember the smallest set of "computed" number
bestSet := {i | 1 <= i <= largeNumber}

-- backtracking algorithm
-- from: input
-- to:   accumulator of "already computed" number
closure from to =
    if (from is empty)
        if (|bestSet| > |to|)
            bestSet := to
            return
    else if (|from| + |to| >= |bestSet|)
        -- cut branch
        return
    else
        m := min(from)
        from' := deleteMin(from)
        foreach (req in (requiredNumbers m))
            closure (from' + (req - to)) (to + {m}) 

-- recoverEquation is a function converts set of number to set of equation.
-- it can be done easily.
output = recoverEquation (closure input {})

Additional Note:

Answers like

• There isn't a fast algorithm, because...
• There is a heuristic algorithm, it is...

are also welcomed. Now I'm feeling that there is no fast and exact algorithm...

Answer #1 can be used as a heuristic, I think.

Answer 1

What if you worked backwards from the highest number in a sorted input, checking if/how to utilize the smaller numbers (and numbers that are being introduced) in its construction?

For example, although this may not guarantee the shortest sequence...

input: {7, 20, 17, 100}

(100) = (20) * 5 => 
(7) = 5 + 2      => 
(17) = 10 + (7)  =>
(20) = 10 * 2    =>
10 = 5 * 2       =>
5 = 3 + 2        =>
3 = 2 + 1        =>
2 = 1 + 1

Answer 2

What I recommend is to transform it into some kind of graph shortest path algorithm.

• For each number, you compute (and store) the shortest path of operations. Technically one step is enough: For each number you can store the operation and the two operands (left and right, because power operation is not commutative), and also the weight ("nodes")
• Initially you register 1 with the weight of zero
• Every time you register a new number, you have to generate all calculations with that number (all additions, multiplications, powers) with all already-registered numbers. ("edges")
  • Filter for the calculations: it the result of the calculation is already registered, you shouldn't store that, because there is an easier way to get to that number
  • Store only 1 operation for the commutative ones (1+2=2+1)
  • Prefilter the power operation because that may even cause overflow
• You have to order this list to the shortest sum path (weight of the edge). Weight = (weight of operand1) + (weight of operand2) + (1, which is the weight of the operation)
  • You can exclude all resulting numbers which are greater than the maximum number that we have to find (e.g. if we found 100 already, anything greater that 20 can be excluded) - this can be refined so that you can check the members of the operations also.
• If you hit one of your target numbers, then you found the shortest way of calculating one of your target numbers, you have to restart the generations:
  • Recalculate the maximum of the target numbers
  • Go back on the paths of the currently found number, set their weight to 0 (they will be given from now on, because their cost is already paid)
  • Recalculate the weight for the operations in the generation list, because the source operand weight may have been changed (this results reordering at the end) - here you can exclude those where either operand is greater than the new maximum
• If all the numbers are hit, then the search is over

You can build your expression using the "backlinks" (operation, left and right operands) for each of your target numbers.

The main point is that we always keep our eye on the target function, which is that the total number of operation must be the minimum possible. In order to get this, we always calculate the shortest path to a certain number, then considering that number (and all the other numbers on the way) as given numbers, then extending our search to the remaining targets.

Theoretically, this algorithm processes (registers) each numbers only once. Applying the proper filters cuts the unnecessary branches, so nothing is calculated twice (except the weights of the in-queue elements)