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 722ec20738dd3b2a9cdda5d0ba25a90011f66095 Author: Dana Jacobsen <d...@acm.org> Date: Mon Oct 14 12:30:54 2013 -0700 Iterator object tests and fixes for next/prev prime behavior near native boundary --- Changes | 3 +- lib/Math/Prime/Util.pm | 14 +++--- lib/Math/Prime/Util/PP.pm | 2 +- lib/Math/Prime/Util/PrimeIterator.pm | 30 ++++++------- t/32-iterators.t | 84 +++++++++++++++++++++++++++++++++++- 5 files changed, 106 insertions(+), 27 deletions(-) diff --git a/Changes b/Changes index 68b2c81..c2e766d 100644 --- a/Changes +++ b/Changes @@ -50,7 +50,8 @@ Revision history for Perl module Math::Prime::Util - Montgomery reduction used in Lucas and Frobenius tests. Up to 2x speedup for 33 to 64-bit inputs on x86_64/gcc platforms. - - Some fixes around near maxint primes, forprimes, etc. + - Some fixes around near maxint primes, forprimes, etc. Includes + more workarounds for Math::BigInt::GMP's constructor sign bug. - Bytes::Random::Secure is loaded only when random prime functionality is used. Shaves a few milliseconds and bytes off of startup. diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm index a2e14f4..38cd325 100644 --- a/lib/Math/Prime/Util.pm +++ b/lib/Math/Prime/Util.pm @@ -62,7 +62,6 @@ sub _import_nobigint { undef *nth_prime; *nth_prime = \&_XS_nth_prime; undef *is_pseudoprime; *is_pseudoprime = \&_XS_is_pseudoprime; undef *is_strong_pseudoprime; *is_strong_pseudoprime = \&_XS_miller_rabin; - undef *miller_rabin; *miller_rabin = \&_XS_miller_rabin; undef *moebius; *moebius = \&_XS_moebius; undef *mertens; *mertens = \&_XS_mertens; undef *euler_phi; *euler_phi = \&_XS_totient; @@ -1247,7 +1246,7 @@ sub primorial { if ($_HAVE_GMP && defined &Math::Prime::Util::GMP::primorial) { if (ref($pn) eq 'Math::BigInt') { - $pn->bzero->badd( Math::Prime::Util::GMP::primorial($n) ); + $pn->bzero->badd( ''.Math::Prime::Util::GMP::primorial($n) ); } else { $pn = int( Math::Prime::Util::GMP::primorial($n) ); } @@ -1265,7 +1264,7 @@ sub pn_primorial { _validate_num($n) || _validate_positive_integer($n); my $pn = Math::Prime::Util::GMP::pn_primorial($n); return int($pn) if $n < (($_Config{'maxbits'} == 32) ? 10 : 16); - return $_[0]->copy->bzero->badd($pn) if ref($_[0]) eq 'Math::BigInt'; + return $_[0]->copy->bzero->badd("$pn") if ref($_[0]) eq 'Math::BigInt'; if (!defined $Math::BigInt::VERSION) { eval { require Math::BigInt; Math::BigInt->import(try=>'GMP,Pari'); 1; } or do { croak "Cannot load Math::BigInt"; }; @@ -1827,10 +1826,11 @@ sub _generic_next_prime { if ($_HAVE_GMP) { # If $n is a bigint object, try to make the return value the same return (ref($_[0]) eq 'Math::BigInt') - ? $_[0]->copy->bzero->badd(Math::Prime::Util::GMP::next_prime($n)) + ? $_[0]->copy->bzero->badd(''.Math::Prime::Util::GMP::next_prime($n)) : Math::Prime::Util::GMP::next_prime($n); } - return Math::Prime::Util::PP::next_prime($n); + # Pass original argument to preserve bigint status + return Math::Prime::Util::PP::next_prime($_[0]); } sub _generic_prev_prime { @@ -1842,7 +1842,7 @@ sub _generic_prev_prime { if ($_HAVE_GMP) { # If $n is a bigint object, try to make the return value the same return (ref($_[0]) eq 'Math::BigInt') - ? $n->copy->bzero->badd(Math::Prime::Util::GMP::prev_prime($n)) + ? $n->copy->bzero->badd(''.Math::Prime::Util::GMP::prev_prime($n)) : Math::Prime::Util::GMP::prev_prime($n); } return Math::Prime::Util::PP::prev_prime($n); @@ -1900,7 +1900,7 @@ sub factor { if ($_HAVE_GMP) { my @factors = Math::Prime::Util::GMP::factor($n); if (ref($_[0]) eq 'Math::BigInt') { - @factors = map { ($_ > ~0) ? $n->copy->bzero->badd($_) : $_ } @factors; + @factors = map { ($_ > ~0) ? $n->copy->bzero->badd(''.$_) : $_ } @factors; } return @factors; } diff --git a/lib/Math/Prime/Util/PP.pm b/lib/Math/Prime/Util/PP.pm index 7bad4f1..a4c147d 100644 --- a/lib/Math/Prime/Util/PP.pm +++ b/lib/Math/Prime/Util/PP.pm @@ -1353,7 +1353,7 @@ sub is_aks_prime { ->bsqrt->bmul($log2n)->bfloor->bstr); $_poly_bignum = 1; - if ( $n < ( (~0 == 4294967295) ? 65535 : 4294967295 ) ) { + if ( $n < ($_half_word-1) ) { $_poly_bignum = 0; $n = int($n->bstr) if ref($n) eq 'Math::BigInt'; } diff --git a/lib/Math/Prime/Util/PrimeIterator.pm b/lib/Math/Prime/Util/PrimeIterator.pm index da70c05..7aa20f9 100644 --- a/lib/Math/Prime/Util/PrimeIterator.pm +++ b/lib/Math/Prime/Util/PrimeIterator.pm @@ -14,23 +14,24 @@ 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/; + +my $bigprime = Math::BigInt->new( + (~0 == 4294967295) ? "4294967311" : "18446744073709551629" +); sub new { - my $class = shift; - my($start) = @_; + my ($class, $start) = @_; my $self = bless { p => 2, }, $class; - $self->rewind($start) if defined $start && $start > 2; + $self->rewind($start) if defined $start; 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; + my $np = next_prime($self->{p}) || $bigprime; $self->{p} = $np; return $self; } @@ -43,23 +44,20 @@ sub prev { sub iterate { my $self = shift; my $p = $self->{p}; - my $np = next_prime($p); - $np = next_prime(Math::BigInt->new(''.~0)) if $np == 0; + my $np = next_prime($p) || $bigprime; $self->{p} = $np; return $p; } sub rewind { - my $self = shift; - my($start) = @_; - if (defined $start) { + my ($self, $start) = @_; + $self->{p} = 2; + if (defined $start && $start ne '2') { 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; + if ($start > 2) { + $self->{p} = next_prime($start-1) || $bigprime; + } } return $self; } diff --git a/t/32-iterators.t b/t/32-iterators.t index 645c1d3..b7fc19c 100644 --- a/t/32-iterators.t +++ b/t/32-iterators.t @@ -3,14 +3,19 @@ use strict; use warnings; use Test::More; -use Math::Prime::Util qw/primes forprimes prime_iterator/; +use Math::Prime::Util qw/primes prev_prime next_prime + forprimes prime_iterator prime_iterator_object/; +use Math::BigInt try => "GMP,Pari"; my $use64 = Math::Prime::Util::prime_get_config->{'maxbits'} > 32; plan tests => 8 + 5 + 12 + 3 + 7 - + 2; + + 2 + + 3 + 7 + + 22 + + 0; ok(!eval { forprimes { 1 } undef; }, "forprimes undef"); ok(!eval { forprimes { 1 } 2, undef; }, "forprimes 2,undef"); @@ -102,3 +107,78 @@ ok(!eval { prime_iterator(4.5); }, "iterator 4.5"); } is_deeply( [@t], [qw/23 29 31 29 31 37 31 37 41 37 41 43 47 53 59 61 59 61 67 71 73 79 73 79 83 79 83 89/], "triple nested iterator" ); } + +# Test new object iterator +ok(!eval { prime_iterator_object(-2); }, "iterator -2"); +ok(!eval { prime_iterator_object("abc"); }, "iterator abc"); +ok(!eval { prime_iterator_object(4.5); }, "iterator 4.5"); + +{ my $it = prime_iterator_object(); + is_deeply( [map { $it->iterate() } 1..10], [2,3,5,7,11,13,17,19,23,29], "iterator first 10 primes" ); +} +{my $it = prime_iterator_object(47); + is_deeply( [map { $it->iterate() } 1..5], [47,53,59,61,67], "iterator 5 primes starting at 47" ); +} +{my $it = prime_iterator_object(199); + is_deeply( [map { $it->iterate() } 1..3], [199,211,223], "iterator 3 primes starting at 199" ); +} +{my $it = prime_iterator_object(200); + is_deeply( [map { $it->iterate() } 1..3], [211,223,227], "iterator 3 primes starting at 200" ); +} +{my $it = prime_iterator_object(31397); + is_deeply( [map { $it->iterate() } 1..3], [31397,31469,31477], "iterator 3 primes starting at 31397" ); +} +{my $it = prime_iterator_object(31396); + is_deeply( [map { $it->iterate() } 1..3], [31397,31469,31477], "iterator 3 primes starting at 31396" ); +} +{my $it = prime_iterator_object(31398); + is_deeply( [map { $it->iterate() } 1..3], [31469,31477,31481], "iterator 3 primes starting at 31398" ); +} + +{ + my $it = prime_iterator_object; + do { $it->next } for 1..10; + is( $it->value(), 31, "iterator object moved forward 10 now returns 31"); + $it->prev; + is( $it->value(), 29, "iterator object moved back now returns 29"); + is( $it->iterate(), 29, "iterator object iterates to 29"); + is( $it->iterate(), 31, "iterator object iterates to 31"); + $it->rewind->next->next->next->prev; + is( $it->value(), 5, "iterator object rewind and move returns 5"); + # Validate that it automatically handles bigint range traversal. + my $top_prime = prev_prime(~0); + my $big_prime = next_prime(Math::BigInt->new(''.~0)); + ok( $big_prime > ~0, "internal check, next_prime on big int works"); + $it->rewind($top_prime); + is( $it->value(), $top_prime, "iterator object can rewind to $top_prime"); + $it->next; + is( $it->value(), $big_prime, "iterator object next is $big_prime"); + $it->rewind(~0); + is( $it->value(), $big_prime, "iterator object rewound to ~0 is $big_prime"); + $it->prev; + is( $it->value(), $top_prime, "iterator object prev goes back to $top_prime"); + + # Validation for the Math::NumSeq compatiblity stuff + $it->rewind; + do { $it->next } for 1..200; + is( $it->tell_i(), 201, "iterator object tell_i"); + is( $it->i_start, 1, "iterator object i_start = 1"); + like( $it->description, qr/prime numbers/, "iterator object description"); + is( $it->values_min, 2, "iterator object values_min = 2"); + is( $it->values_max, undef, "iterator object values_max = undef"); + # missing: characteristic + is( $it->oeis_anum, "A000040", "iterator object oeis_anum = A000040"); + # missing: parameter_info_array / parameter_info_list + is( $it->seek_to_i(156)->value, 911, "iterator object seek_to_i goes to nth prime"); + is( $it->seek_to_value(156)->value, 157, "iterator object seek_to_value goes to value"); + is( $it->ith(589), 4289, "iterator object ith returns nth prime"); + ok( $it->pred(577), "iterator object pred returns true if is_prime"); + is( $it->value_to_i(4289), 589, "iterator object value_to_i works"); + # missing: value_to_i_ceil + # missing: value_to_i_floor + my $est = $it->value_to_i_estimate( 4171510507 ); + my $act = 197710788; + # We will get an estimate that is much, much closer than Math::NumSeq + ok( ($est > ($act-500)) && ($est < ($act+500)), + "iterator object value_to_i_estimage is in range"); +} -- 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