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

[Sheplyakov Alexei]

Hello!

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. For example, this snippet of code

> 	if(is_exactly_a<add>(poly))
> 	{
> 		ex result = 0;
> 		for (size_t i=0; i < poly.nops(); i++)
> 		{
> 			result += polymod2n(poly.op(i), n);
> 		}
> 		return result;
> 	}

involves N = poly.nops() calls to add.eval(), each of them is O(N).
poly.op(i) is O(N) too. So, you'd better use std::vector to represent
univariate polynomials:

void mod2n(std::vector<cln::cl_MI>& result, std::vector<cln::cl_I>& poly,
           const unsigned int n)
{
	result.reserve(poly.size());
	cln::cl_modint_ring R(cln::cl_I(1) << n);
	for (std::size_t i = 0; i < poly.size(); ++i)
		result.push_back(R.canonhom(poly[i]));
}

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

> numeric mod2n(const numeric &p, const int n)
> {
> 	numeric modulus = pow(numeric(2), numeric(n));
> 	return mod(p, modulus);
> }

Operations on mod 2^n integers and polynomials can (and should) be done
using bit shifts (a very fast operation). Actually this is why yacas (and some
other software) use them in first place. So, it should be

static inline const cln::cl_MI mod2n(const cln::cl_I& p, const unsigned int n)
{
  cln::cl_modint_ring R(cln::cl_I(1) << n);
	return R.canonhom(p);
}

> Creating a reasonable implementation would require much work.

Sure.

> 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.


Best regards,
 Alexei

-- 
All science is either physics or stamp collecting.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 827 bytes
Desc: Digital signature
Url : http://www.cebix.net/pipermail/ginac-devel/attachments/20070905/586decb5/attachment.pgp