Given any quadratic equation of the form $y=ax^2+bx+c$, I want to find the minimum value for a specific range of $x$.

My programmer brain can do it in a branchy, algorithmic way as follows, but is there a more elegant solution?

  • if the $a$ coefficient is positive,
    • and the end of my range is before the lowest point of the quadratic,
      • return the end of my range
    • and the start of my range is after the lowest point of the quadratic,
      • return the start of my range
    • and the lowest point of the quadratic occurs in the middle of my range,
      • return the lowest point of the quadratic
  • if the $a$ coefficient is negative, etc...
  • $\begingroup$ Your first half wouldn't look so branchy if you wrote it simply as $\min(\max(x_1, x_0), x_2)$, with $x_0, x_1, x_2$ as in Isaac's answer. $\endgroup$ – Rahul Jan 27 '11 at 14:36

Given that your range is $x_0$ to $x_2$, let $x_1=-\frac{b}{2a}$. The minimum value of $y$ occurs at $x_0$, $x_2$, or $x_1$ (if $x_0\le x_1\le x_2$). So, compute $y_0=ax_0^2+bx_0+c$, $y_1=ax_1^2+bx_1+c$ (if $x_1$ is in the range), and $y_2=ax_2^2+bx_2+c$ and pick whichever is the least of those.

edit to be clear, what I'm suggesting is something like:

def quadMin(a, b, c, xmin, xmax):
  q0 = (a * xmin + b) * xmin + c
  q2 = (a * xmax + b) * xmax + c
  x1 = -b / (2*a)
  if (xmin < x1) and (x1 < xmax):
    q1 = (a * x1 + b) * x1 + c
    return min(q0, q1, q2)
    return min(q0, q2)
  • $\begingroup$ You've stated it more elegantly, but because of your sly brackets, if you write this down formally it ends up as the same branching alg as the OP. $\endgroup$ – tenpn Jan 27 '11 at 15:38
  • $\begingroup$ @tenpn: Not really. This ends up computing all three values of the quadratic, while your branching algorithm does not. $\endgroup$ – Aryabhata Jan 27 '11 at 15:54
  • 1
    $\begingroup$ @tenpn: It depends on what you mean; for a computer, comparisons are more efficient than the simple calculations here, so the "branching" algorithm is probably faster (though slower to program). For a human, on the other hand, navigating the tree is usually more time-consuming than the simple-minded computations. Isaac's recipe says "always compute these two values, check to see if you need to compute this third value, compare the answers", which is simpler to follow (no branching involved). So, for a computer, the branching is more "efficient". For a human, this is easier to remember and use. $\endgroup$ – Arturo Magidin Jan 27 '11 at 16:09
  • 2
    $\begingroup$ @tenpn: You didn't ask for efficient. You asked for elegant. $\endgroup$ – Isaac Jan 27 '11 at 17:01
  • 2
    $\begingroup$ @Tenpn: What Isaac said. You asked for elegant! Inefficient depends on the model. For instance, I would say, on a parallel computer, Isaac's solution would be more efficient that what you have. $\endgroup$ – Aryabhata Jan 27 '11 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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