Re: Counting real roots of integer polynomials

[Gordon Royle <gordon.royle@uwa.edu.au>]

Thank you for your suggestions.

However, I could not find a way to use polsturm effectively - the polsturm  in  Pari 2.9.5  needs a squarefree polynomial, and while the one in Pari  2.10.0 version will accept a non-square-free polynomial, it only returns distinct roots.

So to get the actual multiplicities, I could see no better way than using “factor” to first factorise the polynomial, and then deal with each factor separately.

This proved to be a bad idea, because for polynomials of the size that I am dealing with, “factor” takes about 5 times as long as just running “polrootsreal”. 

Anyway, for the time being I am manually stripping off factors of (x-1) and (x-2) and then just using polrootsreal on the remainder. This is about 40% faster than what I was doing before and it will suffice for my needs. It does about 10^6 polynomials per minute, and seeing I have maybe 2 billion to do, there is no real need to improve it further.







> On 7 Jun 2018, at 3:04 pm, Bill Allombert <Bill.Allombert@math.u-bordeaux.fr> wrote:
> 
> On Thu, Jun 07, 2018 at 08:48:45AM +0200, Dirk Laurie wrote:
>> You don't need polrootsreal. A Sturm sequence is adequate. Since your
>> polynomials have integer coefficients, you can do it in rational
>> arithmetic if necessary.
>> 
>> https://en.wikipedia.org/wiki/Sturm%27s_theorem
> 
> and the GP function for that is polsturm.
> 
> Cheers,
> Bill.