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