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