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 91d0a26fb78393fa39aa63c26df263aa9f4ba519 Author: Dana Jacobsen <[email protected]> Date: Thu Sep 19 17:44:19 2013 -0700 Add prime iterator object --- TODO | 4 +- lib/Math/Prime/Util.pm | 96 ++++++++----- lib/Math/Prime/Util/PrimeIterator.pm | 264 +++++++++++++++++++++++++++++++++++ 3 files changed, 330 insertions(+), 34 deletions(-) diff --git a/TODO b/TODO index 0ffcdba..e9750a3 100644 --- a/TODO +++ b/TODO @@ -41,4 +41,6 @@ - Rewrite 23-primality-proofs.t for new format (keep some of the old tests?). -- Use Montgomery routines in more places: Factoring and Lucas tests. +- Use Montgomery routines in more places: Factoring. + +- Tests for PrimeIterator diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm index e0ea514..54076cf 100644 --- a/lib/Math/Prime/Util.pm +++ b/lib/Math/Prime/Util.pm @@ -27,7 +27,7 @@ our @EXPORT_OK = miller_rabin lucas_sequence primes - forprimes prime_iterator + forprimes prime_iterator prime_iterator_object next_prime prev_prime prime_count prime_count_lower prime_count_upper prime_count_approx @@ -1517,6 +1517,13 @@ sub prime_iterator { } } +sub prime_iterator_object { + my($start) = @_; + eval { require Math::Prime::Util::PrimeIterator; 1; } + or do { croak "Cannot load Math::Prime::Util::PrimeIterator"; }; + return Math::Prime::Util::PrimeIterator->new($start); +} + # Omega function A001221. Just an example. sub _omega { my($n) = @_; @@ -1673,11 +1680,12 @@ sub _generic_is_prime { return 0 if defined $n && $n < 2; if (!_validate_num($n)) { $n = Math::BigInt->new("$n") - if defined $Math::BigInt::VERSION && ref($n) ne 'Math::BigInt'; + if defined $Math::BigInt::VERSION && ref($_[0]) ne 'Math::BigInt'; _validate_positive_integer($n); } - return _XS_is_prime("$n") if ref($n) ne 'Math::BigInt' && $n <= $_XS_MAXVAL; + return _XS_is_prime($n) + if ref($_[0]) ne 'Math::BigInt' && $n <= $_XS_MAXVAL; return Math::Prime::Util::GMP::is_prime($n) if $_HAVE_GMP; return 2 if ($n == 2) || ($n == 3) || ($n == 5); # 2, 3, 5 are prime @@ -1691,11 +1699,12 @@ sub _generic_is_prob_prime { return 0 if defined $n && $n < 2; if (!_validate_num($n)) { $n = Math::BigInt->new("$n") - if defined $Math::BigInt::VERSION && ref($n) ne 'Math::BigInt'; + if defined $Math::BigInt::VERSION && ref($_[0]) ne 'Math::BigInt'; _validate_positive_integer($n); } - return _XS_is_prob_prime($n) if ref($n) ne 'Math::BigInt' && $n<=$_XS_MAXVAL; + return _XS_is_prob_prime($n) + if ref($_[0]) ne 'Math::BigInt' && $n <= $_XS_MAXVAL; return Math::Prime::Util::GMP::is_prob_prime($n) if $_HAVE_GMP; return 2 if ($n == 2) || ($n == 3) || ($n == 5); # 2, 3, 5 are prime @@ -1709,8 +1718,9 @@ sub _generic_next_prime { _validate_num($n) || _validate_positive_integer($n); # If we have XS and n is either small or bigint is unknown, then use XS. - return _XS_next_prime($n) if ref($n) ne 'Math::BigInt' && $n <= $_XS_MAXVAL - && (!defined $bigint::VERSION || $n < $_Config{'maxprime'} ); + return _XS_next_prime($n) + if ref($_[0]) ne 'Math::BigInt' && $n <= $_XS_MAXVAL + && (!defined $bigint::VERSION || $n < $_Config{'maxprime'}); # Try to stick to the plan with respect to maximum return values. return 0 if ref($_[0]) ne 'Math::BigInt' && $n >= $_Config{'maxprime'}; @@ -1728,10 +1738,11 @@ sub _generic_prev_prime { my($n) = @_; _validate_num($n) || _validate_positive_integer($n); - return _XS_prev_prime($n) if ref($n) ne 'Math::BigInt' && $n <= $_XS_MAXVAL; + return _XS_prev_prime($n) + if ref($_[0]) ne 'Math::BigInt' && $n <= $_XS_MAXVAL; if ($_HAVE_GMP) { # If $n is a bigint object, try to make the return value the same - return (ref($n) eq 'Math::BigInt') + return (ref($_[0]) eq 'Math::BigInt') ? $n->copy->bzero->badd(Math::Prime::Util::GMP::prev_prime($n)) : Math::Prime::Util::GMP::prev_prime($n); } @@ -1789,7 +1800,7 @@ sub factor { if ($_HAVE_GMP) { my @factors = Math::Prime::Util::GMP::factor($n); - if (ref($n) eq 'Math::BigInt') { + if (ref($_[0]) eq 'Math::BigInt') { @factors = map { ($_ > ~0) ? $n->copy->bzero->badd($_) : $_ } @factors; } return @factors; @@ -1828,7 +1839,7 @@ sub is_pseudoprime { _validate_num($n) || _validate_positive_integer($n); _validate_num($a) || _validate_positive_integer($a); return _XS_is_pseudoprime($n, $a) - if ref($n) ne 'Math::BigInt' && $n <= $_XS_MAXVAL; + if ref($_[0]) ne 'Math::BigInt' && $n <= $_XS_MAXVAL; return Math::Prime::Util::GMP::is_pseudoprime($n, $a) if $_HAVE_GMP && defined &Math::Prime::Util::GMP::is_pseudoprime; return Math::Prime::Util::PP::is_pseudoprime($n, $a); @@ -1838,7 +1849,8 @@ sub is_strong_pseudoprime { my($n) = shift; _validate_num($n) || _validate_positive_integer($n); # validate bases? - return _XS_miller_rabin($n, @_) if ref($n) ne 'Math::BigInt' && $n <= $_XS_MAXVAL; + return _XS_miller_rabin($n, @_) + if ref($_[0]) ne 'Math::BigInt' && $n <= $_XS_MAXVAL; return Math::Prime::Util::GMP::is_strong_pseudoprime($n, @_) if $_HAVE_GMP; return Math::Prime::Util::PP::miller_rabin($n, @_); } @@ -1847,7 +1859,7 @@ sub is_lucas_pseudoprime { my($n) = shift; _validate_num($n) || _validate_positive_integer($n); return _XS_is_lucas_pseudoprime($n) - if ref($n) ne 'Math::BigInt' && $n <= $_XS_MAXVAL; + if ref($_[0]) ne 'Math::BigInt' && $n <= $_XS_MAXVAL; return Math::Prime::Util::GMP::is_lucas_pseudoprime("$n") if $_HAVE_GMP && defined &Math::Prime::Util::GMP::is_lucas_pseudoprime; return Math::Prime::Util::PP::is_lucas_pseudoprime($n); @@ -1857,7 +1869,7 @@ sub is_strong_lucas_pseudoprime { my($n) = shift; _validate_num($n) || _validate_positive_integer($n); return _XS_is_strong_lucas_pseudoprime($n) - if ref($n) ne 'Math::BigInt' && $n <= $_XS_MAXVAL; + if ref($_[0]) ne 'Math::BigInt' && $n <= $_XS_MAXVAL; return Math::Prime::Util::GMP::is_strong_lucas_pseudoprime("$n") if $_HAVE_GMP; return Math::Prime::Util::PP::is_strong_lucas_pseudoprime($n); @@ -1867,7 +1879,7 @@ sub is_extra_strong_lucas_pseudoprime { my($n) = shift; _validate_num($n) || _validate_positive_integer($n); return _XS_is_extra_strong_lucas_pseudoprime($n) - if ref($n) ne 'Math::BigInt' && $n <= $_XS_MAXVAL; + if ref($_[0]) ne 'Math::BigInt' && $n <= $_XS_MAXVAL; return Math::Prime::Util::GMP::is_extra_strong_lucas_pseudoprime("$n") if $_HAVE_GMP && defined &Math::Prime::Util::GMP::is_extra_strong_lucas_pseudoprime; @@ -1884,7 +1896,7 @@ sub is_almost_extra_strong_lucas_pseudoprime { || _validate_positive_integer($inc, 1, 256); } return _XS_is_almost_extra_strong_lucas_pseudoprime($n, $inc) - if ref($n) ne 'Math::BigInt' && $n <= $_XS_MAXVAL; + if ref($_[0]) ne 'Math::BigInt' && $n <= $_XS_MAXVAL; return Math::Prime::Util::GMP::is_almost_extra_strong_lucas_pseudoprime("$n", $inc) if $_HAVE_GMP && defined &Math::Prime::Util::GMP::is_almost_extra_strong_lucas_pseudoprime; @@ -1895,7 +1907,7 @@ sub is_frobenius_underwood_pseudoprime { my($n) = shift; _validate_num($n) || _validate_positive_integer($n); return _XS_is_frobenius_underwood_pseudoprime($n) - if ref($n) ne 'Math::BigInt' && $n <= $_XS_MAXVAL; + if ref($_[0]) ne 'Math::BigInt' && $n <= $_XS_MAXVAL; return Math::Prime::Util::GMP::is_frobenius_underwood_pseudoprime("$n") if $_HAVE_GMP && defined &Math::Prime::Util::GMP::is_frobenius_underwood_pseudoprime; @@ -1916,8 +1928,8 @@ sub lucas_sequence { { my $testQ = (!defined $Q || $Q >= 0) ? $Q : -$Q; _validate_num($testQ) || _validate_positive_integer($testQ); } return _XS_lucas_sequence($n, $P, $Q, $k) - if ref($n) ne 'Math::BigInt' && $n <= $_XS_MAXVAL - && ref($k) ne 'Math::BigInt' && $k <= $_XS_MAXVAL; + if ref($_[0]) ne 'Math::BigInt' && $n <= $_XS_MAXVAL + && ref($_[3]) ne 'Math::BigInt' && $k <= $_XS_MAXVAL; return Math::Prime::Util::GMP::lucas_sequence($n, $P, $Q, $k) if $_HAVE_GMP && defined &Math::Prime::Util::GMP::lucas_sequence; @@ -1967,7 +1979,8 @@ sub is_provable_prime { return 0 if defined $n && $n < 2; _validate_num($n) || _validate_positive_integer($n); - return _XS_is_prime("$n") if ref($n) ne 'Math::BigInt' && $n <= $_XS_MAXVAL; + return _XS_is_prime($n) + if ref($_[0]) ne 'Math::BigInt' && $n <= $_XS_MAXVAL; return Math::Prime::Util::GMP::is_provable_prime($n) if $_HAVE_GMP && defined &Math::Prime::Util::GMP::is_provable_prime; @@ -1989,7 +2002,7 @@ sub is_provable_prime_with_cert { _validate_num($n) || _validate_positive_integer($n); my $header = "[MPU - Primality Certificate]\nVersion 1.0\n\nProof for:\nN $n\n\n"; - if (ref($n) ne 'Math::BigInt' && $n <= $_XS_MAXVAL) { + if (ref($_[0]) ne 'Math::BigInt' && $n <= $_XS_MAXVAL) { my $isp = _XS_is_prime("$n"); return ($isp, '') unless $isp == 2; return (2, "[MPU - Primality Certificate]\nVersion 1.0\n\nProof for:\nN $n\n\nType Small\nN $n\n"); @@ -2082,7 +2095,7 @@ sub prime_count_approx { } # Turn on high precision FP if they gave us a big number. - $x = _upgrade_to_float($x) if ref($x) eq 'Math::BigInt'; + $x = _upgrade_to_float($x) if ref($_[0]) eq 'Math::BigInt'; # Method 10^10 %error 10^19 %error # ----------------- ------------ ------------ @@ -2122,7 +2135,7 @@ sub prime_count_lower { return $_prime_count_small[$x] if $x <= $#_prime_count_small; - $x = _upgrade_to_float($x) if ref($x) eq 'Math::BigInt'; + $x = _upgrade_to_float($x) if ref($_[0]) eq 'Math::BigInt'; my $flogx = log($x); @@ -2168,7 +2181,7 @@ sub prime_count_upper { return $_prime_count_small[$x] if $x <= $#_prime_count_small; - $x = _upgrade_to_float($x) if ref($x) eq 'Math::BigInt'; + $x = _upgrade_to_float($x) if ref($_[0]) eq 'Math::BigInt'; # Chebyshev: 1.25506*x/logx x >= 17 # Rosser & Schoenfeld: x/(logx-3/2) x >= 67 @@ -2239,7 +2252,7 @@ sub nth_prime_approx { return $_primes_small[$n] if $n <= $#_primes_small; - $n = _upgrade_to_float($n) if ref($n) eq 'Math::BigInt'; + $n = _upgrade_to_float($n) if ref($_[0]) eq 'Math::BigInt'; my $flogn = log($n); my $flog2n = log($flogn); @@ -2293,7 +2306,7 @@ sub nth_prime_lower { return $_primes_small[$n] if $n <= $#_primes_small; - $n = _upgrade_to_float($n) if ref($n) eq 'Math::BigInt'; + $n = _upgrade_to_float($n) if ref($_[0]) eq 'Math::BigInt'; my $flogn = log($n); my $flog2n = log($flogn); # Note distinction between log_2(n) and log^2(n) @@ -2318,7 +2331,7 @@ sub nth_prime_upper { return $_primes_small[$n] if $n <= $#_primes_small; - $n = _upgrade_to_float($n) if ref($n) eq 'Math::BigInt'; + $n = _upgrade_to_float($n) if ref($_[0]) eq 'Math::BigInt'; my $flogn = log($n); my $flog2n = log($flogn); # Note distinction between log_2(n) and log^2(n) @@ -2411,7 +2424,7 @@ __END__ =encoding utf8 -=for stopwords forprimes Möbius Deléglise totient moebius mertens znorder irand primesieve uniqued k-tuples von SoE pari yafu fonction qui compte le nombre nombres voor PhD superset sqrt(N) gcd(A^M +=for stopwords forprimes Möbius Deléglise totient moebius mertens znorder irand primesieve uniqued k-tuples von SoE pari yafu fonction qui compte le nombre nombres voor PhD superset sqrt(N) gcd(A^M k-th =head1 NAME @@ -2740,7 +2753,7 @@ strictly less than the input). 0 is returned if the input is C<2> or lower. =head2 forprimes - forprimes { say } 100,200; # print primes from 100-200 + forprimes { say } 100,200; # print primes from 100 to 200 $sum=0; forprimes { $sum += $_ } 100000; # sum primes to 100k @@ -2749,8 +2762,13 @@ strictly less than the input). 0 is returned if the input is C<2> or lower. Given a block and either an end count or a start and end pair, calls the block for each prime in the range. Compared to getting a big array of primes and iterating through it, this is more memory efficient and perhaps more -convenient. There is no way to exit the loop early, so the iterator may -be more appropriate for those uses. +convenient. This will almost always be the fastest way to loop over a range +of primes. Nesting and using in threads are allowed. + +For some uses an iterator (L</prime_iterator>, L</prime_iterator_object>) +or a tied array (L<Math::Prime::Util::PrimeArray>) may be more convenient. +Objects can be passed to functions, and allow early loop exits which are +only possible in L</forprimes> by using an exception. =head2 prime_iterator @@ -2769,8 +2787,20 @@ will return 211 followed by 223, as those are the next primes E<gt>= 200. On each call, the iterator returns the current value and increments to the next prime. -In general, L</forprimes> will be more efficient, but the generic iterator has -more flexibility (e.g. exiting a loop early, or passing the iterator around). +Other options include L</forprimes> (more efficiency, less flexibility), +L<Math::Prime::Util::PrimeIterator> (an iterator with more functionality), +or L<Math::Prime::Util::PrimeArray> (a tied array). + + +=head2 prime_iterator_object + + my $it = prime_iterator_object; + while ($it->value < 100) { say $it->value; $it->next; } + $sum += $it->iterate for 1..100000; + +Returns a L<Math::Prime::Util::PrimeIterator> object. A shortcut that loads +the package if needed, calls new, and returns the object. See the +documentation for that package for details. =head2 prime_count diff --git a/lib/Math/Prime/Util/PrimeIterator.pm b/lib/Math/Prime/Util/PrimeIterator.pm new file mode 100644 index 0000000..da70c05 --- /dev/null +++ b/lib/Math/Prime/Util/PrimeIterator.pm @@ -0,0 +1,264 @@ +package Math::Prime::Util::PrimeIterator; +use strict; +use warnings; + +BEGIN { + $Math::Prime::Util::PrimeIterator::AUTHORITY = 'cpan:DANAJ'; + $Math::Prime::Util::PrimeIterator::VERSION = '0.32'; +} + +use base qw( Exporter ); +our @EXPORT_OK = qw( ); +our %EXPORT_TAGS = (all => [ @EXPORT_OK ]); + + +use Math::Prime::Util qw/next_prime prev_prime/; +use Math::BigInt try => "GMP,Pari"; +#use Carp qw/carp croak confess/; + +sub new { + my $class = shift; + my($start) = @_; + my $self = bless { + p => 2, + }, $class; + $self->rewind($start) if defined $start && $start > 2; + return $self; +} + +sub value { $_[0]->{p}; } +sub next { + my $self = shift; + my $np = next_prime($self->{p}); + $np = next_prime(Math::BigInt->new(''.~0)) if $np == 0; + $self->{p} = $np; + return $self; +} +sub prev { + my $self = shift; + my $p = $self->{p}; + $self->{p} = ($p <= 2) ? 2 : prev_prime($p); + return $self; +} +sub iterate { + my $self = shift; + my $p = $self->{p}; + my $np = next_prime($p); + $np = next_prime(Math::BigInt->new(''.~0)) if $np == 0; + $self->{p} = $np; + return $p; +} + +sub rewind { + my $self = shift; + my($start) = @_; + if (defined $start) { + Math::Prime::Util::_validate_num($start) + || Math::Prime::Util::_validate_positive_integer($start); + $self->{p} = ($start > 2) ? next_prime($start-1) : 2; + $self->{p} = next_prime(Math::BigInt->new(''.~0)) + if $self->{p} == 0 && $start > 0; + } else { + $self->{p} = 2; + } + return $self; +} + +# Some methods to match Math::NumSeq +sub tell_i { + my $self = shift; + return Math::Prime::Util::prime_count($self->{p}); +} +sub pred { + my($self, $n) = @_; + return Math::Prime::Util::is_prime($n); +} +sub ith { + my($self, $n) = @_; + return Math::Prime::Util::nth_prime($n); +} +sub seek_to_i { + my($self, $n) = @_; + $self->rewind( Math::Prime::Util::nth_prime($n) ); +} +sub seek_to_value { + my($self, $n) = @_; + $self->rewind($n); +} +sub value_to_i { + my($self, $n) = @_; + return Math::Prime::Util::prime_count($n); +} +sub value_to_i_estimate { + my($self, $n) = @_; + return Math::Prime::Util::prime_count_approx($n); +} +sub i_start { 1 } +sub description { "The prime numbers 2, 3, 5, 7, 11, 13, 17, etc." } +sub values_min { 2 } +sub values_max { undef } +sub oeis_anum { "A000040" } +1; + +__END__ + + +# ABSTRACT: An object iterator for primes + +=pod + +=for stopwords prev pred ith i'th + +=head1 NAME + +Math::Prime::Util::PrimeIterator - An object iterator for primes + + +=head1 VERSION + +Version 0.32 + + +=head1 SYNOPSIS + + use Math::Prime::Util::PrimeIterator; + my $it = Math::Prime::Util::PrimeIterator->new(); + + # Simple use: return current value and move forward. + $sum += $it->iterate() for 1..10000; + + # Methods + my $v = $it->value(); # Return current value + $it->next(); # Move to next prime (returns self) + $it->prev(); # Move to prev prime (returns self) + my $v = $it->iterate(); # Returns current value and moves to next prime + $it->rewind(); # Resets position to 2 + $it->rewind($n); # Resets position to next_prime($n-1) + + # Methods similar to Math::NumSeq, do not change iterator + $it->tell_i(); # Returns the index of the current position + $it->pred($n); # Returns true if $n is prime + $it->ith($i); # Returns the $ith prime + $it->value_to_i($n) # Returns the index of the first prime >= $n + $it->value_to_i_estimate($n) # Approx index of value $n + + # Methods similar to Math::NumSeq, changes iterator + $it->seek_to_i($i); # Resets position to the $ith prime + $it->seek_to_value($i); # Resets position to next_prime($i-1) + +=head1 DESCRIPTION + +An iterator over the primes. L</new> returns an iterator object and takes +an optional starting position (the initial value will be the least prime +greater than or equal to the argument). BigInt objects will be returned if +the value overflows a Perl unsigned integer value. + +=head1 METHODS + +=head2 new + +Creates an iterator object with initial value of 2. If an argument is +given, the initial value will be the least prime greater than or equal +to the argument. + +=head2 value + +Returns the value at the current position. Will always be a prime. If +the value is greater than ~0, it will be a L<Math::BigInt> object. + +=head2 next + +Moves the current position to the next prime. +Returns self so calls can be chained. + +=head2 prev + +Moves the current position to the previous prime, unless the current +value is 2, in which case the value remains 2. +Returns self so calls can be chained. + +=head2 iterate + +Returns the value at the current position and also moves the position to +the next prime. + +=head2 rewind + +Resets the current position to either 2 or, if given an integer argument, +the least prime not less than the argument. + +=head2 tell_i + +Returns the index of the current position, starting at 1 (corresponding to +the value 2). +The iterator is unchanged after this call. + +=head2 pred + +Returns true if the argument is a prime, false otherwise. +The iterator is unchanged after this call. + +=head2 ith + +Returns the i'th prime, where the first prime is 2. +The iterator is unchanged after this call. + +=head2 value_to_i_estimate + +Returns an estimate of the index corresponding to the argument. That is, +given a value C<n>, we expect a prime approximately equal to C<n> to occur +at this index.. + +The estimate is performed using L<Math::Prime::Util/prime_count_approx>, +which uses the estimates of Dusart 2010 (or better for small values). +This has an error two or more orders of magnitude less than the estimate +used by L<Math::NumSeq::Primes>. E.g. given a value of 86028121 whose +true index is 5000000, this method returns 5000067 while +Math::NumSeq::Primes returns 4708661. + +=head2 value_to_i + +Returns the index corresponding to the argument. + +=head2 seek_to_i + +Resets the position to the prime corresponding to the given index. + +=head2 seek_to_value + +An alias for L</rewind>. + +=head2 i_start +=head2 description +=head2 values_min +=head2 values_max +=head2 oeis_anum + +Methods to match Math::NumSeq::Primes. + +=head1 SEE ALSO + +L<Math::Prime::Util> + +L<Math::Prime::Util/forprimes> + +L<Math::Prime::Util/prime_iterator> + +L<Math::Prime::Util/prime_iterator_object> + +L<Math::Prime::Util::PrimeArray> + +L<Math::NumSeq::Primes> + +=head1 AUTHORS + +Dana Jacobsen E<lt>[email protected]<gt> + + +=head1 COPYRIGHT + +Copyright 2013 by Dana Jacobsen E<lt>[email protected]<gt> + +This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself. + +=cut -- 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
