Re: polsturm() slower

["Karim Belabas" <belabas@math.u-bordeaux1.fr>]

* Igor Schein [2005-08-12 01:04]:
> Hi,
> 
> ? polsturm(pollegendre(5!));
> time = 2,350 ms.
> ? polroots(pollegendre(5!));
> time = 180 ms.
> 
> Any reason why polsturm is so much slower?  I understand that former
> is doing more than latter, but I can't image it doing that much more.

Actually, no. Polroots is much more complicated than polsturm.
(OK, orthogonal polynomials are totally real, so in this case one could
immensely simplify polroots, but I'm speaking of the general case.)

The main reason for the speed difference is that polroots uses intricate
pertubation results so as to deal with just enough significant digits to
solve the problem, whereas polsturm handles gigantic integers in exact
arithmetic (imagine the remainder sequence for your input...). Compare:

(17:49) gp > polsturm(pollegendre(5!))
time = 15,274 ms.
%1 = 120

(17:50) gp > polsturm(pollegendre(5!) * 1.)
time = 5 ms.
%2 = 52  \\ very wrong...

(17:50) gp > \p100
   realprecision = 105 significant digits (100 digits displayed)
(17:50) gp > polsturm(pollegendre(5!) * 1.)
time = 16 ms.
%3 = 120 \\ OK now

Guillaume Hanrot wrote an implementation of Uspensky's method (faster
than Sturm, but still slower than polroots at low accuracies) some time
ago, but I haven't received a final version yet.

Cheers,

    Karim.
-- 
Karim Belabas                  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]