Re: Real roots of a polynomial

[Bill Allombert <Bill.Allombert@math.u-bordeaux1.fr>]

On Fri, Oct 19, 2012 at 10:10:47AM +0200, Loïc Grenié wrote:
>     Hello pari developers,
> 
>     does anybody know any way to obtain the real roots of a
>   polynomial without computing the non-real ones (potentially
>   saving time) ? A quick and dirty gp script using Sturm sequence
>   and Legendre bounds was 35% faster than polroots on a
>   (single) sample polynomial. Is there any secret pari function
>   GEN __get_real_roots_of_polynomial_really_fast(GEN P) that
>   I have not noticed ? If it helps, I only need the roots between two
>   bounds.

There basically two family of algorithms for that task, Descartes rules and Uspensky,
which are basically equivalent in complexity if you do not the distribution of your
polynomials.

A persistent rumor in Nancy suggests the existence of an implementation of Uspensky
algorithm for libpari, but I never seen it.

Cheers,
Bill.