|Bill Allombert on Fri, 19 Oct 2012 10:30:27 +0200|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|Re: Real roots of a polynomial|
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.