This is an automated email from the git hooks/post-receive script. ppm-guest pushed a commit to annotated tag v0.11 in repository libmath-prime-util-perl.
commit e885753e7fe1ebaea79ec0312bd1eba560726265 Author: Dana Jacobsen <d...@acm.org> Date: Mon Jul 23 00:53:58 2012 -0600 Racing SQUFOF & other UV factoring changes --- Changes | 3 ++- XS.xs | 38 +++++++++++++++++++++++++++++++++++--- examples/bench-factor-extra.pl | 2 ++ examples/bench-miller-rabin.pl | 14 ++++++++++++-- examples/bench-pp-count.pl | 0 examples/bench-pp-isprime.pl | 0 examples/bench-pp-sieve.pl | 0 lib/Math/Prime/Util.pm | 3 +++ 8 files changed, 54 insertions(+), 6 deletions(-) diff --git a/Changes b/Changes index ee18187..617ed05 100644 --- a/Changes +++ b/Changes @@ -1,12 +1,13 @@ Revision history for Perl extension Math::Prime::Util. -0.11 19 July 2012 +0.11 23 July 2012 - Turn of threading tests on Cygwin, as threads on some Cygwin platforms give random panics (my Win7 64-bit works fine, XP 32-bit does not). - Use pow instead of exp2 -- some systems don't have exp2. - Fix compile issues on MSC, thanks to Sisyphus. - some bigint/bignum changes (next_prime and math functions). - speed up and enhance some tests. + - Add racing SQUFOF for UVs, also add a little more trial division. 0.10 16 July 2012 diff --git a/XS.xs b/XS.xs index 22292f8..7236fa6 100644 --- a/XS.xs +++ b/XS.xs @@ -200,7 +200,7 @@ _XS_factor(IN UV n) XPUSHs(sv_2mortal(newSVuv( n ))); /* If n is 0-3, we're done. */ } else { int const verbose = 0; - UV tlim = 53; /* Below this we've checked with trial division */ + UV tlim = 101; /* Below this we've checked with trial division */ UV tofac_stack[MPU_MAX_FACTORS+1]; UV factored_stack[MPU_MAX_FACTORS+1]; int ntofac = 0; @@ -225,6 +225,21 @@ _XS_factor(IN UV n) while ( (n%43) == 0 ) { n /= 43; XPUSHs(sv_2mortal(newSVuv( 43 ))); } while ( (n%47) == 0 ) { n /= 47; XPUSHs(sv_2mortal(newSVuv( 47 ))); } } + if ( (n >= UVCONST(53*53)) && (gcd_ui(n, UVCONST(907383479) != 1)) ) { + while ( (n%53) == 0 ) { n /= 53; XPUSHs(sv_2mortal(newSVuv( 53 ))); } + while ( (n%59) == 0 ) { n /= 59; XPUSHs(sv_2mortal(newSVuv( 59 ))); } + while ( (n%61) == 0 ) { n /= 61; XPUSHs(sv_2mortal(newSVuv( 61 ))); } + while ( (n%67) == 0 ) { n /= 67; XPUSHs(sv_2mortal(newSVuv( 67 ))); } + while ( (n%71) == 0 ) { n /= 71; XPUSHs(sv_2mortal(newSVuv( 71 ))); } + } + if ( (n >= UVCONST(73*73)) && (gcd_ui(n, UVCONST(4132280413) != 1)) ) { + while ( (n%73) == 0 ) { n /= 73; XPUSHs(sv_2mortal(newSVuv( 73 ))); } + while ( (n%79) == 0 ) { n /= 79; XPUSHs(sv_2mortal(newSVuv( 79 ))); } + while ( (n%83) == 0 ) { n /= 83; XPUSHs(sv_2mortal(newSVuv( 83 ))); } + while ( (n%89) == 0 ) { n /= 89; XPUSHs(sv_2mortal(newSVuv( 89 ))); } + while ( (n%97) == 0 ) { n /= 97; XPUSHs(sv_2mortal(newSVuv( 97 ))); } + } + do { /* loop over each remaining factor */ /* In theory we can try to minimize work using is_definitely_prime(n) * but in practice it seems slower. */ @@ -235,15 +250,27 @@ _XS_factor(IN UV n) ((n>>29) < 100000) ? 250000 : 600000; + #if 0 + if (!split_success && n < 1000000) { + nfactored += trial_factor(n, factored_stack+nfactored, 0); + n = 1; + break; + } + #endif + /* Small factors will be found quite rapidly with this */ if (!split_success) { split_success = pbrent_factor(n, tofac_stack+ntofac, 1500)-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 does great with big numbers */ if (!split_success) { - split_success = squfof_factor(n, tofac_stack+ntofac, sq_rounds)-1; + /* SQUFOF does very well with what's left after TD and Rho. + * On such input, racing SQUFOF is ~40% faster and has better + * success, but has input size restrictions. */ + split_success = (n > (UV_MAX >> 3)) + ? squfof_factor(n, tofac_stack+ntofac, sq_rounds)-1 + : racing_squfof_factor(n, tofac_stack+ntofac, 0)-1; if (verbose) printf("squfof %d\n", split_success); } @@ -354,6 +381,11 @@ squfof_factor(IN UV n, IN UV maxrounds = 4*1024*1024) SIMPLE_FACTOR(squfof_factor, n, maxrounds); void +rsqufof_factor(IN UV n) + PPCODE: + SIMPLE_FACTOR(racing_squfof_factor, n, 0); + +void pbrent_factor(IN UV n, IN UV maxrounds = 4*1024*1024) PPCODE: SIMPLE_FACTOR(pbrent_factor, n, maxrounds); diff --git a/examples/bench-factor-extra.pl b/examples/bench-factor-extra.pl index 160f759..8a280da 100755 --- a/examples/bench-factor-extra.pl +++ b/examples/bench-factor-extra.pl @@ -36,6 +36,7 @@ sub test_at_digits { $nfactored{'pbrent'} += $calc_nfacs->(Math::Prime::Util::pbrent_factor($_, $rounds)); $nfactored{'pminus1'} += $calc_nfacs->(Math::Prime::Util::pminus1_factor($_, $rounds)); $nfactored{'squfof'} += $calc_nfacs->(Math::Prime::Util::squfof_factor($_, $sqrounds)); + $nfactored{'rsqufof'} += $calc_nfacs->(Math::Prime::Util::rsqufof_factor($_)); #$nfactored{'trial'} += $calc_nfacs->(Math::Prime::Util::trial_factor($_)); #$nfactored{'fermat'} += $calc_nfacs->(Math::Prime::Util::fermat_factor($_, $rounds)); $nfactored{'holf'} += $calc_nfacs->(Math::Prime::Util::holf_factor($_, $hrounds)); @@ -55,6 +56,7 @@ sub test_at_digits { "fermat" => sub { Math::Prime::Util::fermat_factor($_, $rounds) for @nums }, "holf" => sub { Math::Prime::Util::holf_factor($_, $hrounds) for @nums }, "squfof" => sub { Math::Prime::Util::squfof_factor($_, $sqrounds) for @nums }, + "rsqufof" => sub { Math::Prime::Util::rsqufof_factor($_) for @nums }, "trial" => sub { Math::Prime::Util::trial_factor($_) for @nums }, }; delete $lref->{'fermat'} if $digits >= 9; diff --git a/examples/bench-miller-rabin.pl b/examples/bench-miller-rabin.pl index 02c4478..ec11aab 100755 --- a/examples/bench-miller-rabin.pl +++ b/examples/bench-miller-rabin.pl @@ -1,9 +1,10 @@ #!/usr/bin/env perl use strict; use warnings; -#use Math::Primality; +use Math::Primality; use Math::Prime::XS; use Math::Prime::Util '-nobigint'; +use Math::Prime::Util::GMP; #use Math::Prime::FastSieve; use Benchmark qw/:all/; use List::Util qw/min max/; @@ -30,7 +31,16 @@ sub test_at_digits { print "miller_rabin for 1000 random $digits-digit numbers ($min_num - $max_num)\n"; cmpthese($count,{ - 'M::P::U' => sub { Math::Prime::Util::miller_rabin($_,2,3,5,7,11,13,17) for @nums }, + 'MPU' => sub { Math::Prime::Util::is_strong_pseudoprime($_,2,3,5,7,11,13,17) for @nums }, + 'MPU GMP' => sub { Math::Prime::Util::GMP::is_strong_pseudoprime($_,2,3,5,7,11,13,17) for @nums }, + 'M:Primality' => sub { for (@nums) { + Math::Primality::is_strong_pseudoprime($_,2) && + Math::Primality::is_strong_pseudoprime($_,3) && + Math::Primality::is_strong_pseudoprime($_,5) && + Math::Primality::is_strong_pseudoprime($_,7) && + Math::Primality::is_strong_pseudoprime($_,11) && + Math::Primality::is_strong_pseudoprime($_,13) && + Math::Primality::is_strong_pseudoprime($_,17); } }, }); print "\n"; } diff --git a/examples/bench-pp-count.pl b/examples/bench-pp-count.pl old mode 100644 new mode 100755 diff --git a/examples/bench-pp-isprime.pl b/examples/bench-pp-isprime.pl old mode 100644 new mode 100755 diff --git a/examples/bench-pp-sieve.pl b/examples/bench-pp-sieve.pl old mode 100644 new mode 100755 diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm index e92c858..85bb493 100644 --- a/lib/Math/Prime/Util.pm +++ b/lib/Math/Prime/Util.pm @@ -1870,7 +1870,10 @@ same advantages and disadvantages as Fermat's method. =head2 squfof_factor +=head2 rsqufof_factor + my @factors = squfof_factor($n); + my @factors = rsqufof_factor($n); # racing multiplier version Produces factors, not necessarily prime, of the positive number input. An optional number of rounds can be given as a second parameter. It is possible -- 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