Re: round4 performance

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

On Tue, May 04, 2004 at 04:17:06PM +0200, Xavier-François Roblot wrote:
> Hi developers,
> 
> On Wed, 2004-04-28 at 04:36, Igor Schein wrote:
> > Hi,
> > 
> > here's a polynomial on which round2 heavily outperforms round4:
> > 
> > x^64 + 528*x^60 + 422640*x^56 + 154189440*x^52 + 46085461920*x^48 + 86643136
> > 30464*x^44 + 1067417121457152*x^40 + 76273480007101440*x^36 + 29307987576360
> > 23040*x^32 + 31785192406564024320*x^28 + 729662629421496287232*x^24 - 866453
> > 9928316858220544*x^20 + 114361270118934673858560*x^16 - 51757447983683584779
> > 87840*x^12 + 47264303406943521096007680*x^8 - 774599638688652156020195328*x^
> > 4 + 7585622913396815983510880256
> 
> I have committed a big patch that attempts to make round4 perform better
> with this kind of polynomial. There are some improvements but still it
> is significantly slower than round2... Also, I added some garbage
> collecting so at least the stack necessary should now be reasonable. In
> any case, the changes I have made still require a lot of tunings (and
> also probably debugging!), so any feedback is welcome.

Apparently, now round4 is faster than round2 by 10% on this example.
(maybe not if we look only at the prime 3, though).

I wonder if fastvalpos() could not be changed to compute 
newton sums iteratively and stop as soon as the criterium apply
and return 0, instead of precomputing a fixed set of sums.

Cheers,
Bill.