Find all rational roots of a polynomial equation - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-22T08:23:28Z https://cs.stackexchange.com/feeds/question/64602 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/64602 0 Find all rational roots of a polynomial equation user59821 https://cs.stackexchange.com/users/59821 2016-10-14T13:13:07Z 2017-02-22T07:42:44Z <p>I'm going to try to design an algorithm to find all the rational roots of a polynomial equation in range [a, b]. Can someone please tell me which algorithm currently solves the problem with lowest worst-case complexity? This algorithm will be for a general purpose computer(Turing Machine).</p> https://cs.stackexchange.com/questions/64602/-/64603#64603 2 Answer by adrianN for Find all rational roots of a polynomial equation adrianN https://cs.stackexchange.com/users/4736 2016-10-14T13:33:19Z 2017-02-18T13:05:47Z <p>The paper <a href="https://arxiv.org/pdf/1308.4088.pdf" rel="nofollow noreferrer">Computing Real Roots of Real Polynomials</a> by Sagraloff and Mehlhorn from 2015 provides an almost optimal algorithm and references for simpler algorithms that might be used in practice. The <a href="http://doc.cgal.org/latest/Algebraic_kernel_d/index.html" rel="nofollow noreferrer">CGAL</a> library (in version 4.9) for example uses the method developed by Arno Eigenwillig in his PhD thesis <em>Real Root Isolation for Exact and Approximate Polynomials Using Descartes' Rule of Signs</em>.</p> https://cs.stackexchange.com/questions/64602/-/70458#70458 1 Answer by Discrete lizard for Find all rational roots of a polynomial equation Discrete lizard https://cs.stackexchange.com/users/65339 2017-02-18T11:50:03Z 2017-02-22T07:42:44Z <p>If you only want to find all <em>rational</em> roots, you can simply use the <em><a href="https://en.wikipedia.org/wiki/Rational_root_theorem" rel="nofollow noreferrer">rational root theorem</a></em>. This theorem states that, given a polynomial $a_n x^n + a_{n-1}x^{n-1} + \ldots + a_1x+a_0$, for any rational root $x=p/q$, where $p,q\in \mathbb N$ and $GCD(p,q)=1$, we have:</p> <ul> <li>$p$ is a divisor of $a_0$ and</li> <li>$q$ is a divisor of $a_n$.</li> </ul> <p>So, one possible algorithm is to factorise $a_0$ and $a_n$ to get all possible $p,q$ and simply 'fill in' the combinations as a ratio to see if it is a root. This way, we find all possible roots. The complexity of the root finding is negligible to the factorisation, so the complexity of this method is the complexity of factorising $a_0$ and $a_n$, which will take a long time for large $a_0$ and $a_n$ (but is fast for small $a_0$ and $a_n$, independent of the rest of the equation!)</p> <p>There is a speedup, however. If a root $p/q\in [a,b]$, this means that $p\in [aq,bq]$ and $q\in [p/b,p/a]$. If $a_0$ is small, but $a_n$ is large, we can find all divisors $p_i$ of $a_0$ and test for all integers in the range $[p_i/b,p_i/a]$ whether they divide $a_n$. If $a_n$ is large and $[a,b]$ not too big, this will be a lot faster than factoring $a_n$. This means that we only have to do one factorisation and can do it on the smallest of $a_0$ and $a_n$.</p> <p>So, to get a complete overview of the worst case complexity for the methods described, define $a_{\max}=\max\{a_0,a_n\}$ and $a_{\min} = \min\{a_0,a_n\}$. Assume $b\geq a&gt;1$ (another worst case exists when $a,b&lt;1$, but that will have the same running time, only with $1/a$ and $1/b$). We will factor $a_{\min}$ and consider all it's divisors, of which there are $O(\log n)$ <em>on average</em> (The actual worst case upper bound is $\exp(O(\frac{\log n}{\log\log n}))$, but this factor will likely be dominated anyway, so I'd rather keep it simple. A derivation and more is given <a href="https://terrytao.wordpress.com/2008/09/23/the-divisor-bound/" rel="nofollow noreferrer">here</a>). </p> <p>All divisors of $a_{\min}$ are in the range $[1,\sqrt{a_{\min}}]$, so we do at most $\lceil (b-a)\sqrt{a_{\min}} \rceil$ divisor tests per factor of $a_\min$. Since we know that any factor of $n$ must be in $[1,\sqrt{n}]$, we have that $b-a\leq \sqrt{a_\max}$ to be useful (if not, replace $[a,b]$ by $[1,\sqrt{a_\max}]$). So, we do at most $\lceil \sqrt{a_{\min}a_\max} \rceil$ divisor tests. Testing whether a number is a divisor of $a_\max$ takes $O(\log a_\max)$ time, using the Euclidean algorithm. </p> <p>Factoring $a_\min$ takes $O(F(a_\min))$, where $F(n):=\exp ((\log n)^{1/3}(\log \log n)^{2/3})$.</p> <p>So, in total, this algorithm has a worst case complexity of $O(F(a_\min) + (b-a)\sqrt{a_\min}\log{a_\min}\log{a_\max})$ time. Since we can assume $(b-a)\leq a_\max$, the factoring is the only non-polynomial (in $a_\min$ or $a_\max$) part of this formula, so we get that the complexity is simply $O(F(a_\min))$. </p> <p>I highly doubt that it is possible to find all rational roots within a range without factoring at least one of the coefficients, because that would mean (by the rational root theorem), that we have found a more efficient algorithm for factoring! In that case, the algorithm I gave is asymptotically optimal, as it is the cost of factoring the smallest of the coefficients $a_0$ and $a_n$. </p>