This is an automated email from the git hooks/post-receive script. ppm-guest pushed a commit to annotated tag v0.13 in repository libmath-prime-util-perl.
commit c1a27551cf6c31426c28dc9cf514509aad209c02 Author: Dana Jacobsen <[email protected]> Date: Mon Nov 19 01:01:06 2012 -0800 Ready for next release --- Changes | 5 +++ MANIFEST | 1 + README | 17 +++++--- examples/parallel_fibprime.pl | 98 +++++++++++++++++++++++++++++++++++++++++++ lib/Math/Prime/Util.pm | 8 ++-- lib/Math/Prime/Util/PP.pm | 10 ++--- 6 files changed, 125 insertions(+), 14 deletions(-) diff --git a/Changes b/Changes index b6debc8..dde7860 100644 --- a/Changes +++ b/Changes @@ -1,5 +1,10 @@ Revision history for Perl extension Math::Prime::Util. +0.13 19 November 2012 + + - Fix an issue with prime count, and make prime count available as a + standalone program using primesieve. + 0.12 17 November 2012 - Add bin/primes.pl and bin/factor.pl diff --git a/MANIFEST b/MANIFEST index 2c17b15..66357cb 100644 --- a/MANIFEST +++ b/MANIFEST @@ -46,6 +46,7 @@ examples/test-pcapprox.pl examples/sophie_germain.pl examples/twin_primes.pl examples/find_mr_bases.pl +examples/parallel_fibprime.pl examples/test-bpsw.pl examples/test-euler-pari.pl examples/test-factor-gnufactor.pl diff --git a/README b/README index edba76a..f6bdd86 100644 --- a/README +++ b/README @@ -1,14 +1,21 @@ -Math::Prime::Util version 0.12 +Math::Prime::Util version 0.13 A set of utilities related to prime numbers. These include multiple sieving methods, is_prime, prime_count, nth_prime, approximations and bounds for the prime_count and nth prime, next_prime and prev_prime, moebius and totient functions, integer factoring, and more. -The default sieving and factoring are intended to be the fastest on CPAN, -including Math::Prime::XS, Math::Prime::FastSieve, Math::Factor::XS, -Math::Primality, and Math::Prime::TiedArray. For non-bignums, it is typically -faster than Math::Pari (and doesn't require Pari to be installed). +The default sieving and factoring are intended to be the fastest on CPAN. +Current measurements show it is faster than: + Math::Prime::XS + Math::Prime::FastSieve + Math::Factor::XS + Math::Big::Factors + Math::Factoring + Math::Primality + Math::Prime::TiedArray +For non-bignums, it is typically faster than Math::Pari (and doesn't +require Pari to be installed). SYNOPSIS diff --git a/examples/parallel_fibprime.pl b/examples/parallel_fibprime.pl new file mode 100755 index 0000000..50df2a5 --- /dev/null +++ b/examples/parallel_fibprime.pl @@ -0,0 +1,98 @@ +#!/usr/bin/env perl +use strict; +use warnings; +use threads; +use threads::shared; +use Math::BigInt lib => 'GMP'; +use Math::Prime::Util ':all'; +use Time::HiRes qw(gettimeofday tv_interval); +$| = 1; + +# Find Fibonacci primes in parallel, using Math::Prime::Util and Perl threads. +# +# Dana Jacobsen, 2012. +# +# This will fully utilize however many cores you choose (using the $nthreads +# variable). It spreads the numbers across threads, where each one runs a +# BPSW test. A separate thread handles the in-order display. +# +# On my 12-core computer: +# 24 5387 0.65488 +# 25 9311 4.39227 +# 26 9677 4.54363 +# 27 14431 18.82531 +# 28 25561 121.34584 +# 29 30757 212.99409 +# 30 35999 376.59567 +# 31 37511 432.10713 +# 32 50833 1151.85562 +# +# Though not as pretty as the Haskell solution on haskell.org, it is a +# different way of solving the problem that is faster and more scalable. + +my $time_start = [gettimeofday]; +my $nthreads = 12; +prime_precalc(1_000_000); + +my @found :shared; # push the primes found here +my @karray : shared; # array of min k for each thread + +my @threads; +push @threads, threads->create('fibprime', $_) for (1..$nthreads); + +# Let the threads work for a little before starting the display loop +sleep 2; +my $n = 0; +lock(@karray); +while (1) { + cond_wait(@karray); + { + lock(@found); + next if @found == 0; + # Someone has found a result. Discover min k processed so far. + my $mink = $karray[1] || 0; + for my $t (2..$nthreads) { + my $progress = $karray[$t] || 0; + $mink = $progress if $progress < $mink; + } + next unless $mink > 0; # someone hasn't even started + @found = sort { (split(/ /, $a))[0] <=> (split(/ /, $b))[0] } @found; + while ( @found > 0 && (split(/ /, $found[0]))[0] <= $mink ) { + my($k, $time_int) = split(/ /, shift @found); + printf "%3d %7d %20.5f\n", ++$n, $k, $time_int; + } + } +} +$_->join() for (@threads); + +sub fib_n { + my ($n, $fibstate) = @_; + @$fibstate = (1, Math::BigInt->new(0), Math::BigInt->new(1)) + unless defined $fibstate->[0]; + my ($curn, $a, $b) = @$fibstate; + die "fib_n only increases" if $n < $curn; + do { ($a, $b) = ($b, $a+$b); } for (1 .. $n-$curn); + @$fibstate = ($n, $a, $b); + $b; +} + +sub fibprime { + my $tnum = shift; + my @fibstate; + my $nth = $tnum; + while (1) { + # Exploit knowledge that excepting k=4, all prime F_k have a prime k. + my $k = ($nth <= 2) ? 2 + $nth : nth_prime($nth); + $nth += $nthreads; + my $Fk = fib_n($k, \@fibstate); + if (is_prob_prime($Fk)) { + lock(@found); + push @found, $k . " " . tv_interval($time_start); + } + { + lock(@karray); + $karray[$tnum] = $k; + cond_signal(@karray); + } + } +} diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm index 9ece5e3..841fa30 100644 --- a/lib/Math/Prime/Util.pm +++ b/lib/Math/Prime/Util.pm @@ -5,7 +5,7 @@ use Carp qw/croak confess carp/; BEGIN { $Math::Prime::Util::AUTHORITY = 'cpan:DANAJ'; - $Math::Prime::Util::VERSION = '0.12'; + $Math::Prime::Util::VERSION = '0.13'; } # parent is cleaner, and in the Perl 5.10.1 / 5.12.0 core, but not earlier. @@ -575,7 +575,7 @@ sub primes { } or do { croak "Cannot load Math::BigInt and Math::BigFloat"; }; - + my $c = Math::BigFloat->new("0.09"); # higher = more trial divisions my $r = Math::BigFloat->new("0.5"); my $m = 24; # How much randomness we're trying to get at a time @@ -1046,7 +1046,7 @@ sub is_provable_prime { carp "could not prove primality of $n.\n"; return 1; } - + for (my $a = 2; $a < $nm1; $a++) { my $ap = Math::BigInt->new($a); # 1. a^(n-1) = 1 mod n. @@ -1403,7 +1403,7 @@ Math::Prime::Util - Utilities related to prime numbers, including fast sieves an =head1 VERSION -Version 0.12 +Version 0.13 =head1 SYNOPSIS diff --git a/lib/Math/Prime/Util/PP.pm b/lib/Math/Prime/Util/PP.pm index 0a67888..a1e5406 100644 --- a/lib/Math/Prime/Util/PP.pm +++ b/lib/Math/Prime/Util/PP.pm @@ -5,7 +5,7 @@ use Carp qw/carp croak confess/; BEGIN { $Math::Prime::Util::PP::AUTHORITY = 'cpan:DANAJ'; - $Math::Prime::Util::PP::VERSION = '0.12'; + $Math::Prime::Util::PP::VERSION = '0.13'; } # The Pure Perl versions of all the Math::Prime::Util routines. @@ -757,7 +757,7 @@ sub is_strong_lucas_pseudoprime { # my $d=$m->copy; my $s=0; while ($d->is_even) { $s++; $d->brsft(1); } # die "Invalid $m, $d, $s\n" unless $m == $d * 2**$s; my $dstr = substr($m->as_bin, 2); - $dstr =~ s/(0*)$//; + $dstr =~ s/(0*)$//; my $s = length($1); my $ZERO = $n->copy->bzero; @@ -1142,7 +1142,7 @@ sub pbrent_factor { my $Xm = 2; if ( ref($n) eq 'Math::BigInt' ) { - + $Xi = $n->copy->bzero->badd($Xi); $Xm = $n->copy->bzero->badd($Xm); for my $i (1 .. $rounds) { @@ -1489,7 +1489,7 @@ Math::Prime::Util::PP - Pure Perl version of Math::Prime::Util =head1 VERSION -Version 0.12 +Version 0.13 =head1 SYNOPSIS @@ -1891,7 +1891,7 @@ Memory use will generally be higher for the PP code, and in some cases B<much> higher. Some of this may be addressed in a later release. For small values (e.g. primes and prime counts under 10M) most of this will -not matter. +not matter. =head1 SEE ALSO -- 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 [email protected] http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/pkg-perl-cvs-commits
