search

leto / math--primality

Advanced primality-checking algorithms
http://duke.leto.net
8 stars 13 forks source link

Research feasibility of using Math::Polynomial+Math::GMPz instead of Math::Primality::BigPolynomial #5

Open leto opened 12 years ago

leto commented 12 years ago

Currently we have Math::Primality::BigPolynomial, which basically allows you to create univariate polynomials with Math::GMPz objects as coefficients.

Last night I was going to extract BigPolynomial out to it's own CPAN module, but I ran across Math::Polynomial, which allows arbitrary objects as coefficients of univariate polynomials.

It seems like we could remove the need for M::P::BigPolynomial if we have Math::Primality::AKS use Math::Polynomial with Math::GMPz objects. This would also mean moving the mpz_* functions out of M::P::BigPolynomial back into M::P::AKS, which is probably where they belong, for now.

Any comments about this, @bubaflub ?

bubaflub commented 12 years ago

Quoth the Math::Polynomial docs:

The module works with various types of coefficients, like ordinary floating point numbers, complex numbers, arbitrary precision rationals, matrices, elements of finite fields, and lots of others. All that is required is that the coefficients are either Perl numbers or objects with suitably overloaded arithmetic operators. Operations on polynomials are carried out by reducing them to basic operations in the domain of their coefficients.

Math::GMPz does have operator overloading:

Overloading works with numbers, strings, Math::GMPz objects and, to a limited extent, Math::MPFR objects (iff version 3.13 or later of Math::MPFR has been installed).

So in theory we could combine this and just take our specific algorithm out. It looks like Math::Polynomial has mod and mmod functions which should cover what we need. Do you want to open up another branch to hack on this?

leto commented 12 years ago

Yes, sounds good to me! We may see a performance hit if Math::Polynomial uses overloading extensively, but we won't really know unless we try.