leto / math--primality

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

Merge the fix_aks branch #1

Closed leto closed 12 years ago

leto commented 12 years ago

Do it.

leto commented 12 years ago

Hey @bubaflub, can you help with this?

bubaflub commented 12 years ago

Just saw this - I'll try and get this done sometime this week or perhaps next weekend. I've got a few other fixes coming in for this module as well.

bubaflub commented 12 years ago

What do you think about splitting functionality into other modules - Math::Primality::AKS and Math::Primality::BPSW. We could still bundle all of it together but then things would be a bit more separated.

leto commented 12 years ago

+1 On Dec 3, 2011 10:59 PM, "Bob Kuo" < reply@reply.github.com> wrote:

What do you think about splitting functionality into other modules - Math::Primality::AKS and Math::Primality::BPSW. We could still bundle all of it together but then things would be a bit more separated.


Reply to this email directly or view it on GitHub: https://github.com/leto/math--primality/issues/1#issuecomment-3005178

leto commented 12 years ago

Current status:

 prove -lrv t/is_aks_prime.t 
t/is_aks_prime.t .. 
1..232
ok 1 - use Math::Primality::AKS;
# Testing Math::Primality::AKS 0.01, Perl 5.012004, /usr/bin/perl
Can't call method "degree" without a package or object reference at /Users/jleto/git/math--primality/lib/Math/Primality/BigPolynomial.pm line 116
    Math::Primality::BigPolynomial::mpz_poly_mod_mult('Math::Primality::BigPolynomial=HASH(0x7f8c8882bb80)', 'Math::Primality::BigPolynomial=HASH(0x7f8c8882bb80)', 'Math::Primality::BigPolynomial=HASH(0x7f8c8882bb80)', 2, undef) called at /Users/jleto/git/math--primality/lib/Math/Primality/BigPolynomial.pm line 156
    Math::Primality::BigPolynomial::mpz_poly_mod_power('Math::Primality::BigPolynomial=HASH(0x7f8c88830318)', 'Math::Primality::BigPolynomial=HASH(0x7f8c8882bb80)', 'Math::GMPz=SCALAR(0x7f8c8882bc58)', 'Math::GMPz=SCALAR(0x7f8c8882bc58)', 2) called at /Users/jleto/git/math--primality/lib/Math/Primality/AKS.pm line 122
    Math::Primality::AKS::is_aks_prime('Math::GMPz=SCALAR(0x7f8c888073b8)') called at t/is_aks_prime.t line 20
# Looks like you planned 232 tests but ran 1.
# Looks like your test exited with 255 just after 1.
leto commented 12 years ago

Now:

$ prove -lrv t/is_aks_prime.t 
t/is_aks_prime.t .. 
1..232
ok 1 - use Math::Primality::AKS;
# Testing Math::Primality::AKS 0.01, Perl 5.012004, /usr/bin/perl
Use of uninitialized value $polymod in numeric lt (<) at /Users/jleto/git/math--primality/lib/Math/Primality/BigPolynomial.pm line 119
    Math::Primality::BigPolynomial::mpz_poly_mod_mult('Math::Primality::BigPolynomial=HASH(0x7fed2882bb80)', 'Math::Primality::BigPolynomial=HASH(0x7fed2882bb80)', 'Math::Primality::BigPolynomial=HASH(0x7fed2882bb80)', 2, undef) called at /Users/jleto/git/math--primality/lib/Math/Primality/BigPolynomial.pm line 156
    Math::Primality::BigPolynomial::mpz_poly_mod_power('Math::Primality::BigPolynomial=HASH(0x7fed28830318)', 'Math::Primality::BigPolynomial=HASH(0x7fed2882bb80)', 'Math::GMPz=SCALAR(0x7fed2882bc58)', 'Math::GMPz=SCALAR(0x7fed2882bc58)', 2) called at /Users/jleto/git/math--primality/lib/Math/Primality/AKS.pm line 122
    Math::Primality::AKS::is_aks_prime('Math::GMPz=SCALAR(0x7fed288073b8)') called at t/is_aks_prime.t line 20
Use of uninitialized value $polymod in numeric lt (<) at /Users/jleto/git/math--primality/lib/Math/Primality/BigPolynomial.pm line 119
    Math::Primality::BigPolynomial::mpz_poly_mod_mult('Math::Primality::BigPolynomial=HASH(0x7fed2882bb80)', 'Math::Primality::BigPolynomial=HASH(0x7fed2882bb80)', 'Math::Primality::BigPolynomial=HASH(0x7fed2882bb80)', 2, undef) called at /Users/jleto/git/math--primality/lib/Math/Primality/BigPolynomial.pm line 156
    Math::Primality::BigPolynomial::mpz_poly_mod_power('Math::Primality::BigPolynomial=HASH(0x7fed28830318)', 'Math::Primality::BigPolynomial=HASH(0x7fed2882bb80)', 'Math::GMPz=SCALAR(0x7fed2882bc58)', 'Math::GMPz=SCALAR(0x7fed2882bc58)', 2) called at /Users/jleto/git/math--primality/lib/Math/Primality/AKS.pm line 122
    Math::Primality::AKS::is_aks_prime('Math::GMPz=SCALAR(0x7fed288073b8)') called at t/is_aks_prime.t line 20
Undefined subroutine &Math::Primality::BigPolynomial::mpz_poly_mod_mul called at /Users/jleto/git/math--primality/lib/Math/Primality/BigPolynomial.pm line 158
    Math::Primality::BigPolynomial::mpz_poly_mod_power('Math::Primality::BigPolynomial=HASH(0x7fed28830318)', 'Math::Primality::BigPolynomial=HASH(0x7fed2882bb80)', 'Math::GMPz=SCALAR(0x7fed2882bc58)', 'Math::GMPz=SCALAR(0x7fed2882bc58)', 2) called at /Users/jleto/git/math--primality/lib/Math/Primality/AKS.pm line 122
    Math::Primality::AKS::is_aks_prime('Math::GMPz=SCALAR(0x7fed288073b8)') called at t/is_aks_prime.t line 20
# Looks like you planned 232 tests but ran 1.
# Looks like your test exited with 255 just after 1.
leto commented 12 years ago

@bubaflub can you lend any assistance?

bubaflub commented 12 years ago

@leto hey man, long time no see. I've got some branches that are in various states on my fork - one for better test coverage, one for some more cleanup. I've also received two RT tickets - https://rt.cpan.org/Public/Bug/Display.html?id=79674 and https://rt.cpan.org/Public/Bug/Display.html?id=78379. I'll take a look at this stuff and file some issues for these other two tickets. I'd like to get back to hacking on this.

bubaflub commented 12 years ago

I just did a fresh checkout of your copy and the test passed. I'm using perl 5.12.3 and Math::GMPz version 0.31.

leto commented 12 years ago

I used the patch in one of the RT tickets in 0045721ca . The other patch that mentions prime_count/is_prime confuses me. We already do some of the checks and I would want to see some benchmark data before going further.

leto commented 12 years ago

I get a coredump on Perl 5.10.1 and Math::GMPz as well. Odd.

leto commented 12 years ago

The line that is causing the coredump is this inside Math::Primality::BigPolynomial::mpz_poly_mod_mult:

            Rmpz_mul( $temp, $x->getCoef($j), $temp );

@bubaflub : Your original code has a line:

 Rmpz_add( $temp,  $y->getCoef( $i - $j ) + $y->getCoef( $i + $polymod - $j ) );

which is an invalid call to Rmpz_add (it needs 3 args), so I converted that to:

 Rmpz_add( $temp, $temp,  $y->getCoef( $i - $j ) + $y->getCoef( $i + $polymod - $j ) );

Is that right?

leto commented 12 years ago

After more sleuthing, it looks like this is caused by getCoef returning a 0 instead of a Math::GMPz object that has a value of zero. This is because we do getCoef(2) on a 1st degree polynomial.

leto commented 12 years ago

Looks like getCoef is not quite the issue. Are you sure everything passes for you @bubaflub ? Here is the coredump happening on Travis: http://travis-ci.org/#!/leto/math--primality/jobs/2553084

Did you run the test with prove -lrv ? Without the -l, you will be testing against an installed Math::Primality.

bubaflub commented 12 years ago

Yup, I ran it with -l and I don't have a system or installed Math::Primality anywhere. I'm at a1ea2beae35a9c021791b82249dbe68a4a54cd3c right now.

bubaflub commented 12 years ago

Just realized I'm on the wrong branch. My bad. One sec.