[GiNaC-devel] Volunteer to continue the work on NTL factorisation bindings

[Remco Bloemen]

Alexei,

First of all, thank you very much for looking at my code and giving good 
pointers! It really makes a newcomer feel appreciated.

On Wednesday 05 September 2007 15:07:36 Sheplyakov Alexei wrote:
> On Tue, Aug 28, 2007 at 06:02:08PM +0200, Remco Bloemen wrote:
> > I have created a simple factorisation for polynomials in Q[x] with real
> > roots (source attached, based on [2]) but it's really slow.
>
> I _think_ there are two reasons for that. First, GiNaC::add and GiNaC::mul
> are way to abstract to repersent polynomials (especially univariate ones)
> efficiently.

Your suggestion of using std::vector was already on my mind, I will certainly 
implement it. It's just that I wanted to evaluate the NTL way before I would 
spent time improving my own humble factorizer.

> Secondly, your implementation of  mod 2^n arithmetic is really
> far from optimal.

Yes, I am aware of that. I wrote the *2n functions as a temporary solution, 
mainly because I did not know how to do it efficiently using CLN. Your 
examples teach me that this can be easily done.

> > An NTL based implementation would be very powerfull and feasible, as said
> > in [1]. I would like to volunteer to continue this work.
>
> IMHO, using two different bignum libraries and converting expressions (and
> numbers) between them is a bad idea. Much better option is to port NTL's
> algorithms to CLN.

I also looked at Singular and I came to the same conclusion that it would be 
best to port the algorithms. The main reasons was that NTL only supports 
univariate integer factorization and that is only a fairly small (though 
performance-wise important) part of full multivariate polynomial 
factorization over extension fields.

Kind regards,
Remco