This is an automated email from the git hooks/post-receive script. ppm-guest pushed a commit to annotated tag v0.33 in repository libmath-prime-util-perl.
commit ee69ab7813cf44f75ddd3fd557e0a004b459cbe5 Author: Dana Jacobsen <d...@acm.org> Date: Tue Oct 29 16:10:00 2013 -0700 Speedups for pure perl testing --- lib/Math/Prime/Util.pm | 15 +++++++-------- lib/Math/Prime/Util/PP.pm | 18 +++++++++++------- lib/Math/Prime/Util/PrimalityProving.pm | 1 + t/19-moebius.t | 11 +++++++++-- t/50-factoring.t | 9 +++++++++ t/81-bignum.t | 4 ++-- 6 files changed, 39 insertions(+), 19 deletions(-) diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm index dae7acb..600ed21 100644 --- a/lib/Math/Prime/Util.pm +++ b/lib/Math/Prime/Util.pm @@ -1418,10 +1418,12 @@ sub mertens { my $inner_sum = 0; my $lower = int($u/$m) + 1; my $last_nmk = int($n/($m*$lower)); - my ($this_k, $next_k) = (0, int($n/($m*1))); + my ($denom, $this_k, $next_k) = ($m, 0, int($n/($m*1))); for my $nmk (1 .. $last_nmk) { - $this_k = $next_k; - $next_k = int($n/($m*($nmk+1))); + $denom += $m; + $this_k = int($n/$denom); + next if $this_k == $next_k; + ($this_k, $next_k) = ($next_k, $this_k); $inner_sum += $M[$nmk] * ($this_k - $next_k); } $sum -= $mu[$m] * $inner_sum; @@ -1678,12 +1680,9 @@ sub partitions { if ($_HAVE_GMP && defined &Math::Prime::Util::GMP::partitions) { return Math::BigInt->new( '' . Math::Prime::Util::GMP::partitions($n) ); } - my @part = (Math::BigInt->bone); - my @pent = (1); my $d = int(sqrt($n+1)); - foreach my $i ( 1 .. $d ) { - push @pent, int(($i*(3*$i+1))/2), int((($i+1)*(3*$i+2))/2); - } + my @pent = (1, map { ($_*(3*$_+1))>>1, (($_+1)*(3*$_+2))>>1 } 1 .. $d); + my @part = (Math::BigInt->bone); foreach my $j (scalar @part .. $n) { my ($psum1, $psum2, $k) = (Math::BigInt->bzero, Math::BigInt->bzero, 1); foreach my $p (@pent) { diff --git a/lib/Math/Prime/Util/PP.pm b/lib/Math/Prime/Util/PP.pm index 6d3d085..67bc7e7 100644 --- a/lib/Math/Prime/Util/PP.pm +++ b/lib/Math/Prime/Util/PP.pm @@ -145,10 +145,14 @@ sub _is_prime7 { # n must not be divisible by 2, 3, or 5 return 2; } - return 0 if !($n % 7) || !($n % 11) || !($n % 13) || !($n % 17) || - !($n % 19) || !($n % 23) || !($n % 29) || !($n % 31) || - !($n % 37) || !($n % 41) || !($n % 43) || !($n % 47) || - !($n % 53) || !($n % 59); + if (ref($n) eq 'Math::BigInt') { + return 0 unless Math::BigInt::bgcd($n, "64092011671807087969")->is_one; + } else { + return 0 if !($n % 7) || !($n % 11) || !($n % 13) || !($n % 17) || + !($n % 19) || !($n % 23) || !($n % 29) || !($n % 31) || + !($n % 37) || !($n % 41) || !($n % 43) || !($n % 47) || + !($n % 53) || !($n % 59); + } if ($n <= 1_000_000) { my $limit = int(sqrt($n)); @@ -792,9 +796,7 @@ sub miller_rabin { _validate_positive_integer($n); croak "No bases given to miller_rabin" unless @bases; - return 0 if ($n == 0) || ($n == 1); - return 1 if ($n == 2) || ($n == 3); - return 0 if !($n % 2); + return $n >> 1 if $n <= 3; # Die on invalid bases foreach my $base (@bases) { croak "Base $base is invalid" if $base < 2 } @@ -803,6 +805,7 @@ sub miller_rabin { if ( ref($n) eq 'Math::BigInt' ) { + return 0 if $n->is_even; my $nminus1 = $n->copy->bdec(); my $s = 0; my $d = $nminus1->copy; @@ -829,6 +832,7 @@ sub miller_rabin { } else { + return 0 unless $n & 1; my $s = 0; my $d = $n - 1; while ( ($d & 1) == 0 ) { diff --git a/lib/Math/Prime/Util/PrimalityProving.pm b/lib/Math/Prime/Util/PrimalityProving.pm index 9e73fd5..83c72eb 100644 --- a/lib/Math/Prime/Util/PrimalityProving.pm +++ b/lib/Math/Prime/Util/PrimalityProving.pm @@ -129,6 +129,7 @@ sub primality_proof_bls75 { my @factors = (2); croak "BLS75 error: n-1 not even" unless $nm1->is_even(); my $trial_B = 20000; + $trial_B = 500 if ! prime_get_config->{'xs'}; { while ($B->is_even) { $B /= 2; $A *= 2; } my @tf = Math::Prime::Util::PP::trial_factor($B, $trial_B); diff --git a/t/19-moebius.t b/t/19-moebius.t index b5b5160..9db14d4 100644 --- a/t/19-moebius.t +++ b/t/19-moebius.t @@ -41,6 +41,9 @@ my %big_mertens = ( 1000000 => 212, 10000000 => 1037, ); +if (!$extra && !Math::Prime::Util::prime_get_config->{'xs'}) { + delete $big_mertens{10000000}; +} if ($extra && $use64) { %big_mertens = ( %big_mertens, 2 => 0, # A087987, mertens at primorials @@ -143,7 +146,7 @@ my %chebyshev1 = ( 4 => 1.79175946922805, 5 => 3.40119738166216, 243 => 226.593507136467, - 1234567 => 1233272.80087825, + 123456 => 123034.091739914, ); my %chebyshev2 = ( 0 => 0, @@ -153,8 +156,12 @@ my %chebyshev2 = ( 4 => 2.484906649788, 5 => 4.0943445622221, 243 => 245.274469978683, - 1234567 => 1234515.17962833, + 123456 => 123435.148054491 ); +if ($extra) { + $chebyshev1{1234567} = 1233272.80087825; + $chebyshev2{1234567} = 1234515.17962833; +} my @A002322 = (0,1,1,2,2,4,2,6,2,6,4,10,2,12,6,4,4,16,6,18,4,6,10,22,2,20,12,18,6,28,4,30,8,10,16,12,6,36,18,12,4,40,6,42,10,12,22,46,4,42,20,16,12,52,18,20,6,18,28,58,4,60,30,6,16,12,10,66,16,22,12,70,6,72,36,20,18,30,12,78,4,54,40,82,6,16,42,28,10,88,12,12,22,30,46,36,8,96,42,30,20,100,16,102,12,12,52,106,18,108,20,36,12,112,18,44,28,12,58,48,4,110,60,40,30,100,6,126,32,42,12,130,10,18,66,36,16,136,22,138,12,46,70,60,12,28,72,42,36,148,20,150,18,48,30,60,12,156,78,52,8,66,54,162,40,20, [...] diff --git a/t/50-factoring.t b/t/50-factoring.t index 32af300..4cc339d 100644 --- a/t/50-factoring.t +++ b/t/50-factoring.t @@ -50,6 +50,15 @@ push @testn, @testn64 if $use64; push @testn, qw/9999986200004761 99999989237606677 999999866000004473/ if $use64 && $extra; +# For time savings, trim these if we're pure Perl. +if ( !$extra + && !Math::Prime::Util::prime_get_config->{'xs'} + && !Math::Prime::Util::prime_get_config->{'gmp'} ) { + @testn = grep { $_ != 10023859281455311421 + && $_ != 3369738766071892021 + } @testn; +} + my %all_factors = ( 1234567890 => [1,2,3,5,6,9,10,15,18,30,45,90,3607,3803,7214,7606,10821,11409,18035,19015,21642,22818,32463,34227,36070,38030,54105,57045,64926,68454,108210,114090,162315,171135,324630,342270,13717421,27434842,41152263,68587105,82304526,123456789,137174210,205761315,246913578,411522630,617283945,1234567890], 1032924637 => [1,6469,159673,1032924637], diff --git a/t/81-bignum.t b/t/81-bignum.t index 8301ca0..8fdd9c5 100644 --- a/t/81-bignum.t +++ b/t/81-bignum.t @@ -233,8 +233,8 @@ SKIP: { } ############################################################################### -is( liouville( 48981631802481400359696467), -1, "liouville(a x b x c) = -1" ); -is( liouville(16091004845064967313564246070637), 1, "liouville(a x b x c x d) = 1" ); +is( liouville( 560812147176208202656339069), -1, "liouville(a x b x c) = -1" ); +is( liouville(10571644062695614514374497899), 1, "liouville(a x b x c x d) = 1" ); ############################################################################### -- 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