title: Given an increasing polynomial, how do you efficiently find x values for fixed intervals of y?
body: <p><strong>Problem:</strong> Given a polynomial of degree <em>n</em> (with coefficients <em>a</em><sub>0</sub> through <em>a</em><sub>n-1</sub>) that is guaranteed to be increasing from <em>x</em> = 0 to <em>x</em><sub>max</sub>, what is the most efficient algorithm to find the first <em>m</em> points with equally-spaced <em>y</em> values (i.e. <em>y</em><sub>i</sub> - <em>y</em><sub>i-1</sub> == <em>c</em>, for all <em>i</em>)?</p>
  
  <p><strong>Example:</strong> If I want the spacing to be <em>c</em> = 1, and my polynomial is <code>f(x) = x^2</code>, then the first three points would be at <em>y</em>=1 (<em>x</em>=1), <em>y</em>=2 (<em>x</em>~=1.4142), and <em>y</em>=3 (<em>x</em>~=1.7321).</p>
  
  <hr>
  
  <p>I'm not sure if it will be significant, but my specific problem involves the <em>cube</em> of a polynomial with given coefficients.  My intuition tells me that the most efficient solution should be the same, but I'm not sure.</p>
  
  <p>I'm encountering this working through the problems in the ACM's <a href="http://home.a-eskwadraat.nl/~kink/icpc2012.pdf" rel="nofollow noreferrer">problem set</a> for the 2012 World Finals (problem B), so this is mostly because I'm curious.</p>
  
  <hr>
  
  <p><strong>Edit:</strong> I'm not sure if this should go on the <a href="https://math.stackexchange.com/">Math SE</a>?</p>