Re: polredabs() observation

[Igor Schein <igor@txc.com>]

On Tue, Feb 04, 2003 at 09:33:08PM +0100, Karim BELABAS wrote:
> On Fri, 31 Jan 2003, Igor Schein wrote:
> 
> > On Tue, Jan 28, 2003 at 10:09:08AM -0500, Igor Schein wrote:
> >> polredabs() on the following polynomial is much slower in latest CVS compared to stable:
> >>
> >> x^16-224*x^14+19520*x^12-843488*x^10+19172700*x^8-223732800*x^6+1177835136*x^4-1779647552*x^2+171662404
> >
> > Actually, here's the very recent change that made polredabs()
> > considerably slower in many cases:
> >
> > \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
> > revision 1.627
> > date: 2003/01/04 19:00:43;  author: karim;  state: Exp;  lines: +2 -0
> > 48- simplified fincke_pohst() [don't recompute gram_matrix]
> > \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
> >
> > And here's a smaller yet even more drastic example:
> >
> > polredabs(x^4+51976*x^3+837697192*x^2+4716826989696*x+5560701377110272);
> 
> Typo: the smallvectors() bound was the square of what it should have been...
> I was confused by the terse comment [ due to me, from code
> reverse-engineering ] at the header of sqred1(), and didn't check which
> "Cholesky form" it was about. It turned out it was not the standard one:-(.
> 
> Both fixed.

It's still pretty much broken.  Consider the following trivial cases:

polredabs(x^4+10^80*x^2+1,16)

precision issue, takes years

polredabs(x^8+10^80*x^4+1,16)

too many vectors, also takes years

Both used to finish in no time.

Thanks

Igor