This is an automated email from the git hooks/post-receive script. ppm-guest pushed a commit to annotated tag v0.35 in repository libmath-prime-util-perl.
commit f3f8ce9041157f0e42a377241c815215ae8d1407 Author: Dana Jacobsen <d...@acm.org> Date: Wed Nov 20 18:17:01 2013 -0800 auto bigint, round 1 --- Changes | 17 ++ lib/Math/Prime/Util.pm | 313 ++++++++++------------------------- lib/Math/Prime/Util/PP.pm | 106 ++++-------- lib/Math/Prime/Util/PrimeIterator.pm | 15 +- lib/Math/Prime/Util/ZetaBigFloat.pm | 1 + t/12-nextprime.t | 4 +- t/14-nthprime.t | 11 -- t/80-pp.t | 4 +- 8 files changed, 142 insertions(+), 329 deletions(-) diff --git a/Changes b/Changes index 796776a..a950550 100644 --- a/Changes +++ b/Changes @@ -1,5 +1,22 @@ Revision history for Perl module Math::Prime::Util +0.35 2013-11 + + [API Changes] + + - We now use Math::BigInt in the module rather than dynamically loading + it, and will switch to BigInts as needed. The most noticeable effect + of this is that next_prime() / prev_prime() will switch between BigInt + and native int at the boundary without regard to the input type or + whether bigint is in effect, and next_prime will never return 0. + Additionally, all functions will convert large decimal number strings + to BigInts if needed. + + $pref = primes("1000000000000000000000", "1000000000000000000999"); + is_prime("882249208105452588824618008529"); + $a = euler_phi("801294088771394680000412"); + + 0.34 2013-11-19 - Fixed test that was using a 64-bit number on 32-bit machines. diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm index a14ce7c..25e5995 100644 --- a/lib/Math/Prime/Util.pm +++ b/lib/Math/Prime/Util.pm @@ -2,6 +2,7 @@ package Math::Prime::Util; use strict; use warnings; use Carp qw/croak confess carp/; +use Math::BigInt try=>"GMP,Pari"; BEGIN { $Math::Prime::Util::AUTHORITY = 'cpan:DANAJ'; @@ -161,30 +162,6 @@ our $_Infinity = 0+'inf'; $_Infinity = 20**20**20 if 65535 > $_Infinity; # E.g. Windows our $_Neg_Infinity = -$_Infinity; -# Notes on how we're dealing with big integers: -# -# 1) if (ref($n) eq 'Math::BigInt') -# $n is a bigint, so do bigint stuff -# -# 2) if (defined $bigint::VERSION && $n > ~0) -# make $n into a bigint. This is debatable, but they *did* hand us a -# string with a big integer in it. The big gotcha here is that -# is_strong_lucas_pseudoprime does bigint computations, so it will load -# up Math::BigInt and there is no way to unload it. -# -# 3) if (ref($n) =~ /^Math::Big/) -# $n is a big int, float, or rat. We probably want this as an int. -# -# $n = $n->numify if $n < ~0 && ref($n) =~ /^Math::Big/; -# get us out of big math if we can -# -# Sadly, non-modern versions of bignum (5.12.4 and earlier) completely make a -# mess of things like BigInt::numify and int(BigFloat). Using int($x->bstr) -# seems to work. -# E.g.: -# $n = 33662485846146713; $n->numify; $n is now 3.36624858461467e+16 - - sub prime_get_config { my %config = %_Config; @@ -240,22 +217,11 @@ sub _validate_positive_integer { croak "Parameter '$n' must be >= $min" if defined $min && $n < $min; croak "Parameter '$n' must be <= $max" if defined $max && $n > $max; - if (ref($_[0])) { - $_[0] = Math::BigInt->new("$_[0]") unless ref($_[0]) eq 'Math::BigInt'; - # Stupid workaround for Math::BigInt::GMP RT # 71548 - if ($_[0]->bacmp(''.~0) <= 0) { - $_[0] = int($_[0]->bstr); - } else { - $_[0]->upgrade(undef) if $_[0]->upgrade(); # Stop BigFloat upgrade - } + $_[0] = Math::BigInt->new("$_[0]") unless ref($_[0]) eq 'Math::BigInt'; + if ($_[0]->bacmp(''.~0) <= 0) { + $_[0] = int($_[0]->bstr); } else { - # The second term is used instead of '<=' to fix strings like ~0+delta. - if ( ! ($n < $_Config{'maxparam'} || int($n) eq $_Config{'maxparam'}) ) { - # We were handed a string representing a big number. - croak "Parameter '$n' outside of integer range" if !defined $bigint::VERSION; - $_[0] = Math::BigInt->new("$n"); # Make $n a proper bigint object - $_[0]->upgrade(undef) if $_[0]->upgrade(); # Stop BigFloat upgrade - } + $_[0]->upgrade(undef) if $_[0]->upgrade(); # Stop BigFloat upgrade } # One of these will be true: # 1) $n <= ~0 and $n is not a bigint @@ -263,20 +229,10 @@ sub _validate_positive_integer { 1; } -# If you use bigint then call one of the approx/bounds/math functions, you'll -# end up with full bignum turned on. This seems non-optimal. However, if I -# don't do this, then you'll get wrong results and end up with it turned on -# _anyway_. As soon as anyone does something like log($n) where $n is a -# Math::BigInt, it auto-upgrade and loads up Math::BigFloat. -# -# Ideally we'd notice we were causing this, and turn off Math::BigFloat after -# we were done. sub _upgrade_to_float { - my($n) = @_; - return $n unless defined $Math::BigInt::VERSION || defined $Math::BigFloat::VERSION; - do { require Math::BigFloat; Math::BigFloat->import() } - if defined $Math::BigInt::VERSION && !defined $Math::BigFloat::VERSION; - return Math::BigFloat->new($n); # $n is a Math::BigInt + do { require Math::BigFloat; Math::BigFloat->import(); } + if !defined $Math::BigFloat::VERSION; + return Math::BigFloat->new($_[0]); } my @_primes_small = ( @@ -318,8 +274,6 @@ sub primes { $sref = Math::Prime::Util::GMP::primes($low,$high); if ($high > ~0) { # Convert the returned strings into BigInts - croak "Internal error: large value without bigint loaded." - unless defined $Math::BigInt::VERSION; @$sref = map { Math::BigInt->new("$_") } @$sref; } else { @$sref = map { int($_) } @$sref; @@ -480,7 +434,6 @@ sub primes { $_big_gcd_use = 0; return; } - croak "Internal error: make_big_gcds needs Math::BigInt!" unless defined $Math::BigInt::VERSION; if (Math::BigInt->config()->{lib} !~ /^Math::BigInt::(GMP|Pari)/) { $_big_gcd_use = 0; return; @@ -874,10 +827,6 @@ sub primes { if (!defined $_random_ndigit_ranges[$digits]) { if ($bigdigits) { - if (!defined $Math::BigInt::VERSION) { - eval { require Math::BigInt; Math::BigInt->import(try=>'GMP,Pari'); 1; } - or do { croak "Cannot load Math::BigInt"; }; - } my $low = Math::BigInt->new('10')->bpow($digits-1); my $high = Math::BigInt->new('10')->bpow($digits); # Just pull the range in to the nearest odd. @@ -918,12 +867,6 @@ sub primes { croak "Mid-size random primes not supported on broken old Perl" if $] < 5.008 && $bits > 49 && $_Config{'maxbits'} > 32 && $bits <= $_Config{'maxbits'}; - if ($bits > $_Config{'maxbits'}) { - if (!defined $Math::BigInt::VERSION) { - eval { require Math::BigInt; Math::BigInt->import(try=>'GMP,Pari'); 1; } - or do { croak "Cannot load Math::BigInt"; }; - } - } # Fouque and Tibouchi (2011) Algorithm 1 (basic) # Modified to make sure the nth bit is always set. @@ -1069,19 +1012,13 @@ sub primes { return ($n, $cert); } - if (!defined $Math::BigInt::VERSION) { - eval { require Math::BigInt; Math::BigInt->import(try=>'GMP,Pari'); 1; } - or do { croak "Cannot load Math::BigInt"; }; - } - if (!defined $Math::BigFloat::VERSION) { - eval { require Math::BigFloat; Math::BigFloat->import(); 1; } - or do { croak "Cannot load Math::BigFloat"; }; - } - # Set verbose to 3 to get pretty output like Crypt::Primes my $verbose = $_Config{'verbose'}; local $| = 1 if $verbose > 2; + do { require Math::BigFloat; Math::BigFloat->import(); } + if !defined $Math::BigFloat::VERSION; + # Ignore Maurer's g and c that controls how much trial division is done. my $r = Math::BigFloat->new("0.5"); # relative size of the prime q my $m = 20; # makes sure R is big enough @@ -1171,10 +1108,6 @@ sub primes { _validate_num($t, 128) || _validate_positive_integer($t, 128); croak "Random strong primes must be >= 173 bits on old Perl" if $] < 5.008 && $_Config{'maxbits'} > 32 && $t < 173; - if (!defined $Math::BigInt::VERSION) { - eval { require Math::BigInt; Math::BigInt->import(try=>'GMP,Pari'); 1; } - or do { croak "Cannot load Math::BigInt"; }; - } _set_randf() unless defined $_RANDF; my $l = (($t+1) >> 1) - 2; @@ -1234,43 +1167,26 @@ sub primorial { my($n) = @_; _validate_num($n) || _validate_positive_integer($n); - my $pn = 1; - if ($n >= (($_Config{'maxbits'} == 32) ? 29 : 53)) { - if (!defined $Math::BigInt::VERSION) { - eval { require Math::BigInt; Math::BigInt->import(try=>'GMP,Pari'); 1; } - or do { croak "Cannot load Math::BigInt"; }; - } - $pn = Math::BigInt->bone(); - } - # Make sure we use their type if they passed one in. - $pn = $_[0]->copy->bone() if ref($_[0]) eq 'Math::BigInt'; + return Math::BigInt->new(''.Math::Prime::Util::GMP::primorial($n)) + if $_HAVE_GMP && defined &Math::Prime::Util::GMP::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) ); - } else { - $pn = int( Math::Prime::Util::GMP::primorial($n) ); - } - } else { - forprimes(sub { $pn *= $_ }, $n); - } + my $max = ($_Config{'maxbits'} == 32) ? 29 : 53; + my $pn = (ref($_[0]) eq 'Math::BigInt') ? $_[0]->copy->bone() + : ($n >= $max) ? Math::BigInt->bone() + : 1; + forprimes { $pn *= $_ } $n; return $pn; } sub pn_primorial { my($n) = @_; - return primorial(nth_prime($n)) - unless $_HAVE_GMP && defined &Math::Prime::Util::GMP::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'; - if (!defined $Math::BigInt::VERSION) { - eval { require Math::BigInt; Math::BigInt->import(try=>'GMP,Pari'); 1; } - or do { croak "Cannot load Math::BigInt"; }; + if ($_HAVE_GMP && defined &Math::Prime::Util::GMP::pn_primorial) { + _validate_num($n) || _validate_positive_integer($n); + return Math::BigInt->new(''.Math::Prime::Util::GMP::pn_primorial($n)) } - return Math::BigInt->new("$pn"); + + return primorial(nth_prime($n)); } sub consecutive_integer_lcm { @@ -1278,31 +1194,23 @@ sub consecutive_integer_lcm { _validate_num($n) || _validate_positive_integer($n); return 0 if $n < 1; - my $pn = 1; my $max = ($_Config{'maxbits'} == 32) ? 22 : ($] < 5.008) ? 43 : 46; - if ($n >= $max) { - if (!defined $Math::BigInt::VERSION) { - eval { require Math::BigInt; Math::BigInt->import(try=>'GMP,Pari'); 1; } - or do { croak "Cannot load Math::BigInt"; }; - } - $pn = Math::BigInt->bone(); - } - # Ensure we use their type - $pn = $_[0]->copy->bone() if ref($_[0]) eq 'Math::BigInt'; if ($_HAVE_GMP && defined &Math::Prime::Util::GMP::consecutive_integer_lcm) { my $clcm = Math::Prime::Util::GMP::consecutive_integer_lcm($n); - return int($clcm) unless ref($pn) eq 'Math::BigInt'; - return $pn->bzero->badd("$clcm"); + return ($n < $max) ? int($clcm) : Math::BigInt->new("$clcm"); } + my $pn = (ref($_[0]) eq 'Math::BigInt') ? $_[0]->copy->bone() + : ($n >= $max) ? Math::BigInt->bone() + : 1; forprimes { my($p_power, $pmin) = ($_, int($n/$_)); $p_power *= $_ while $p_power <= $pmin; $pn *= $p_power; } $n; - return (ref($pn) eq 'Math::BigInt') ? $pn : int($pn); + return $pn; } @@ -1312,8 +1220,7 @@ sub all_factors { # In scalar context, returns sigma_0(n). Very fast. return divisor_sum($n,0) unless wantarray; - my $use_bigint = defined $bigint::VERSION - || !($n < $_Config{'maxparam'} || int($n) eq $_Config{'maxparam'}); + my $use_bigint = !($n < $_Config{'maxparam'} || int($n) eq $_Config{'maxparam'}); my @factors = factor($n); if ($n <= 0) { @factors = (); return @factors; } my %all_factors; @@ -1554,13 +1461,6 @@ sub divisor_sum { return _XS_divisor_sum($n, $k) if $n <= $_XS_MAXVAL && !$will_overflow; - if ($will_overflow) { - if (!defined $Math::BigInt::VERSION) { - eval { require Math::BigInt; Math::BigInt->import(try=>'GMP,Pari'); 1; } - or do { croak "Cannot load Math::BigInt"; }; - } - } - # The standard way is: # my $pk = $f ** $k; $product *= ($pk ** ($e+1) - 1) / ($pk - 1); # But we get less overflow using: @@ -1675,13 +1575,10 @@ sub partitions { my($n) = @_; return 1 if defined $n && $n <= 0; _validate_num($n) || _validate_positive_integer($n); - if (!defined $Math::BigInt::VERSION) { - eval { require Math::BigInt; Math::BigInt->import(try=>'GMP,Pari'); 1; } - or do { croak "Cannot load Math::BigInt"; }; - } - if ($_HAVE_GMP && defined &Math::Prime::Util::GMP::partitions) { - return Math::BigInt->new( '' . Math::Prime::Util::GMP::partitions($n) ); - } + + return Math::BigInt->new(''.Math::Prime::Util::GMP::partitions($n)) + if $_HAVE_GMP && defined &Math::Prime::Util::GMP::partitions; + my $d = int(sqrt($n+1)); my @pent = (1, map { (($_*(3*$_+1))>>1, (($_+1)*(3*$_+2))>>1) } 1 .. $d); my @part = (Math::BigInt->bone); @@ -1710,12 +1607,14 @@ sub chebyshev_psi { _validate_num($n) || _validate_positive_integer($n); return 0 if $n <= 1; return _XS_chebyshev_psi($n) if $n <= $_XS_MAXVAL; - my ($sum, $logn, $mults_are_one) = (0.0, log($n), 0); + my ($sum, $logn, $sqrtn) = (0.0, log($n), int(sqrt($n))); forprimes { my $logp = log($_); - $mults_are_one = 1 if !$mults_are_one && $_ > int($n/$_); - $sum += ($mults_are_one) ? $logp : $logp * int($logn/$logp+1e-15); - } $n; + $sum += $logp * int($logn/$logp+1e-15); + } $sqrtn; + forprimes { + $sum += log($_); + } $sqrtn+1, $n; return $sum; } @@ -1730,10 +1629,6 @@ sub carmichael_lambda { my @pe = ($n <= $_XS_MAXVAL) ? _XS_factor_exp($n) : factor_exp($n); $pe[0]->[1]-- if $pe[0]->[0] == 2 && $pe[0]->[1] > 2; - if (!defined $Math::BigInt::VERSION) { - eval { require Math::BigInt; Math::BigInt->import(try=>'GMP,Pari'); 1; } - or do { croak "Cannot load Math::BigInt"; }; - } my $lcm = Math::BigInt::blcm( map { $_->[0]->copy->bpow($_->[1]->copy->bdec)->bmul($_->[0]->copy->bdec) } map { [ map { Math::BigInt->new("$_") } @$_ ] } @@ -1750,10 +1645,7 @@ sub znorder { return if $n <= 0; return (undef,1)[$a] if $a <= 1; return 1 if $n == 1; - if (!defined $Math::BigInt::VERSION) { - eval { require Math::BigInt; Math::BigInt->import(try=>'GMP,Pari'); 1; } - or do { croak "Cannot load Math::BigInt"; }; - } + # Sadly, Calc/FastCalc are horrendously slow for this function. return if Math::BigInt::bgcd($a, $n) > 1; # Method 1: check all a^k 1 .. $n-1. @@ -1819,14 +1711,9 @@ sub znorder { sub _generic_is_prime { my($n) = @_; return 0 if defined $n && $n < 2; - if (!_validate_num($n)) { - $n = Math::BigInt->new("$n") - if defined $Math::BigInt::VERSION && ref($_[0]) ne 'Math::BigInt'; - _validate_positive_integer($n); - } + _validate_num($n) || _validate_positive_integer($n); - return _XS_is_prime($n) - if ref($_[0]) ne 'Math::BigInt' && $n <= $_XS_MAXVAL; + return _XS_is_prime($n) if $n <= $_XS_MAXVAL; return Math::Prime::Util::GMP::is_prime($n) if $_HAVE_GMP; if ($n < 7) { return ($n == 2) || ($n == 3) || ($n == 5) ? 2 : 0; } @@ -1837,14 +1724,9 @@ sub _generic_is_prime { sub _generic_is_prob_prime { my($n) = @_; return 0 if defined $n && $n < 2; - if (!_validate_num($n)) { - $n = Math::BigInt->new("$n") - if defined $Math::BigInt::VERSION && ref($_[0]) ne 'Math::BigInt'; - _validate_positive_integer($n); - } + _validate_num($n) || _validate_positive_integer($n); - return _XS_is_prob_prime($n) - if ref($_[0]) ne 'Math::BigInt' && $n <= $_XS_MAXVAL; + return _XS_is_prob_prime($n) if $n <= $_XS_MAXVAL; return Math::Prime::Util::GMP::is_prob_prime($n) if $_HAVE_GMP; if ($n < 7) { return ($n == 2) || ($n == 3) || ($n == 5) ? 2 : 0; } @@ -1856,21 +1738,15 @@ sub _generic_next_prime { my($n) = @_; _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($_[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'}; + if $n <= $_XS_MAXVAL && $n < $_Config{'maxprime'}; 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)) - : Math::Prime::Util::GMP::next_prime($n); + my $r = Math::Prime::Util::GMP::next_prime($n); + return (ref($n) eq 'Math::BigInt' || $n >= $_Config{'maxprime'}) + ? Math::BigInt->new("$r") : int($r); } - # Pass original argument to preserve bigint status + return Math::Prime::Util::PP::next_prime($_[0]); } @@ -1879,14 +1755,15 @@ sub _generic_prev_prime { _validate_num($n) || _validate_positive_integer($n); return _XS_prev_prime($n) - if ref($_[0]) ne 'Math::BigInt' && $n <= $_XS_MAXVAL; + if $n <= $_XS_MAXVAL; + 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)) - : Math::Prime::Util::GMP::prev_prime($n); + my $r = Math::Prime::Util::GMP::prev_prime($n); + return (ref($n) eq 'Math::BigInt' && $r > $_Config{'maxprime'}) + ? Math::BigInt->new("$r") : int($r); } - return Math::Prime::Util::PP::prev_prime($n); + + return Math::Prime::Util::PP::prev_prime($_[0]); } sub prime_count { @@ -1932,7 +1809,9 @@ sub nth_prime { my($n) = @_; _validate_num($n) || _validate_positive_integer($n); - return _XS_nth_prime($n) if $_Config{'xs'} && $n <= $_Config{'maxprimeidx'}; + return _XS_nth_prime($n) + if $n <= $_XS_MAXVAL && $n < $_Config{'maxprimeidx'}; + return Math::Prime::Util::PP::nth_prime($n); } @@ -1940,12 +1819,12 @@ sub factor { my($n) = @_; _validate_num($n) || _validate_positive_integer($n); - return _XS_factor($n) if ref($n) ne 'Math::BigInt' && $n <= $_XS_MAXVAL; + return _XS_factor($n) if $n <= $_XS_MAXVAL; 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) ? Math::BigInt->new(''.$_) : $_ } @factors; } return @factors; } @@ -1995,7 +1874,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($_[0]) ne 'Math::BigInt' && $n <= $_XS_MAXVAL; + if $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); @@ -2006,7 +1885,7 @@ sub is_strong_pseudoprime { _validate_num($n) || _validate_positive_integer($n); # validate bases? return _XS_miller_rabin($n, @_) - if ref($_[0]) ne 'Math::BigInt' && $n <= $_XS_MAXVAL; + if $n <= $_XS_MAXVAL; return Math::Prime::Util::GMP::is_strong_pseudoprime($n, @_) if $_HAVE_GMP; return Math::Prime::Util::PP::miller_rabin($n, @_); } @@ -2015,7 +1894,7 @@ sub is_lucas_pseudoprime { my($n) = shift; _validate_num($n) || _validate_positive_integer($n); return _XS_is_lucas_pseudoprime($n) - if ref($_[0]) ne 'Math::BigInt' && $n <= $_XS_MAXVAL; + if $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); @@ -2025,7 +1904,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($_[0]) ne 'Math::BigInt' && $n <= $_XS_MAXVAL; + if $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); @@ -2035,7 +1914,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($_[0]) ne 'Math::BigInt' && $n <= $_XS_MAXVAL; + if $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; @@ -2052,7 +1931,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($_[0]) ne 'Math::BigInt' && $n <= $_XS_MAXVAL; + if $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; @@ -2063,7 +1942,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($_[0]) ne 'Math::BigInt' && $n <= $_XS_MAXVAL; + if $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; @@ -2087,7 +1966,7 @@ sub lucas_sequence { if ref($_[0]) ne 'Math::BigInt' && $n <= $_XS_MAXVAL && ref($_[3]) ne 'Math::BigInt' && $k <= $_XS_MAXVAL; if ($_HAVE_GMP && defined &Math::Prime::Util::GMP::lucas_sequence) { - return map { ($_ > ~0) ? $n->copy->bzero->badd(''.$_) : $_ } + return map { ($_ > ~0) ? Math::BigInt->new(''.$_) : $_ } Math::Prime::Util::GMP::lucas_sequence($n, $P, $Q, $k); } return Math::Prime::Util::PP::lucas_sequence($n, $P, $Q, $k); @@ -2177,7 +2056,7 @@ sub is_provable_prime { _validate_num($n) || _validate_positive_integer($n); return _XS_is_prime($n) - if ref($_[0]) ne 'Math::BigInt' && $n <= $_XS_MAXVAL; + if $n <= $_XS_MAXVAL; return Math::Prime::Util::GMP::is_provable_prime($n) if $_HAVE_GMP && defined &Math::Prime::Util::GMP::is_provable_prime; @@ -2199,7 +2078,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($_[0]) ne 'Math::BigInt' && $n <= $_XS_MAXVAL) { + if ($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"); @@ -2449,7 +2328,8 @@ sub nth_prime_approx { return $_primes_small[$n] if $n <= $#_primes_small; - $n = _upgrade_to_float($n) if ref($_[0]) eq 'Math::BigInt'; + $n = _upgrade_to_float($n) + if ref($n) eq 'Math::BigInt' || $n >= $_Config{'maxprimeidx'}; my $flogn = log($n); my $flog2n = log($flogn); @@ -2488,11 +2368,6 @@ sub nth_prime_approx { # $approx = -0.025 is better for the last, but it gives problems with some # other code that always wants the asymptotic approximation to be >= actual. - if ( ($approx >= ~0) && (ref($approx) ne 'Math::BigFloat') ) { - return $_Config{'maxprime'} if $n <= $_Config{'maxprimeidx'}; - croak "nth_prime_approx($n) overflow"; - } - return int($approx + 0.5); } @@ -2503,7 +2378,8 @@ sub nth_prime_lower { return $_primes_small[$n] if $n <= $#_primes_small; - $n = _upgrade_to_float($n) if ref($_[0]) eq 'Math::BigInt'; + $n = _upgrade_to_float($n) + if ref($n) eq 'Math::BigInt' || $n > $_Config{'maxprimeidx'}; my $flogn = log($n); my $flog2n = log($flogn); # Note distinction between log_2(n) and log^2(n) @@ -2513,11 +2389,6 @@ sub nth_prime_lower { # Dusart 2010 page 2, for all n >= 3 my $lower = $n * ($flogn + $flog2n - 1.0 + (($flog2n-2.10)/$flogn)); - if ( ($lower >= ~0) && (ref($lower) ne 'Math::BigFloat') ) { - return $_Config{'maxprime'} if $n <= $_Config{'maxprimeidx'}; - croak "nth_prime_lower($n) overflow"; - } - return int($lower); } @@ -2528,7 +2399,8 @@ sub nth_prime_upper { return $_primes_small[$n] if $n <= $#_primes_small; - $n = _upgrade_to_float($n) if ref($_[0]) eq 'Math::BigInt'; + $n = _upgrade_to_float($n) + if ref($n) eq 'Math::BigInt' || $n >= $_Config{'maxprimeidx'}; my $flogn = log($n); my $flog2n = log($flogn); # Note distinction between log_2(n) and log^2(n) @@ -2546,11 +2418,6 @@ sub nth_prime_upper { $upper = $n * ( $flogn + $flog2n ); } - if ( ($upper >= ~0) && (ref($upper) ne 'Math::BigFloat') ) { - return $_Config{'maxprime'} if $n <= $_Config{'maxprimeidx'}; - croak "nth_prime_upper($n) overflow"; - } - return int($upper + 1.0); } @@ -2772,14 +2639,12 @@ L<Math::Factoring>, and L<Math::Primality> (when the GMP module is available). For numbers in the 10-20 digit range, it is often orders of magnitude faster. Typically it is faster than L<Math::Pari> for 64-bit operations. -All operations support both Perl UV's (32-bit or 64-bit) and bignums. It -requires no external software for big number support, as there are Perl -implementations included that solely use Math::BigInt and Math::BigFloat. -B<If you want high performance with big numbers (larger than Perl's UV -size), you should install L<Math::Prime::Util::GMP>>. This will be a -recurring theme throughout this documentation -- while all bignum operations -are supported in pure Perl, most methods will be much slower than the C+GMP -alternative. +All operations support both Perl UV's (32-bit or 64-bit) and bignums. If +you want high performance with big numbers (larger than Perl's native 32-bit +or 64-bit size), you should install L<Math::Prime::Util::GMP> and +L<Math::BigInt::GMP>. This will be a recurring theme throughout this +documentation -- while all bignum operations are supported in pure Perl, +most methods will be much slower than the C+GMP alternative. The module is thread-safe and allows concurrency between Perl threads while still sharing a prime cache. It is not itself multi-threaded. See the @@ -2806,15 +2671,9 @@ bigint and expression inputs. =head1 BIGNUM SUPPORT -By default all functions support bignums. With a few exceptions, the module -will not turn on bignum support for you -- you will need to C<use bigint>, -C<use bignum>, or pass in a L<Math::BigInt> or L<Math::BigFloat> object as -your input. The functions take some care to perform all bignum operations -using the same class as was passed in, allowing the module to work properly -with Calc, FastCalc, GMP, Pari, etc. You should try to install -L<Math::Prime::Util::GMP> if you plan to use bigints with this module, as -it will make it run much faster. - +By default all functions support bignums. For performance, you should +install and use L<Math::BigInt::GMP> or L<Math::BigInt::Pari>, and +L<Math::Prime::Util::GMP>. Some of the functions, including: diff --git a/lib/Math/Prime/Util/PP.pm b/lib/Math/Prime/Util/PP.pm index f65b106..dea5f81 100644 --- a/lib/Math/Prime/Util/PP.pm +++ b/lib/Math/Prime/Util/PP.pm @@ -2,6 +2,7 @@ package Math::Prime::Util::PP; use strict; use warnings; use Carp qw/carp croak confess/; +use Math::BigInt try=>"GMP,Pari"; BEGIN { $Math::Prime::Util::PP::AUTHORITY = 'cpan:DANAJ'; @@ -91,21 +92,12 @@ sub _validate_positive_integer { if ref($n) ne 'Math::BigInt' && $n =~ tr/0123456789//c; croak "Parameter '$n' must be >= $min" if defined $min && $n < $min; croak "Parameter '$n' must be <= $max" if defined $max && $n > $max; - if (ref($_[0])) { - $_[0] = Math::BigInt->new("$_[0]") unless ref($_[0]) eq 'Math::BigInt'; - # Workarounds for Math::BigInt::GMP RT # 71548 and Perl 5.6 - if ($_[0]->bacmp(''.~0) <= 0) { - my $intn = int($_[0]->bstr); - $_[0] = $intn if $_[0]->bcmp("$intn") == 0; - } + $_[0] = Math::BigInt->new("$_[0]") unless ref($_[0]) eq 'Math::BigInt'; + if ($_[0]->bacmp(''.~0) <= 0) { + $_[0] = int($_[0]->bstr); + } else { # Stop BigFloat upgrade $_[0]->upgrade(undef) if ref($_[0]) && $_[0]->upgrade(); - } else { - if ($n > ~0) { - croak "Parameter '$n' outside of integer range" if !defined $bigint::VERSION; - $_[0] = Math::BigInt->new("$n"); # Make $n a proper bigint object - $_[0]->upgrade(undef) if $_[0]->upgrade(); # Stop BigFloat upgrade - } } # One of these will be true: # 1) $n <= ~0 and $n is not a bigint @@ -400,12 +392,14 @@ sub primes { sub next_prime { my($n) = @_; _validate_positive_integer($n); - if ($n >= ((_PP_prime_maxbits == 32) ? 4294967291 : 18446744073709551557)) { - return 0 if ref($_[0]) ne 'Math::BigInt'; - $n = $_[0]; # $n is a bigint now - } + return $_prime_next_small[$n] if $n <= $#_prime_next_small; + if (ref($n) ne 'Math::BigInt' && + $n >= ((_PP_prime_maxbits == 32) ? 4294967291 : 18446744073709551557)) { + $n = Math::BigInt->new(''.$n); + } + # Be careful trying to do: # my $d = int($n/30); # my $m = $n - $d*30; @@ -619,16 +613,14 @@ sub nth_prime { return $_primes_small[$n] if $n <= $#_primes_small; - if (!defined $bigint::VERSION) { # This isn't ideal. - if (_PP_prime_maxbits == 32) { - croak "nth_prime($n) overflow" if $n > 203280221; - } else { - croak "nth_prime($n) overflow" if $n > 425656284035217743; - } + my $max = (_PP_prime_maxbits == 32) ? 203280221 : 425656284035217743; + if ($n > $max && ref($n) ne 'Math::BigFloat') { + do { require Math::BigFloat; Math::BigFloat->import(); } + if !defined $Math::BigFloat::VERSION; + $n = Math::BigFloat->new("$n") } my $prime = 0; - my $count = 1; my $start = 3; @@ -959,13 +951,7 @@ sub lucas_sequence { croak "lucas_sequence: P out of range" if $P < 0 || $P >= $n; croak "lucas_sequence: Q out of range" if $Q >= $n; - if (ref($n) ne '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 "; } - } - $n = Math::BigInt->new("$n"); - } + $n = Math::BigInt->new("$n") unless ref($n) eq 'Math::BigInt'; my $ZERO = $n->copy->bzero; my $ONE = $ZERO + 1; @@ -1111,13 +1097,7 @@ sub is_extra_strong_lucas_pseudoprime { } # We have to convert n to a bigint or Math::BigInt::GMP's stupid set_si bug # (RT 71548) will hit us and make the test $V == $n-2 always return false. - if (ref($n) ne '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 "; } - } - $n = Math::BigInt->new("$n"); - } + $n = Math::BigInt->new("$n") unless ref($n) eq 'Math::BigInt'; my($U, $V, $Qk) = lucas_sequence($n, $P, $Q, $k); return 1 if $U->is_zero && ($V == 2 || $V == ($n-2)); @@ -1142,13 +1122,7 @@ sub is_almost_extra_strong_lucas_pseudoprime { return 0 if $D == 0; # We found a divisor in the sequence die "Lucas parameter error: $D, $P, $Q\n" if ($D != $P*$P - 4*$Q); - if (ref($n) ne '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 "; } - } - $n = Math::BigInt->new("$n"); - } + $n = Math::BigInt->new("$n") unless ref($n) eq 'Math::BigInt'; my $ZERO = $n->copy->bzero; my $V = $ZERO + $P; # V_{k} @@ -1183,13 +1157,7 @@ sub is_frobenius_underwood_pseudoprime { return 0 if ($n % 2) == 0; return 0 if _is_perfect_square($n); - if (ref($n) ne '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 "; } - } - $n = Math::BigInt->new("$n"); - } + $n = Math::BigInt->new("$n") unless ref($n) eq 'Math::BigInt'; my $ZERO = $n->copy->bzero; my $fa = $ZERO + 1; @@ -1302,19 +1270,13 @@ sub _test_anr { sub is_aks_prime { my $n = shift; - if (!defined $Math::BigInt::VERSION) { - eval { require Math::BigInt; Math::BigInt->import(try=>'GMP,Pari'); 1; } - or do { croak "Cannot load Math::BigInt "; } - } - if (!defined $Math::BigFloat::VERSION) { - eval { require Math::BigFloat; Math::BigFloat->import(); 1; } - or do { croak "Cannot load Math::BigFloat "; } - } $n = Math::BigInt->new("$n") unless ref($n) eq 'Math::BigInt'; return 0 if $n < 2; return 0 if _is_perfect_power($n); + do { require Math::BigFloat; Math::BigFloat->import(); } + if !defined $Math::BigFloat::VERSION; # limit = floor( log2(n) * log2(n) ). o_r(n) must be larger than this my $floatn = Math::BigFloat->new($n); my $sqrtn = int($floatn->copy->bsqrt->bfloor->bstr); @@ -2109,10 +2071,8 @@ sub ExponentialIntegral { my $wantbf = 0; my $xdigits = 17; if (defined $bignum::VERSION || ref($x) =~ /^Math::Big/) { - if (!defined $Math::BigFloat::VERSION) { - eval { require Math::BigFloat; Math::BigFloat->import(); 1; } - or do { croak "Cannot load Math::BigFloat "; } - } + do { require Math::BigFloat; Math::BigFloat->import(); } + if !defined $Math::BigFloat::VERSION; $x = Math::BigFloat->new("$x") if ref($x) ne 'Math::BigFloat'; $wantbf = 1; $xdigits = $x->accuracy || Math::BigFloat->accuracy() || Math::BigFloat->div_scale(); @@ -2213,10 +2173,8 @@ sub LogarithmicIntegral { my $wantbf = 0; my $xdigits = 17; if (defined $bignum::VERSION || ref($x) =~ /^Math::Big/) { - if (!defined $Math::BigFloat::VERSION) { - eval { require Math::BigFloat; Math::BigFloat->import(); 1; } - or do { croak "Cannot load Math::BigFloat "; } - } + do { require Math::BigFloat; Math::BigFloat->import(); } + if !defined $Math::BigFloat::VERSION; $x = Math::BigFloat->new("$x") if ref($x) ne 'Math::BigFloat'; $wantbf = 1; $xdigits = $x->accuracy || Math::BigFloat->accuracy() || Math::BigFloat->div_scale(); @@ -2340,10 +2298,8 @@ sub RiemannZeta { my $wantbf = 0; my $xdigits = 17; if (defined $bignum::VERSION || ref($x) =~ /^Math::Big/) { - if (!defined $Math::BigFloat::VERSION) { - eval { require Math::BigFloat; Math::BigFloat->import(); 1; } - or do { croak "Cannot load Math::BigFloat "; } - } + do { require Math::BigFloat; Math::BigFloat->import(); } + if !defined $Math::BigFloat::VERSION; if (ref($x) eq 'Math::BigInt') { my $xacc = $x->accuracy(); $x = Math::BigFloat->new($x); @@ -2431,10 +2387,8 @@ sub RiemannR { my $wantbf = 0; my $xdigits = 17; if (defined $bignum::VERSION || ref($x) =~ /^Math::Big/) { - if (!defined $Math::BigFloat::VERSION) { - eval { require Math::BigFloat; Math::BigFloat->import(); 1; } - or do { croak "Cannot load Math::BigFloat "; } - } + do { require Math::BigFloat; Math::BigFloat->import(); } + if !defined $Math::BigFloat::VERSION; if (ref($x) eq 'Math::BigInt') { my $xacc = $x->accuracy(); $x = Math::BigFloat->new($x); diff --git a/lib/Math/Prime/Util/PrimeIterator.pm b/lib/Math/Prime/Util/PrimeIterator.pm index 0de15c5..68d9fb9 100644 --- a/lib/Math/Prime/Util/PrimeIterator.pm +++ b/lib/Math/Prime/Util/PrimeIterator.pm @@ -15,10 +15,6 @@ our %EXPORT_TAGS = (all => [ @EXPORT_OK ]); use Math::Prime::Util qw/next_prime prev_prime is_prime prime_count nth_prime/; use Math::BigInt try => "GMP,Pari"; -my $bigprime = Math::BigInt->new( - (~0 == 4294967295) ? "4294967311" : "18446744073709551629" -); - # We're going to use a scalar rather than a hash because there is currently # only one data object (the current value) and this makes it little faster. @@ -41,7 +37,7 @@ sub __iter__ { sub value { ${$_[0]}; } sub next { my $self = shift; - $$self = next_prime($$self) || $bigprime; + $$self = next_prime($$self); return $self; } sub prev { @@ -53,7 +49,7 @@ sub prev { sub iterate { my $self = shift; my $p = $$self; - $$self = next_prime($p) || $bigprime; + $$self = next_prime($p); return $p; } @@ -63,17 +59,14 @@ sub rewind { if (defined $start && $start ne '2') { Math::Prime::Util::_validate_num($start) || Math::Prime::Util::_validate_positive_integer($start); - if ($start > 2) { - $$self = next_prime($start-1) || $bigprime; - } + $$self = next_prime($start-1) if $start > 2; } return $self; } sub peek { my $self = shift; - my $np = next_prime($$self) || $bigprime; - return $np; + return next_prime($$self); } # Some methods to match Math::NumSeq diff --git a/lib/Math/Prime/Util/ZetaBigFloat.pm b/lib/Math/Prime/Util/ZetaBigFloat.pm index 2c0d9e3..d837fcd 100644 --- a/lib/Math/Prime/Util/ZetaBigFloat.pm +++ b/lib/Math/Prime/Util/ZetaBigFloat.pm @@ -7,6 +7,7 @@ BEGIN { $Math::Prime::Util::ZetaBigFloat::VERSION = '0.34'; } +use Math::BigInt try => "GMP,Pari"; use Math::BigFloat; # Riemann Zeta($k) for integer $k. diff --git a/t/12-nextprime.t b/t/12-nextprime.t index 35a1f21..8bf6316 100644 --- a/t/12-nextprime.t +++ b/t/12-nextprime.t @@ -78,9 +78,9 @@ is( prev_prime(19610), 19609, "prev prime of 19610 is 19609" ); is( prev_prime(2), 0, "Previous prime of 2 returns 0" ); if ($use64) { - is( next_prime(18446744073709551611), 0, "Next prime of ~0-4 returns 0" ); + is( next_prime(18446744073709551611), "18446744073709551629", "Next prime of ~0-4 returns bigint next prime" ); } else { - is( next_prime(4294967291), 0, "Next prime of ~0-4 returns 0" ); + is( next_prime(4294967291), "4294967311", "Next prime of ~0-4 returns bigint next prime" ); } # Turns out the testing of prev/next from 0-3572 still misses some cases. diff --git a/t/14-nthprime.t b/t/14-nthprime.t index acfe551..d3b7438 100644 --- a/t/14-nthprime.t +++ b/t/14-nthprime.t @@ -58,7 +58,6 @@ plan tests => 0 + 2*scalar(keys %pivals32) + 3*scalar(keys %nthprimes32) + scalar(keys %nthprimes_small) + $use64 * 3 * scalar(keys %nthprimes64) - + 4 + 3 + (($extra && $use64 && $usexs) ? 1 : 0); @@ -102,20 +101,10 @@ my $maxindexp1 = $use64 ? 425656284035217744 : 203280222; my $maxprime = $use64 ? 18446744073709551557 : 4294967291; cmp_ok( nth_prime_lower($maxindex), '<=', $maxprime, "nth_prime_lower(maxindex) <= maxprime"); cmp_ok( nth_prime_upper($maxindex), '>=', $maxprime, "nth_prime_upper(maxindex) >= maxprime"); -cmp_ok( nth_prime_approx($maxindex), '==', $maxprime, "nth_prime_approx(maxindex) == maxprime"); cmp_ok( nth_prime_lower($maxindexp1), '>=', nth_prime_lower($maxindex), "nth_prime_lower(maxindex+1) >= nth_prime_lower(maxindex)"); my $overindex = ($broken64) ? 425656284035217843 : $maxindexp1; -eval { nth_prime_upper($overindex); }; -like($@, qr/overflow/, "nth_prime_upper($overindex) overflows"); - -eval { nth_prime_approx($overindex); }; -like($@, qr/overflow/, "nth_prime_approx($overindex) overflows"); - -eval { nth_prime($overindex); }; -like($@, qr/overflow/, "nth_prime($overindex) overflows"); - if ($extra && $use64 && $usexs) { # Test an nth prime value that uses the binary-search-on-R(n) algorithm is( nth_prime(21234567890), 551990503367, "nth_prime(21234567890)" ); diff --git a/t/80-pp.t b/t/80-pp.t index 12a31f0..0b269cd 100644 --- a/t/80-pp.t +++ b/t/80-pp.t @@ -355,9 +355,9 @@ is( prev_prime(19610), 19609, "prev prime of 19610 is 19609" ); is( prev_prime(2), 0, "Previous prime of 2 returns 0" ); if ($use64) { - is( next_prime(18446744073709551611), 0, "Next prime of ~0-4 returns 0" ); + is( next_prime(18446744073709551611), "18446744073709551629", "Next prime of ~0-4 returns bigint next prime" ); } else { - is( next_prime(4294967291), 0, "Next prime of ~0-4 returns 0" ); + is( next_prime(4294967291), "4294967311", "Next prime of ~0-4 returns bigint next prime" ); } { -- 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