This is an automated email from the git hooks/post-receive script.

ppm-guest pushed a commit to annotated tag v0.19
in repository libmath-prime-util-perl.

commit 5687cb8dccd3176c1a73bc2957bed39fc6be8554
Author: Dana Jacobsen <d...@acm.org>
Date:   Sat Jan 19 02:20:33 2013 -0800

    Better test coverage
---
 Changes                |  2 ++
 lib/Math/Prime/Util.pm |  1 +
 t/13-primecount.t      | 15 ++++++++++-
 t/50-factoring.t       |  9 ++++---
 t/80-pp.t              | 72 +++++++++++++++++++++++++++++++++++++++++++++++++-
 5 files changed, 94 insertions(+), 5 deletions(-)

diff --git a/Changes b/Changes
index c30fc93..02a80c6 100644
--- a/Changes
+++ b/Changes
@@ -8,6 +8,8 @@ Revision history for Perl extension Math::Prime::Util.
 
     - Added tests for bigint is_provable_prime.
 
+    - Added a few tests to give better coverage.
+
 0.18  14 January 2012
 
     - Add random_strong_prime.
diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm
index 18e50b1..a97623b 100644
--- a/lib/Math/Prime/Util.pm
+++ b/lib/Math/Prime/Util.pm
@@ -84,6 +84,7 @@ BEGIN {
     *fermat_factor  = \&Math::Prime::Util::PP::fermat_factor;
     *holf_factor    = \&Math::Prime::Util::PP::holf_factor;
     *squfof_factor  = \&Math::Prime::Util::PP::squfof_factor;
+    *rsqufof_factor = \&Math::Prime::Util::PP::squfof_factor;
     *pbrent_factor  = \&Math::Prime::Util::PP::pbrent_factor;
     *prho_factor    = \&Math::Prime::Util::PP::prho_factor;
     *pminus1_factor = \&Math::Prime::Util::PP::pminus1_factor;
diff --git a/t/13-primecount.t b/t/13-primecount.t
index dc1c53a..9448451 100644
--- a/t/13-primecount.t
+++ b/t/13-primecount.t
@@ -5,6 +5,7 @@ use warnings;
 use Test::More;
 use Math::Prime::Util qw/prime_count prime_count_lower prime_count_upper 
prime_count_approx/;
 
+my $isxs  = Math::Prime::Util::prime_get_config->{'xs'};
 my $use64 = Math::Prime::Util::prime_get_config->{'maxbits'} > 32;
 my $extra = defined $ENV{RELEASE_TESTING} && $ENV{RELEASE_TESTING};
 
@@ -82,7 +83,8 @@ plan tests => 0 + 1
                 + scalar(keys %pivals_small)
                 + $use64 * 3 * scalar(keys %pivals64)
                 + scalar(keys %intervals)
-                + 1;
+                + 1
+                + 6; # prime count specific methods
 
 ok( eval { prime_count(13); 1; }, "prime_count in void context");
 
@@ -148,3 +150,14 @@ sub parse_range {
 #    109726486, // prime count 2^32 interval starting at 10^17
 #    103626726, // prime count 2^32 interval starting at 10^18
 #    98169972}; // prime count 2^32 interval starting at 10^19
+
+# Make sure each specific algorithm isn't broken.
+SKIP: {
+  skip "Not XS -- skipping direct primecount tests", 4 unless $isxs;
+  is(Math::Prime::Util::_XS_lehmer_pi  (3456789), 247352, "XS Lehmer count");
+  is(Math::Prime::Util::_XS_meissel_pi (3456789), 247352, "XS Meissel count");
+  is(Math::Prime::Util::_XS_legendre_pi(3456789), 247352, "XS Legendre count");
+  is(Math::Prime::Util::_XS_prime_count(3456789), 247352, "XS sieve count");
+}
+is(Math::Prime::Util::PP::_lehmer_pi   (3456789), 247352, "PP Lehmer count");
+is(Math::Prime::Util::PP::_sieve_prime_count(3456789), 247352, "PP sieve 
count");
diff --git a/t/50-factoring.t b/t/50-factoring.t
index c826416..fdc2008 100644
--- a/t/50-factoring.t
+++ b/t/50-factoring.t
@@ -30,8 +30,9 @@ my @testn = qw/0 1 2 3 4 5 6 7 8 16 57 64 377 9592 30107 
78498 664579 5761455
                1363 989 779 629 403
                547308031
                808 2727 12625 34643 134431 221897 496213 692759 1228867
-               2463289 3008891 5115953 6961021 8030207 10486123
+               2231139 2463289 3008891 5115953 6961021 8030207 10486123
                10893343 12327779 701737021
+               549900
               /;
 
 my @testn64 = qw/37607912018 346065536839 600851475143
@@ -72,7 +73,7 @@ my %all_factors = (
       0 => [],
 );
 
-plan tests =>  (2 * scalar @testn) + scalar(keys %all_factors) + 6*7;
+plan tests =>  (2 * scalar @testn) + scalar(keys %all_factors) + 7*8;
 
 foreach my $n (@testn) {
   my @f = factor($n);
@@ -100,6 +101,7 @@ extra_factor_test("trial_factor",  sub 
{Math::Prime::Util::trial_factor(shift)})
 extra_factor_test("fermat_factor", sub 
{Math::Prime::Util::fermat_factor(shift)});
 extra_factor_test("holf_factor",   sub 
{Math::Prime::Util::holf_factor(shift)});
 extra_factor_test("squfof_factor", sub 
{Math::Prime::Util::squfof_factor(shift)});
+extra_factor_test("rsqufof_factor", sub 
{Math::Prime::Util::rsqufof_factor(shift)});
 extra_factor_test("pbrent_factor", sub 
{Math::Prime::Util::pbrent_factor(shift)});
 extra_factor_test("prho_factor",   sub 
{Math::Prime::Util::prho_factor(shift)});
 extra_factor_test("pminus1_factor",sub 
{Math::Prime::Util::pminus1_factor(shift)});
@@ -111,8 +113,9 @@ sub extra_factor_test {
   is_deeply( [ sort {$a<=>$b} $fsub->(1)   ], [1],       "$fname(1)" );
   is_deeply( [ sort {$a<=>$b} $fsub->(4)   ], [2, 2],    "$fname(4)" );
   is_deeply( [ sort {$a<=>$b} $fsub->(9)   ], [3, 3],    "$fname(9)" );
-  is_deeply( [ sort {$a<=>$b} $fsub->(25)  ], [5, 5],    "$fname(9)" );
+  is_deeply( [ sort {$a<=>$b} $fsub->(25)  ], [5, 5],    "$fname(25)" );
   is_deeply( [ sort {$a<=>$b} $fsub->(175) ], [5, 5, 7], "$fname(175)" );
   is_deeply( [ sort {$a<=>$b} $fsub->(403) ], [13, 31],  "$fname(403)" );
+  is_deeply( [ sort {$a<=>$b} $fsub->(549900) ], [2,2,3,3,5,5,13,47],  
"$fname(549900)" );
 }
 
diff --git a/t/80-pp.t b/t/80-pp.t
index b1ff085..94f7481 100644
--- a/t/80-pp.t
+++ b/t/80-pp.t
@@ -55,6 +55,8 @@ my %pseudoprimes = (
   61 => [ qw/217 341 1261 2701 3661 6541 6697 7613 13213 16213 22177 23653 
23959 31417 50117 61777 63139 67721 76301 77421 79381 80041/ ],
   73 => [ qw/205 259 533 1441 1921 2665 3439 5257 15457 23281 24617 26797 
27787 28939 34219 39481 44671 45629 64681 67069 76429 79501 93521/ ],
 );
+# Test a pseudoprime larger than 2^32.
+push @{$pseudoprimes{2}}, 75792980677 if $use64;
 my $num_pseudoprimes = 0;
 foreach my $ppref (values %pseudoprimes) {
   push @composites, @$ppref;
@@ -221,10 +223,13 @@ plan tests => 1 +
               2*scalar(keys %pivals_small) + scalar(keys %nthprimes_small) +
               4 + scalar(keys %pseudoprimes) +
               scalar(keys %eivals) + scalar(keys %livals) + scalar(keys 
%rvals) +
-              1 + 1 +
+              1 + 1 +    # factor
+              8 + 4*3 +  # factoring subs
+              10 +       # AKS
               0;
 
 use Math::Prime::Util qw/primes prime_count_approx prime_count_lower/;
+use Math::BigInt try => 'GMP';
 require_ok 'Math::Prime::Util::PP';
     # This function skips some setup
     undef *primes;
@@ -238,6 +243,7 @@ require_ok 'Math::Prime::Util::PP';
     *prev_prime     = \&Math::Prime::Util::PP::prev_prime;
 
     *miller_rabin   = \&Math::Prime::Util::PP::miller_rabin;
+    *is_aks_prime   = \&Math::Prime::Util::PP::is_aks_prime;
 
     *factor         = \&Math::Prime::Util::PP::factor;
 
@@ -398,6 +404,70 @@ while (my($n, $rin) = each (%rvals)) {
   is_deeply( \@gotfactor, \@expfactor, "test factoring for $ntests 
composites");
 }
 
+# The PP factor code does small trials, then loops doing 64k rounds of HOLF
+# if the composite is less than a half word, followed by 64k rounds each of
+# prho with a = {3,5,7,11,13}.  Most numbers are handled by these.  The ones
+# that aren't end up being too slow for us to put in a test.  So we'll try
+# running the various factoring methods manually.
+{
+  is_deeply( [ sort {$a<=>$b} Math::Prime::Util::PP::holf_factor(403) ],
+             [ 13, 31 ],
+             "holf(403)" );
+  is_deeply( [ sort {$a<=>$b} Math::Prime::Util::PP::prho_factor(403) ],
+             [ 13, 31 ],
+             "prho(403)" );
+  is_deeply( [ sort {$a<=>$b} Math::Prime::Util::PP::pbrent_factor(403) ],
+             [ 13, 31 ],
+             "pbrent(403)" );
+  is_deeply( [ sort {$a<=>$b} Math::Prime::Util::PP::pminus1_factor(403) ],
+             [ 13, 31 ],
+             "pminus1(403)" );
+  is_deeply( [ sort {$a<=>$b} Math::Prime::Util::PP::prho_factor(851981) ],
+             [ 13, 65537 ],
+             "prho(851981)" );
+  is_deeply( [ sort {$a<=>$b} Math::Prime::Util::PP::pbrent_factor(851981) ],
+             [ 13, 65537 ],
+             "pbrent(851981)" );
+  my $n64 = $use64 ? 55834573561 : Math::BigInt->new("55834573561");
+  is_deeply( [ sort {$a<=>$b} Math::Prime::Util::PP::prho_factor($n64) ],
+             [ 13, 4294967197 ],
+             "prho(55834573561)" );
+  is_deeply( [ sort {$a<=>$b} Math::Prime::Util::PP::pbrent_factor($n64) ],
+             [ 13, 4294967197 ],
+             "pbrent(55834573561)" );
+  # 1013 4294967197 4294967291
+  my $nbig = Math::BigInt->new("18686551294184381720251");
+  my @nfac;
+  @nfac = sort {$a<=>$b} Math::Prime::Util::PP::holf_factor($nbig);
+  is(scalar @nfac, 2, "holf finds a factor of 18686551294184381720251");
+  is($nfac[0] * $nfac[1], $nbig, "holf found a correct factor");
+  ok($nfac[0] != 1 && $nfac[1] != 1, "holf didn't return a degenerate factor");
+  @nfac = sort {$a<=>$b} Math::Prime::Util::PP::prho_factor($nbig);
+  is(scalar @nfac, 2, "prho finds a factor of 18686551294184381720251");
+  is($nfac[0] * $nfac[1], $nbig, "prho found a correct factor");
+  ok($nfac[0] != 1 && $nfac[1] != 1, "prho didn't return a degenerate factor");
+  @nfac = sort {$a<=>$b} Math::Prime::Util::PP::pbrent_factor($nbig);
+  is(scalar @nfac, 2, "pbrent finds a factor of 18686551294184381720251");
+  is($nfac[0] * $nfac[1], $nbig, "pbrent found a correct factor");
+  ok($nfac[0] != 1 && $nfac[1] != 1, "pbrent didn't return a degenerate 
factor");
+  @nfac = sort {$a<=>$b} Math::Prime::Util::PP::pminus1_factor($nbig);
+  is(scalar @nfac, 2, "pminus1 finds a factor of 18686551294184381720251");
+  is($nfac[0] * $nfac[1], $nbig, "pminus1 found a correct factor");
+  ok($nfac[0] != 1 && $nfac[1] != 1, "pminus1 didn't return a degenerate 
factor");
+}
+
+##### AKS primality test.  Be very careful with performance.
+is( is_aks_prime(1), 0, "AKS: 1 is composite (less than 2)" );
+is( is_aks_prime(2), 1, "AKS: 2 is prime" );
+is( is_aks_prime(3), 1, "AKS: 3 is prime" );
+is( is_aks_prime(4), 0, "AKS: 4 is composite" );
+is( is_aks_prime(64), 0, "AKS: 64 is composite (perfect power)" );
+is( is_aks_prime(65), 0, "AKS: 65 is composite (caught in trial)" );
+is( is_aks_prime(23), 1, "AKS: 23 is prime (r >= n)" );
+is( is_aks_prime(101), 1, "AKS: 101 is prime (passed anr test)" );
+is( is_aks_prime(70747), 0, "AKS: 70747 is composite (n mod r)" );
+is( is_aks_prime(74513), 0, "AKS: 74513 is composite (failed anr test)" );
+
 ###############################################################################
 
 sub parse_range {

-- 
Alioth's /usr/local/bin/git-commit-notice on 
/srv/git.debian.org/git/pkg-perl/packages/libmath-prime-util-perl.git

_______________________________________________
Pkg-perl-cvs-commits mailing list
Pkg-perl-cvs-commits@lists.alioth.debian.org
http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/pkg-perl-cvs-commits

Reply via email to