This is an automated email from the git hooks/post-receive script.
ppm-guest pushed a commit to annotated tag v0.32
in repository libmath-prime-util-perl.
commit 736a704cdafb28a7c256055a3bd45cc50f91e233
Author: Dana Jacobsen <d...@acm.org>
Date: Wed Oct 2 15:41:37 2013 -0700
Adjust some benchmarks
---
examples/bench-primearray.pl | 66 ++++++++++++++++++-----
xt/primality-proofs.pl | 122 ++++++++++++++++++++++++-------------------
2 files changed, 121 insertions(+), 67 deletions(-)
diff --git a/examples/bench-primearray.pl b/examples/bench-primearray.pl
index ca6aba5..88f0ff6 100755
--- a/examples/bench-primearray.pl
+++ b/examples/bench-primearray.pl
@@ -13,21 +13,12 @@ my ($s, $nlimit, $ilimit, $expect);
if (1) {
print '-' x 79, "\n";
-print "summation to 100k\n";
-print "Note: MPU::PrimeArray is about 30x faster than MPTA here.\n";
-print " It seems slices are the fastest way to access the tied array\n";
-print " Math::NumSeq::Primes is reasonable fast (not random access)\n";
-print " MPU's forprimes smashes everything else (not random access)\n";
+print "summation to 100k, looking for best methods (typically slice)\n";
$nlimit = 100000;
$ilimit = prime_count($nlimit)-1;
$expect = 0; forprimes { $expect += $_ } $nlimit;
cmpthese($count,{
- 'primes' => sub { $s=0; $s += $_ for @{primes($nlimit)}; die unless $s ==
$expect; },
- 'forprimes' => sub { $s=0; forprimes { $s += $_ } $nlimit; die unless $s ==
$expect; },
- 'iterator' => sub { $s=0; my $it = prime_iterator();
- $s += $it->() for 0..$ilimit;
- die unless $s == $expect; },
'pa index' => sub { $s=0; tie my @primes, "Math::Prime::Util::PrimeArray";
$s += $primes[$_] for 0..$ilimit;
die unless $s == $expect; },
@@ -43,11 +34,59 @@ cmpthese($count,{
'pa shift' => sub { $s=0; tie my @primes, "Math::Prime::Util::PrimeArray";
while ((my $p = shift @primes) <= $nlimit) { $s += $p; }
die unless $s == $expect; },
- 'numseq' => sub { $s=0; my $seq = Math::NumSeq::Primes->new;
+});
+}
+
+if (1) {
+print '-' x 79, "\n";
+print "summation to 100k, looking for best MPTA extension (typically ~1000)\n";
+$nlimit = 100000;
+$ilimit = prime_count($nlimit)-1;
+$expect = 0; forprimes { $expect += $_ } $nlimit;
+
+cmpthese($count,{
+ 'MPTA' => sub { $s=0; tie my @primes, "Math::Prime::TiedArray";
+ $s += $primes[$_] for 0..$ilimit;
+ die unless $s == $expect; },
+ 'MPTA 400' => sub { $s=0; tie my @primes, "Math::Prime::TiedArray",
extend_step => 400;
+ $s += $primes[$_] for 0..$ilimit;
+ die unless $s == $expect; },
+ 'MPTA 1000' => sub { $s=0; tie my @primes, "Math::Prime::TiedArray",
extend_step => 1000;
+ $s += $primes[$_] for 0..$ilimit;
+ die unless $s == $expect; },
+ 'MPTA 4000' => sub { $s=0; tie my @primes, "Math::Prime::TiedArray",
extend_step => 4000;
+ $s += $primes[$_] for 0..$ilimit;
+ die unless $s == $expect; },
+});
+}
+
+if (1) {
+print '-' x 79, "\n";
+print "summation to 100k\n";
+print "Note: MPU::PrimeArray is about 30x faster than MPTA here.\n";
+print " Math::NumSeq::Primes is reasonable fast (not random access)\n";
+print " MPU's forprimes smashes everything else (not random access)\n";
+$nlimit = 100000;
+$ilimit = prime_count($nlimit)-1;
+$expect = 0; forprimes { $expect += $_ } $nlimit;
+
+cmpthese($count,{
+ 'primes' => sub { $s=0; $s += $_ for @{primes($nlimit)}; die unless $s ==
$expect; },
+ 'forprimes' => sub { $s=0; forprimes { $s += $_ } $nlimit; die unless $s ==
$expect; },
+ 'iterator' => sub { $s=0; my $it = prime_iterator();
+ $s += $it->() for 0..$ilimit;
+ die unless $s == $expect; },
+ 'OO iter' => sub { $s=0; my $it = prime_iterator_object();
+ $s += $it->iterate() for 0..$ilimit;
+ die unless $s == $expect; },
+ 'pa slice' => sub { $s=0; tie my @primes, "Math::Prime::Util::PrimeArray";
+ $s += $_ for @primes[0..$ilimit];
+ die unless $s == $expect; },
+ 'NumSeq' => sub { $s=0; my $seq = Math::NumSeq::Primes->new;
while (1) { my($undev,$v) = $seq->next; last if $v >
$nlimit; $s += $v; }
die $s unless $s == $expect; },
# This was slightly faster than slice or shift
- 'tiedarray' => sub { $s=0; tie my @primes, "Math::Prime::TiedArray",
extend_step => 1000;
+ 'MPTA' => sub { $s=0; tie my @primes, "Math::Prime::TiedArray",
extend_step => 1000;
$s += $primes[$_] for 0..$ilimit;
die unless $s == $expect; },
});
@@ -101,6 +140,9 @@ cmpthese($count,{
'pa index' => sub { $s=0; tie my @primes, "Math::Prime::Util::PrimeArray";
$s += $primes[$_] for reverse 0..$ilimit;
die unless $s == $expect; },
+ 'OO iter' => sub { $s=0; my $it = prime_iterator_object($nlimit);
+ $s += $it->prev->value() for 0..$ilimit;
+ die unless $s == $expect; },
'tiedarray' => sub { $s=0; tie my @primes, "Math::Prime::TiedArray",
extend_step => 1000;
$s += $primes[$_] for reverse 0..$ilimit;
die unless $s == $expect; },
diff --git a/xt/primality-proofs.pl b/xt/primality-proofs.pl
index c4cdf85..cfaaf41 100755
--- a/xt/primality-proofs.pl
+++ b/xt/primality-proofs.pl
@@ -6,77 +6,89 @@ use Math::BigInt lib=>"GMP";
$|++;
-# The number of tests performed. 71 makes a nice display for 80 columns.
-my $num = 71;
-# Select random primes with sizes randomly between 4 and this number of bits.
-my $size = 500;
-# Which selection method? Ideally we would use some independent code. Time
-# for one thousand random primes from rand(4-300) or rand(4-600) bits:
-#
-# 300bits 600bits which
-# 2sec 6sec mpu (with mpu::gmp installed)
-# 31sec 124sec pari
-# 97sec 254sec cpmaurer
-#
-# We don't seem to have any practical choice other than MPU's
-# random_nbit_prime as the other random prime code is just so slow.
-#
-my $prime_method = 'mpu'; # mpu, pari, or cpmaurer
+print "random prime proofs: 50, 100, 200, 300, 400 +/- 50 digits\n";
+test_proofs( 4, 100, 71, 'mpu'); print "\n";
+test_proofs( 50, 150, 71, 'mpu'); print "\n";
+test_proofs(150, 250, 71, 'mpu'); print "\n";
+test_proofs(250, 350, 71, 'mpu'); print "\n";
+test_proofs(350, 450, 71, 'mpu'); print "\n";
-my @ns;
-print "Generate ";
-die "invalid size, must be > 4" unless $size > 4;
-foreach my $i (1..$num) {
- my $bits = int(rand($size-4)) + 4;
- my $n;
+# size: random primes with bit sizes randomly between 4 and this number
+# num: this many tests performed. 71 makes a nice 80-column display
+# method: how to generate random primes:
+# Ideally we would use some independent code. Time for one thousand
+# random primes from rand(4-300) or rand(4-600) bits:
+# 300bits 600bits which
+# 2sec 6sec mpu (with mpu::gmp installed)
+# 31sec 124sec pari
+# 97sec 254sec cpmaurer
+# We don't seem to have any practical choice other than MPU's
+# random_nbit_prime as the other random prime code is just so slow.
+sub test_proofs {
+ my($minsize, $size, $num, $prime_method) = @_;
if ($prime_method eq 'cpmaurer') {
require Crypt::Primes;
- $n = Crypt::Primes::maurer(Size=>$bits);
} elsif ($prime_method eq 'pari') {
require Math::Pari;
require Crypt::Random;
- # This is ~4x faster, has awful distribution. Still much slower than MPU.
- # $n = Math::Pari::nextprime( ...makerandom... );
- do { $n = Crypt::Random::makerandom(Size=>$bits,Strength=>0); }
- while !Math::Pari::isprime($n);
} elsif ($prime_method eq 'mpu') {
- $n = random_nbit_prime($bits);
+ # nothing
} else {
die "Unknown random prime generation method\n";
}
- push @ns, Math::BigInt->new("$n");
- # print a number corresponding to hundreds of bits
- print int(3.322*length("$n")/100);
-}
-print "\n";
+ my @ns;
+ print "Generate ";
+ $minsize = 4 if $minsize < 4;
+ $minsize = $size if $minsize > $size;
+ die "invalid size, must be > 4" unless $size > 4;
+ foreach my $i (1..$num) {
+ my $bits = int(rand($size-$minsize)) + $minsize;
+ my $n;
+ if ($prime_method eq 'cpmaurer') {
+ $n = Crypt::Primes::maurer(Size=>$bits);
+ } elsif ($prime_method eq 'pari') {
+ # This is ~4x faster, has awful distribution. Still much slower than
MPU.
+ # $n = Math::Pari::nextprime( ...makerandom... );
+ do { $n = Crypt::Random::makerandom(Size=>$bits,Strength=>0); }
+ while !Math::Pari::isprime($n);
+ } else {
+ $n = random_nbit_prime($bits);
+ }
+ push @ns, Math::BigInt->new("$n");
+ # print a number corresponding to hundreds of bits
+ print int(3.322*length("$n")/100);
+ }
+ print "\n";
-my @certs;
-print "Prove ";
-foreach my $n (@ns) {
- my ($isp,$cert) = is_provable_prime_with_cert($n);
- die "$n is reported as $isp\n" unless $isp == 2;
- push @certs, [$n, $cert];
- print proof_mark($cert);
-}
-print "\n";
+ my @certs;
+ print "Prove ";
+ foreach my $n (@ns) {
+ my ($isp,$cert) = is_provable_prime_with_cert($n);
+ die "$n is reported as $isp\n" unless $isp == 2;
+ push @certs, [$n, $cert];
+ print proof_mark($cert);
+ }
+ print "\n";
-print "Verify ";
-prime_set_config(verbose=>1);
-foreach my $certn (@certs) {
- my $v = verify_prime($certn->[1]);
- print proof_mark($certn->[1]);
- next if $v;
- print "\n\n$certn->[0] didn't verify!\n\n";
- {
- my $c = $certn->[1];
- $c =~ s/^/ /smg;
- print $c;
+ print "Verify ";
+ prime_set_config(verbose=>1);
+ foreach my $certn (@certs) {
+ my $v = verify_prime($certn->[1]);
+ print proof_mark($certn->[1]);
+ next if $v;
+ print "\n\n$certn->[0] didn't verify!\n\n";
+ {
+ my $c = $certn->[1];
+ $c =~ s/^/ /smg;
+ print $c;
+ }
+ die;
}
- die;
+ prime_set_config(verbose=>0);
+ print "\n";
}
-print "\n";
sub proof_mark {
my $cert = shift;
--
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
