This is an automated email from the git hooks/post-receive script. ppm-guest pushed a commit to annotated tag v0.08 in repository libmath-prime-util-perl.

## Advertising

commit 4df961923c1b768485f3b5ce5ccc43f4c1163a14 Author: Dana Jacobsen <d...@acm.org> Date: Tue Jun 19 02:07:12 2012 -0600 Add add_factors --- Changes | 1 + examples/test-nextprime-yafu.pl | 4 +-- lib/Math/Prime/Util.pm | 71 +++++++++++++++++++++++++++++++++++++---- 3 files changed, 67 insertions(+), 9 deletions(-) diff --git a/Changes b/Changes index 7b3d91a..cf964d2 100644 --- a/Changes +++ b/Changes @@ -7,6 +7,7 @@ Revision history for Perl extension Math::Prime::Util. performance comparisons. - Static presieve for 7, 11, and 13. 1k of ROM used for prefilling sieve memory, meaning we can skip the 7, 11, and 13 loops. ~15% speedup. + - Add all_factors function. 0.07 17 June 2012 - Fixed a bug in next_prime found by Lou Godio (thank you VERY much!). diff --git a/examples/test-nextprime-yafu.pl b/examples/test-nextprime-yafu.pl index e30c348..47e5bde 100755 --- a/examples/test-nextprime-yafu.pl +++ b/examples/test-nextprime-yafu.pl @@ -6,11 +6,11 @@ use File::Temp qw/tempfile/; use autodie; my $maxdigits = (~0 <= 4294967295) ? 10 : 20; $| = 1; # fast pipes -my $num = 10000; +my $num = shift || 10000; my $yafu_fname = "yafu_batchfile_$$.txt"; $SIG{'INT'} = \&gotsig; -foreach my $digits (1 .. $maxdigits) { +foreach my $digits (4 .. $maxdigits) { printf "%2d-digit numbers", $digits; my @narray = gendigits($digits, $num); print "."; diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm index 64f290f..62bc48e 100644 --- a/lib/Math/Prime/Util.pm +++ b/lib/Math/Prime/Util.pm @@ -19,7 +19,7 @@ our @EXPORT_OK = qw( prime_count prime_count_lower prime_count_upper prime_count_approx nth_prime nth_prime_lower nth_prime_upper nth_prime_approx random_prime random_ndigit_prime - factor + factor all_factors ExponentialIntegral LogarithmicIntegral RiemannR ); our %EXPORT_TAGS = (all => [ @EXPORT_OK ]); @@ -93,7 +93,7 @@ sub primes { } if ($method =~ /^Simple\w*$/i) { - warn "Method 'Simple' is deprecated."; + carp "Method 'Simple' is deprecated."; $method = 'Erat'; } @@ -180,6 +180,21 @@ sub random_ndigit_prime { # Perhaps a random_nbit_prime ? Definition? +sub all_factors { + my $n = shift; + my @factors = factor($n); + my %all_factors; + foreach my $f1 (@factors) { + my @all = keys %all_factors;; + foreach my $f2 (@all) { + $all_factors{$f1*$f2} = 1 if ($f1*$f2) < $n; + } + $all_factors{$f1} = 1; + } + @factors = sort {$a<=>$b} keys %all_factors; + return @factors; +} + # We use this object to let them control when memory is freed. package Math::Prime::Util::MemFree; use Carp qw/croak confess/; @@ -193,6 +208,7 @@ sub DESTROY { my $self = shift; confess "instances count mismatch" unless $memfree_instances > 0; Math::Prime::Util::prime_memfree if --$memfree_instances == 0; + return; } package Math::Prime::Util; @@ -600,6 +616,15 @@ finally trial division for any survivors. This process is repeated for each non-prime factor. +=head2 all_factors + + my @divisors = all_factors(30); # returns (2, 3, 5, 6, 10, 15) + +Produces all the divisors of a positive number input. Note that 1 and the +input number are excluded. The divisors are a power set of multiplications +of the prime factors, returned as a uniqued sorted list. + + =head2 trial_factor my @factors = trial_factor($n); @@ -735,6 +760,8 @@ implementation. Counting the primes to C<10^10> (10 billion), with time in seconds. Pi(10^10) = 455,052,511. + External C programs in C / C++: + 1.9 primesieve 3.6 forced to use only a single thread 2.2 yafu 1.31 5.6 Tomás Oliveira e Silva's segmented sieve v2 (Sep 2010) @@ -742,7 +769,9 @@ Pi(10^10) = 455,052,511. 11.2 Tomás Oliveira e Silva's segmented sieve v1 (May 2003) 17.0 Pari 2.3.5 (primepi) - 5.9 My segmented SoE + Small portable functions suitable for plugging into XS: + + 5.3 My segmented SoE used in this module 15.6 My Sieve of Eratosthenes using a mod-30 wheel 17.2 A slightly modified verion of Terje Mathisen's mod-30 sieve 35.5 Basic Sieve of Eratosthenes on odd numbers @@ -762,10 +791,38 @@ Perl modules, counting the primes to C<800_000_000> (800 million), in seconds: [hours] Math::Primality 0.04 -C<is_prime> is slightly faster than M::P::XS for small inputs, but is much -faster with larger ones (5x faster for 8-digit, over 50x for 14-digit). -Math::Pari is relatively slow for small inputs, but becomes faster in the -13-digit range. + +C<is_prime>: my impressions: + + Module Small inputs Large inputs (10-20dig) + ----------------------- ------------- ---------------------- + Math::Prime::Util Very fast Pretty fast + Math::Prime::XS Very fast Very, very slow if no small factors + Math::Pari Slow OK + Math::Prime::FastSieve Very fast N/A (too much memory) + Math::Primality Very slow Very slow + +The differences are in the implementations: + - L<Math::Prime::FastSieve> only works in a sieved range, which is really + fast if you can do it (M::P::U will do the same if you call + C<prime_precalc>). Larger inputs just need too much time and memory + for the sieve. + - L<Math::Primality> uses a GMP BPSW test which is overkill for our 64-bit + range. It's generally an order of magnitude or two slower than any + of the others. + - L<Math::Pari> has some very effective code, but it has some overhead to get + to it from Perl. That means for small numbers it is relatively slow: an + order of magnitude slower than M::P::XS and M::P::Util (though arguably + this is only important for benchmarking since "slow" is ~2 microseconds). + Large numbers transition over to smarter tests so don't slow down much. + - L<Math::Prime::XS> does trial divisions, which is wonderful if the input + has a small factor (or is small itself). But it can take 1000x longer + if given a large prime. + - L<Math::Prime::Util> looks in the sieve for a fast bit lookup if that + exists (default up to 30,000 but it can be expanded, e.g. + C<prime_precalc>), uses trial division for numbers higher than this but + not too large (0.1M on 64-bit machines, 100M on 32-bit machines), and a + deterministic set of Miller-Rabin tests for large numbers. Factoring performance depends on the input, and the algorithm choices used -- 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