I am writing an algorithm that will need to find the first positive real root of a given polynomial, over and over again, where the only thing that changes in each iteration is the constant term. I need this algorithm to be as efficient as possible and want to avoid redundant computation in each iteration. Is there some calculation or manipulation that can be done before the constant term is known in order to reduce the calculation after it's known?

Specifically, given that we want the first positive real root (if it exists) of the following,

$a_n x^n + a_{n-1}x^{n-1} + \ldots + a_0 = 0$,

where $a_k \in \mathbb{Z} \space \forall \space k$, and $a_0$ is not yet known, what can be done now in order to minimize computation after $a_0$ becomes known? I am asking in the mathematical sense, but if it helps, I will be implementing this in C++.

  • $\begingroup$ What does "first" mean here? $\endgroup$ – kimchi lover Dec 27 '17 at 23:59
  • $\begingroup$ Good question. In this case, it is arbitrary. I just want ANY positive real root, whichever is the fastest to calculate or emerges "first" from the calculation. In almost all my usage cases, there will only be one such root anyway for the polynomials I'm dealing with. $\endgroup$ – Ben Hershey Dec 28 '17 at 0:02
  • $\begingroup$ Use the root of the previous iteration as an initial guess to find the root of the polynomial in the current iteration if there is a relationship between $a_0$'s of both iteration. $\endgroup$ – Math Lover Dec 28 '17 at 0:02
  • $\begingroup$ @MathLover I should clarify though that there is no predictable relationship between $a_0$ terms in each iteration. Still a good idea though. Better than a random initial guess probably. $\endgroup$ – Ben Hershey Dec 28 '17 at 0:09

Your Answer

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

Browse other questions tagged or ask your own question.