Re: Inefficient "solve" in Pari 2.0.18 (beta) ?

[Karim BELABAS <Karim.Belabas@math.u-psud.fr>]

[Bill Allombert:]
> Thanks to Will Galway, the corrected solve function is much faster
> 
> ? \p400
>    realprecision = 404 significant digits (400 digits displayed)
> ? solve(x=-2,2,cos(x)-x)
> %12 = 0.7390851332151606416553120876738734040134117589007574649656806357732846548835475945993761069317665318498012466439871630277149036913084203157804405746207786885249038915392894388450952348013356312767722315809563537765724512043734199364335125384097800343406467004794021434780802718018837711361382042066316335037277991696731223230061388658203621770810997897062684240588094898683261860600485898958548725736   
> 
> Old version:
>  ***   last result computed in 12,950 ms.   
> New version:
>  ***   last result computed in 160 ms.  

Brent's method uses (inverse) quadratic interpolation to speed up the
convergence, and reverts to naive bissection when convergence gets slower
than it should be (meaning the function is not well behaved enough near the
root). The typo I corrected yesterday caused the check to fail most of the
time, hence the interpolation was never successful. Net result is that we
only got linear convergence, and in a very inefficient way on top of that
since auxiliary data needed to be computed for the doomed checks...

    Karim.
__
Karim Belabas                    email: Karim.Belabas@math.u-psud.fr
Dep. de Mathematiques, Bat. 425
Universite Paris-Sud             Tel: (00 33) 1 69 15 57 48
F-91405 Orsay (France)           Fax: (00 33) 1 69 15 60 19
--
PARI/GP Home Page: http://www.parigp-home.de/