title: Fast algorithm to optimize a sequence of arithmetic expression
body: <p><strong>EDIT: clarified description of problem</strong></p>
  
  <p>Is there a fast algorithm solving following problem?
  <del>And, is also for extendend version of this problem
  that is replaced natural numbers to Z/(2^n Z)?</del>(This problem was too complex to add more quesion in one place, IMO.)</p>
  
  <h2>Problem:</h2>
  
  <p>For a given set of natural numbers like {7, 20, 17, 100}, required algorithm
  returns the <em>shortest</em> sequence of additions, mutliplications and powers compute
  all of given numbers.
  Each item of sequence are (correct) equation that matches following pattern:</p>
  
  <pre><code>&lt;number&gt; = &lt;number&gt; &lt;op&gt; &lt;number&gt;
  </code></pre>
  
  <p>where &lt;number&gt; is a natual number, &lt;op&gt; is one of {+, *, ^}.</p>
  
  <p>In the sequence, each operand of &lt;op&gt; should be one of</p>
  
  <ul>
  <li>1</li>
  <li>numbers which are already appeared in the left-hand-side of equal.</li>
  </ul>
  
  <h2>Example:</h2>
  
  <pre><code>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
  </code></pre>
  
  <hr>
  
  <p>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.</p>
  
  <p>(<a href="https://gist.github.com/minkless/5451060" rel="nofollow">Actual code</a>,
   <a href="https://gist.github.com/minkless/5451090" rel="nofollow">very simple test</a>)</p>
  
  <h2>My current (Pseudo)code:</h2>
  
  <pre><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 &gt;= 2, k &gt;= 2 }
      + { {j, k} | j*k == n, j &gt;= 2, k &gt;= 2 }
      + { {j, k} | j+k == n, j &gt;= 1, k &gt;= 1 }
  
  -- remember the smallest set of "computed" number
  bestSet := {i | 1 &lt;= i &lt;= largeNumber}
  
  -- backtracking algorithm
  -- from: input
  -- to:   accumulator of "already computed" number
  closure from to =
      if (from is empty)
          if (|bestSet| &gt; |to|)
              bestSet := to
              return
      else if (|from| + |to| &gt;= |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 {})
  </code></pre>
  
  <h2>Additional Note:</h2>
  
  <p>Answers like</p>
  
  <ul>
  <li>There isn't a fast algorithm, because...</li>
  <li>There is a heuristic algorithm, it is...</li>
  </ul>
  
  <p>are also welcomed. Now I'm feeling that there is no fast and exact algorithm...</p>
  
  <p>Answer #1 can be used as a heuristic, I think.</p>