This is an automated email from the git hooks/post-receive script. ppm-guest pushed a commit to annotated tag v0.25 in repository libmath-prime-util-perl.
commit c72237b008b6580aa5f662686184a693c732a9b1 Author: Dana Jacobsen <d...@acm.org> Date: Wed Mar 13 14:23:43 2013 -0700 Tweak factoring and factor tests based on coverage analysis --- Changes | 4 ++-- TODO | 3 --- factor.c | 18 ++++++++---------- t/50-factoring.t | 3 ++- 4 files changed, 12 insertions(+), 16 deletions(-) diff --git a/Changes b/Changes index 390d496..0102f37 100644 --- a/Changes +++ b/Changes @@ -2,8 +2,8 @@ Revision history for Perl extension Math::Prime::Util. 0.25 xx March 2013 - - Speed up p-1 stage 2 factoring. This makes factor() about 20% faster - for 19 digit semiprimes. + - Speed up p-1 stage 2 factoring. Combined with some minor changes to the + general factoring combination, ~20% faster for 19 digit semiprimes. - New internal macro to loop over primary sieve starting at 2. Simplifies code in quite a few places. diff --git a/TODO b/TODO index a75cc17..b0be486 100644 --- a/TODO +++ b/TODO @@ -19,9 +19,6 @@ - finish test suite for bignum. Work on making it faster. -- After the factoring changes, we need to use Devel::Cover again to ferret - out numbers that pass the early tests. - - Test all routines for numbers on word-size boundary, or ranges that cross. - Test all functions return either native or bigints. Functions that return diff --git a/factor.c b/factor.c index 26622cf..44f36bd 100644 --- a/factor.c +++ b/factor.c @@ -49,34 +49,31 @@ int factor(UV n, UV *factors) UV const br_rounds = ((n>>29) < 100000) ? 1500 : 1500; UV const sq_rounds = 80000; /* 20k 91%, 40k 98%, 80k 99.9%, 120k 99.99% */ - /* About 94% of random inputs are factored with this pbrent call */ + /* 99.7% of 32-bit, 94% of 64-bit random inputs factored here */ if (!split_success) { split_success = pbrent_factor(n, tofac_stack+ntofac, br_rounds, 3)-1; if (verbose) { if (split_success) printf("pbrent 1: %"UVuf" %"UVuf"\n", tofac_stack[ntofac], tofac_stack[ntofac+1]); else printf("pbrent 0\n"); } } - /* SQUFOF with these parameters gets 95% of what's left. */ + /* SQUFOF with these parameters gets 99.9% of everything left */ if (!split_success && n < (UV_MAX>>3)) { split_success = racing_squfof_factor(n,tofac_stack+ntofac, sq_rounds)-1; if (verbose) printf("rsqufof %d\n", split_success); } - /* Perhaps prho using different parameters will find it */ - if (!split_success) { - split_success = pbrent_factor(n, tofac_stack+ntofac, 800, 5)-1; - if (verbose) printf("pbrent5 %d\n", split_success); - } + /* At this point we should only have 16+ digit semiprimes. */ /* This p-1 gets about 2/3 of what makes it through the above */ if (!split_success) { split_success = pminus1_factor(n, tofac_stack+ntofac, 5000, 80000)-1; if (verbose) printf("pminus1 %d\n", split_success); } - /* Some rounds of HOLF, good for close to perfect squares */ + /* Some rounds of HOLF, good for close to perfect squares which are + * the worst case for the next step */ if (!split_success) { split_success = holf_factor(n, tofac_stack+ntofac, 2000)-1; if (verbose) printf("holf %d\n", split_success); } - /* Less than 0.1% of random inputs make it here */ + /* The catch-all. Should factor anything. */ if (!split_success) { - split_success = pbrent_factor(n, tofac_stack+ntofac, 256*1024, 7)-1; + split_success = prho_factor(n, tofac_stack+ntofac, 256*1024)-1; if (verbose) printf("long prho %d\n", split_success); } @@ -277,6 +274,7 @@ static int is_perfect_square(UV n, UV* sqrtn) if ((m*0xabf1a3a7) & (m*0x2612bf93) & 0x45854000) return 0; /* 99.92% of non-squares are rejected now */ #else + /* It may be faster to skip these */ m = n % 63; if ((m*0x3d491df7) & (m*0xc824a9f9) & 0x10f14008) return 0; #endif diff --git a/t/50-factoring.t b/t/50-factoring.t index 35cf133..2d367a7 100644 --- a/t/50-factoring.t +++ b/t/50-factoring.t @@ -32,7 +32,7 @@ my @testn = qw/0 1 2 3 4 5 6 7 8 16 57 64 377 9592 30107 78498 664579 5761455 808 2727 12625 34643 134431 221897 496213 692759 1228867 2231139 2463289 3008891 5115953 6961021 8030207 10486123 10893343 12327779 701737021 - 549900 + 549900 10000142 /; my @testn64 = qw/37607912018 346065536839 600851475143 @@ -42,6 +42,7 @@ my @testn64 = qw/37607912018 346065536839 600851475143 9007199254740991 9007199254740992 9007199254740993 6469693230 200560490130 7420738134810 304250263527210 13082761331670030 614889782588491410 + 440091295252541 5333042142001571 /; push @testn, @testn64 if $use64; -- 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