Bill Allombert on Wed, 30 Apr 2003 10:47:46 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: polredabs() suggestion


On Tue, Apr 29, 2003 at 05:53:15PM -0400, Igor Schein wrote:
> > P.S: I could "mark" the previous generator, so that the check is not done
> > many times on the same element, and it is just accepted as is, provided it
> > passes the test once. With current settings that means < 0.5% savings. I
> > didn't bother.
> > -- 
> > Karim Belabas                     Tel: (+33) (0)1 69 15 57 48
> 
> I feel very strongly that this would show a significant improvement on
> the polynomials I've had problems with, e.g.
> 
> x^8-97418273277417164826810*x^4-97418273278115084139045*x^2+97418273278115084139045
> 
> ( from one of my older postings ).
> 
> So if there's no performance penalty for an average case ( which I
> don't forsee ), it's a change I would more than welcome.

I am with Igor here. I have made a lot a similar tweaking in galoisinit.
While it seems wasteful in normal case, it can make a large difference
on catastrophical case. And usually catastrophical case are the more
interesting.

For example you could keep a 'top 10' list of generators that appear the
most often and compare with them before the other test. If it is found, you
reorder them.

Cheers,
Bill