This is an automated email from the git hooks/post-receive script.
ppm-guest pushed a commit to annotated tag v0.40
in repository libmath-prime-util-perl.
commit f74438fe6bdc0c3dfb3002e0aeed2db29251f2ae
Author: Dana Jacobsen <d...@acm.org>
Date: Tue Mar 4 18:53:58 2014 -0800
Documentation updates
---
lib/Math/Prime/Util.pm | 221 ++++++++++++++++++++++++--------------------
t/92-release-pod-coverage.t | 2 +
2 files changed, 122 insertions(+), 101 deletions(-)
diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm
index d9c2a10..ac134a3 100644
--- a/lib/Math/Prime/Util.pm
+++ b/lib/Math/Prime/Util.pm
@@ -47,6 +47,9 @@ our @EXPORT_OK =
);
our %EXPORT_TAGS = (all => [ @EXPORT_OK ]);
+# These are only exported if specifically asked for
+push @EXPORT_OK, (qw/trial_factor fermat_factor holf_factor squfof_factor
prho_factor pbrent_factor pminus1_factor pplus1_factor/);
+
my %_Config;
# Similar to how boolean handles its option
@@ -1356,10 +1359,6 @@ Returning composite for all non-2 even input makes the
function match most
other implementations including L<Math::Primality>'s C<is_strong_pseudoprime>
function.
-=head2 miller_rabin
-
-An alias for C<is_strong_pseudoprime>. This name is deprecated.
-
=head2 is_lucas_pseudoprime
Takes a positive number as input, and returns 1 if the input is a standard
@@ -1763,6 +1762,14 @@ literally B<millions> of times slower than other
algorithms. From R.P.
Brent, 2010: "AKS is not a practical algorithm. ECPP is much faster."
We have ECPP, and indeed it is much faster.
+This implementation includes the v6 improvements from Lenstra as well as
+further improvements from Bernstein and Voloch. It runs substantially
+faster than the original or v6 versions. The GMP implementation uses
+a binary segmentation method for modular polynomial multiplication
+(see Bernstein's 2007 Quartic paper), which reduces to a single scalar
+multiplication, at which GMP excels. Because of this, the GMP
+implementation is likely to be faster once the input is larger than C<2^32>.
+
=head2 is_power
@@ -1776,10 +1783,10 @@ the largest possible. This can be used in a boolean
statement to
determine if C<n> is a perfect power.
If given two arguments C<n> and C<k>, returns 1 if C<n> is a C<k-th> power,
-and 0 otherwise.
+and 0 otherwise. For example, if C<k=2> then this detects perfect squares.
This corresponds to Pari/GP's C<ispower> function, with the limitations of
-only integer arguments and no third argument may be given returning the root.
+only integer arguments and no third argument may be given to return the root.
=head2 lucas_sequence
@@ -2053,29 +2060,31 @@ coprime to C<n>. This is L<OEIS series
A002322|http://oeis.org/A002322>.
=head2 kronecker
Returns the Kronecker symbol C<(a|n)> for two integers. The possible
-return values with their meanings for odd positive C<n> are:
+return values with their meanings for odd prime C<n> are:
0 a = 0 mod n
- 1 a is a quadratic residue modulo n (a = x^2 mod n for some x)
- -1 a is a quadratic non-residue modulo n
+ 1 a is a quadratic residue mod n (a = x^2 mod n for some x)
+ -1 a is a quadratic non-residue mod n (no a where a = x^2 mod n)
The Kronecker symbol is an extension of the Jacobi symbol to all integer
values of C<n> from the latter's domain of positive odd values of C<n>.
The Jacobi symbol is itself an extension of the Legendre symbol, which is
only defined for odd prime values of C<n>. This corresponds to Pari's
-C<kronecker(a,n)> function and Mathematica's C<KroneckerSymbol[n,m]>
-function.
+C<kronecker(a,n)> function, Mathematica's C<KroneckerSymbol[n,m]>
+function, and GMP's C<mpz_kronecker(a,n)>, C<mpz_jacobi(a,n)>, and
+C<mpz_legendre(a,n)> functions.
+
=head2 znorder
- $order = znorder(2, next_prime(10**19)-6);
+ $order = znorder(2, next_prime(10**16)-6);
Given two positive integers C<a> and C<n>, returns the multiplicative order
of C<a> modulo C<n>. This is the smallest positive integer C<k> such that
C<a^k ≡ 1 mod n>. Returns 1 if C<a = 1>. Returns undef if C<a = 0> or if
C<a> and C<n> are not coprime, since no value will result in 1 mod n.
This corresponds to Pari's C<znorder(Mod(a,n))> function and Mathematica's
-C<MultiplicativeOrder[n]> function.
+C<MultiplicativeOrder[a,n]> function.
=head2 znprimroot
@@ -2362,6 +2371,7 @@ in place because you still have an object.
Returns a reference to a hash of the current settings. The hash is copy of
the configuration, so changing it has no effect. The settings include:
+ verbose verbose level. 1 or more will result in extra output.
precalc_to primes up to this number are calculated
maxbits the maximum number of bits for native operations
xs 0 or 1, indicating the XS code is available
@@ -2378,26 +2388,35 @@ the configuration, so changing it has no effect. The
settings include:
Allows setting of some parameters. Currently the only parameters are:
- xs Allows turning off the XS code, forcing the Pure Perl
- code to be used. Set to 0 to disable XS, set to 1 to
- re-enable. You probably will never want to do this.
-
- gmp Allows turning off the use of L<Math::Prime::Util::GMP>,
- which means using Pure Perl code for big numbers. Set
- to 0 to disable GMP, set to 1 to re-enable.
- You probably will never want to do this.
-
- assume_rh Allows functions to assume the Riemann hypothesis is
- true if set to 1. This defaults to 0. Currently this
- setting only impacts prime count lower and upper
- bounds, but could later be applied to other areas such
- as primality testing. A later version may also have a
- way to indicate whether no RH, RH, GRH, or ERH is to
- be assumed.
-
- irand Takes a code ref to an irand function returning a
- uniform number between 0 and 2**32-1. This will be
- used for all random number generation in the module.
+ verbose The default setting of 0 will generate no extra output.
+ Setting to 1 or higher results in extra output. For
+ example, at setting 1 the AKS algorithm will indicate
+ the chosen r and s values. At setting 2 it will output
+ a sequence of dots indicating progress. Similarly, for
+ random_maurer_prime, setting 3 shows real time progress.
+ Factoring large numbers is another place where verbose
+ settings can give progress indications.
+
+ xs Allows turning off the XS code, forcing the Pure Perl
+ code to be used. Set to 0 to disable XS, set to 1 to
+ re-enable. You probably will never want to do this.
+
+ gmp Allows turning off the use of L<Math::Prime::Util::GMP>,
+ which means using Pure Perl code for big numbers. Set
+ to 0 to disable GMP, set to 1 to re-enable.
+ You probably will never want to do this.
+
+ assume_rh Allows functions to assume the Riemann hypothesis is
+ true if set to 1. This defaults to 0. Currently this
+ setting only impacts prime count lower and upper
+ bounds, but could later be applied to other areas such
+ as primality testing. A later version may also have a
+ way to indicate whether no RH, RH, GRH, or ERH is to
+ be assumed.
+
+ irand Takes a code ref to an irand function returning a
+ uniform number between 0 and 2**32-1. This will be
+ used for all random number generation in the module.
=head1 FACTORING FUNCTIONS
@@ -2418,21 +2437,18 @@ C<PrimeOmega[n]> function.
This is same result that we would get if we evaluated the resulting
array in scalar context.
-The current algorithm for non-bigints is a sequence of small trial division,
-a few rounds of Pollard's Rho, SQUFOF, Pollard's p-1, Hart's OLF, a long
-run of Pollard's Rho, and finally trial division if anything survives. This
-process is repeated for each non-prime factor. In practice, it is very rare
-to require more than the first Rho + SQUFOF to find a factor, and I have not
-seen anything go to the last step.
+The current algorithm does a little trial division, a check for perfect
+powers, followed by combinations of Pollard's Rho, SQUFOF, and Pollard's
+p-1. The combination is applied to each non-prime factor found.
Factoring bigints works with pure Perl, and can be very handy on 32-bit
machines for numbers just over the 32-bit limit, but it can be B<very> slow
-for "hard" numbers. Installing the L<Math::Prime::Util::GMP> module will speed
-up bigint factoring a B<lot>, and all future effort on large number factoring
-will be in that module. If you do not have that module for some reason, use
-the GMP or Pari version of bigint if possible
-(e.g. C<use bigint try =E<gt> 'GMP,Pari'>), which will run 2-3x faster (though
-still 100x slower than the real GMP code).
+for "hard" numbers. Installing the L<Math::Prime::Util::GMP> module will
+speed up bigint factoring a B<lot>, and all future effort on large number
+factoring will be in that module. If you do not have that module for
+some reason, use the GMP or Pari version of bigint if possible
+(e.g. C<use bigint try =E<gt> 'GMP,Pari'>), which will run 2-3x faster
+(though still 100x slower than the real GMP code).
=head2 factor_exp
@@ -2460,8 +2476,6 @@ Just the way the factors are arranged is different.
=head2 divisors
-=head2 all_factors
-
my @divisors = divisors(30); # returns (1, 2, 3, 5, 6, 10, 15, 30)
Produces all the divisors of a positive number input, including 1 and
@@ -2483,9 +2497,10 @@ C<all_factors> is the deprecated name for this function.
my @factors = trial_factor($n);
-Produces the prime factors of a positive number input. The factors will be
-in numerical order.
+Produces the prime factors of a positive number input.
+The factors will be in numerical order.
For large inputs this will be very slow.
+Not exported.
=head2 fermat_factor
@@ -2506,7 +2521,7 @@ optional number of rounds can be given as a second
parameter. It is possible
the function will be unable to find a factor, in which case a single element,
the input, is returned. This uses Hart's One Line Factorization with no
premultiplier. It is an interesting alternative to Fermat's algorithm,
-and there are some inputs it can rapidly factor. In the long run it has the
+and there are some inputs it can rapidly factor. Overall it has the
same advantages and disadvantages as Fermat's method.
=head2 squfof_factor
@@ -2741,11 +2756,10 @@ Project Euler, problem 10 (summation of primes):
Project Euler, problem 21 (Amicable numbers):
use Math::Prime::Util qw/divisor_sum/;
- sub dsum { my $n = shift; divisor_sum($n) - $n; }
my $sum = 0;
- foreach my $a (1..10000) {
- my $b = dsum($a);
- $sum += $a + $b if $b > $a && dsum($b) == $a;
+ foreach my $x (1..10000) {
+ my $y = divisor_sum($x)-$x;
+ $sum += $x + $y if $y > $x && $x == divisor_sum($y)-$y;
}
say $sum;
@@ -2764,12 +2778,12 @@ Project Euler, problem 47 (Distinct primes factors):
Project Euler, problem 69, stupid brute force solution (about 1 second):
use Math::Prime::Util qw/euler_phi/;
- my ($n, $max) = (0,0);
- do {
- my $ndivphi = $_ / euler_phi($_);
- ($n, $max) = ($_, $ndivphi) if $ndivphi > $max;
- } for 1..1000000;
- say "$n $max";
+ my ($maxn, $maxratio) = (0,0);
+ foreach my $n (1..1000000) {
+ my $ndivphi = $n / euler_phi($n);
+ ($maxn, $maxratio) = ($n, $ndivphi) if $ndivphi > $maxratio;
+ }
+ say "$maxn $maxratio";
Here is the right way to do PE problem 69 (under 0.03s):
@@ -2880,13 +2894,14 @@ the first C<k> prime bases, but not much. See, for
example, Nicely's
L<mpz_probab_prime_p pseudoprimes|http://www.trnicely.net/misc/mpzspsp.html>
page.
-=item L<Math::Pari>
+=item L<Math::Pari> (not recent Pari/GP)
Pari 2.1.7 is the default version installed with the L<Math::Pari>
module. It uses 10 random M-R bases (the PRNG uses a fixed seed
set at compile time). Pari 2.3.0 was released in May 2006 and it,
like all later releases through at least 2.6.1, use BPSW / APRCL,
-after complaints of false results from using M-R tests.
+after complaints of false results from using M-R tests. For example,
+it will indicate 9 is prime about 1 out of every 276k calls.
=back
@@ -2930,7 +2945,7 @@ Perl threads.
This section describes other CPAN modules available that have some feature
overlap with this one. Also see the L</REFERENCES> section. Please let me
know if any of this information is inaccurate. Also note that just because
-a module doesn't match what I believe are the best set of features, doesn't
+a module doesn't match what I believe are the best set of features doesn't
mean it isn't perfect for someone else.
I will use SoE to indicate the Sieve of Eratosthenes, and MPU to denote this
@@ -2963,7 +2978,7 @@ MPXS's prime sieve is an unoptimized non-segmented SoE
which returns an array. Sieve bases larger than C<10^7> start taking
inordinately long and using a lot of memory (gigabytes beyond C<10^10>).
E.g. C<primes(10**9, 10**9+1000)> takes 36 seconds with MPXS, but only
-0.00015 seconds with MPU.
+0.0001 seconds with MPU.
L<Math::Prime::FastSieve> supports C<primes>, C<is_prime>, C<next_prime>,
C<prev_prime>, C<prime_count>, and C<nth_prime>. The caveat is that all
@@ -2981,7 +2996,7 @@ the XS sieves, and has the most memory use. It is faster
than pure Perl code.
L<Crypt::Primes> supports C<random_maurer_prime> functionality. MPU has
more options for random primes (n-digit, n-bit, ranged, and strong) in
addition to Maurer's algorithm. MPU does not have the critical bug
-L<RT81858|https://rt.cpan.org/Ticket/Display.html?id=81858>. MPU should have
+L<RT81858|https://rt.cpan.org/Ticket/Display.html?id=81858>. MPU has
a more uniform distribution as well as return a larger subset of primes
(L<RT81871|https://rt.cpan.org/Ticket/Display.html?id=81871>).
MPU does not depend on L<Math::Pari> though can run slow for bigints unless
@@ -2996,9 +3011,9 @@ What Crypt::Primes has that MPU does not is the ability
to return a generator.
L<Math::Factor::XS> calculates prime factors and factors, which correspond to
the L</factor> and L</divisors> functions of MPU. These functions do
not support bigints. Both are implemented with trial division, meaning they
-are very fast for really small values, but quickly become unusably slow
-(factoring 19 digit semiprimes is over 700 times slower). The function
-C<count_prime_factors> can be done in MPU using C<scalar factor($n)>.
+are very fast for really small values, but become very slow as the input
+gets larger (factoring 19 digit semiprimes is over 1000 times slower). The
+function C<count_prime_factors> can be done in MPU using C<scalar factor($n)>.
See the L</"EXAMPLES"> section for a 2-line function replicating C<matches>.
L<Math::Big> version 1.12 includes C<primes> functionality. The current
@@ -3066,8 +3081,11 @@ Some of the highlights:
The default L<Math::Pari> is built with Pari 2.1.7. This uses 10 M-R
tests with randomly chosen bases (fixed seed, but doesn't reset each
invocation like GMP's C<is_probab_prime>). This has a greater chance
-of false positives compared to the BPSW test. Calling with
-C<isprime($n,1)> will perform a Pocklington-Lehmer C<n-1> proof,
+of false positives compared to the BPSW test -- some composites such as
+C<9>, C<88831>, C<38503>, etc.
+(L<OEIS A141768|http://oeis.org/A141768>)
+have a surprisingly high chance of being indicated prime.
+Using C<isprime($n,1)> will perform a Pocklington-Lehmer C<n-1> proof,
but this becomes unreasonably slow past 70 or so digits.
If L<Math::Pari> is built using Pari 2.3.5 (this requires manual
@@ -3138,14 +3156,14 @@ more efficient. Without L<Math::Prime::Util::GMP>
installed, MPU is
very slow with bigints. With it installed, it is about 2x slower than
Math::Pari.
-=item C<gcd>, C<lcm>, C<kronecker>, C<znorder>, C<znprimroot>
+=item C<gcd>, C<lcm>, C<kronecker>, C<znorder>, C<znprimroot>, C<znlog>
Similar to MPU's L</gcd>, L</lcm>, L</kronecker>, L</znorder>,
-and L</znprimroot>. Pari's C<znprimroot> only returns the smallest
-root for prime powers. The behavior is undefined when the group is
+L</znprimroot>, and L</znlog>. Pari's C<znprimroot> only returns the
+smallest root for prime powers. The behavior is undefined when the group is
not cyclic (sometimes it throws an exception, sometimes it returns
-an incorrect answer). MPU's L</znprimroot> will always return the
-smallest root if it exists, and C<undef> otherwise.
+an incorrect answer, sometimes it hangs). MPU's L</znprimroot> will always
+return the smallest root if it exists, and C<undef> otherwise.
=item C<sigma>
@@ -3170,10 +3188,11 @@ function supports negative and complex inputs.
=back
Overall, L<Math::Pari> supports a huge variety of functionality and has a
-sophisticated and mature code base behind it (noting that the default version
-of Pari used is about 10 years old now).
-For native integers often using Math::Pari will be slower, but bigints are
-often superior and it rarely has any performance surprises. Some of the
+sophisticated and mature code base behind it (noting that the Pari library
+used is about 10 years old now).
+For native integers, typically Math::Pari will be slower than MPU. For
+bigints, Math::Pari may be superior and it rarely has any performance
+surprises. Some of the
unique features MPU offers include super fast prime counts, nth_prime,
ECPP primality proofs with certificates, approximations and limits for both,
random primes, fast Mertens calculations, Chebyshev theta and psi functions,
@@ -3204,7 +3223,7 @@ candidates. A test such as the BPSW test in this module
is then recommended.
L<Primo|http://www.ellipsa.eu/> is the best method for open source primality
proving for inputs over 1000 digits. Primo also does well below that size,
but other good alternatives are
-L<WraithX APRCL|http://sourceforge.net/projects/mpzaprcl/>,
+David Cleaver's L<mpzaprcl|http://sourceforge.net/projects/mpzaprcl/>,
the APRCL from the modern L<Pari|http://pari.math.u-bordeaux.fr/> package,
or the standalone ECPP from this module with large polynomial set.
@@ -3337,7 +3356,7 @@ are still being tuned. L<Math::Factor::XS> is very fast
when given input with
only small factors, but it slows down rapidly as the smallest factor increases
in size. For numbers larger than 32 bits, L<Math::Prime::Util> can be 100x or
more faster (a number with only very small factors will be nearly identical,
-while a semiprime with large factors will be the extreme end). L<Math::Pari>
+while a semiprime may be 3000x faster). L<Math::Pari>
is much slower with native sized inputs, probably due to calling
overhead. For bigints, the L<Math::Prime::Util::GMP> module is needed or
performance will be far worse than Math::Pari. With the GMP module,
@@ -3365,7 +3384,7 @@ warrant distributed processing.
=head2 PRIMALITY PROVING
The C<n-1> proving algorithm in L<Math::Prime::Util::GMP> compares well to
-the version including in Pari. Both are pretty fast to about 60 digits, and
+the version included in Pari. Both are pretty fast to about 60 digits, and
work reasonably well to 80 or so before starting to take many minutes per
number on a fast computer. Version 0.09 and newer of MPU::GMP contain an
ECPP implementation that, while not state of the art compared to closed source
@@ -3465,51 +3484,51 @@ thank Kim Walisch for the many discussions about prime
counting.
=item *
-Henri Cohen, "A Course in Computational Algebraic Number Theory", Springer,
1996. Practical computational number theory from the team lead of
L<Pari|http://pari.math.u-bordeaux.fr/>. Lots of explicit algorithms.
+Christian Bau, "The Extended Meissel-Lehmer Algorithm", 2003, preprint with
example C++ implementation. Very detailed implementation-specific paper which
was used for the implementation here. Highly recommended for implementing a
sieve-based LMO.
L<http://cs.swan.ac.uk/~csoliver/ok-sat-library/OKplatform/ExternalSources/sources/NumberTheory/ChristianBau/>
=item *
-Hans Riesel, "Prime Numbers and Computer Methods for Factorization",
Birkh?user, 2nd edition, 1994. Lots of information, some code, easy to follow.
+Manuel Benito and Juan L. Varona, "Recursive formulas related to the summation
of the Möbius function", I<The Open Mathematics Journal>, v1, pp 25-34, 2007.
Among many other things, shows a simple formula for computing the Mertens
functions with only n/3 Möbius values (not as fast as Deléglise and Rivat, but
really simple).
L<http://www.unirioja.es/cu/jvarona/downloads/Benito-Varona-TOMATJ-Mertens.pdf>
=item *
-Pierre Dusart, "Estimates of Some Functions Over Primes without R.H.",
preprint, 2010. Updates to the best non-RH bounds for prime count and nth
prime. L<http://arxiv.org/abs/1002.0442/>
+John Brillhart, D. H. Lehmer, and J. L. Selfridge, "New Primality Criteria and
Factorizations of 2^m +/- 1", Mathematics of Computation, v29, n130, Apr 1975,
pp 620-647.
L<http://www.ams.org/journals/mcom/1975-29-130/S0025-5718-1975-0384673-1/S0025-5718-1975-0384673-1.pdf>
=item *
-Pierre Dusart, "Autour de la fonction qui compte le nombre de nombres
premiers", PhD thesis, 1998. In French. The mathematics is readable and
highly recommended reading if you're interesting in prime number bounds.
L<http://www.unilim.fr/laco/theses/1998/T1998_01.html>
+W. J. Cody and Henry C. Thacher, Jr., "Rational Chebyshev Approximations for
the Exponential Integral E_1(x)", I<Mathematics of Computation>, v22, pp
641-649, 1968.
=item *
-Gabriel Mincu, "An Asymptotic Expansion", I<Journal of Inequalities in Pure
and Applied Mathematics>, v4, n2, 2003. A very readable account of Cipolla's
1902 nth prime approximation.
L<http://www.emis.de/journals/JIPAM/images/153_02_JIPAM/153_02.pdf>
+W. J. Cody and Henry C. Thacher, Jr., "Chebyshev approximations for the
exponential integral Ei(x)", I<Mathematics of Computation>, v23, pp 289-303,
1969.
L<http://www.ams.org/journals/mcom/1969-23-106/S0025-5718-1969-0242349-2/>
=item *
-Christian Bau, "The Extended Meissel-Lehmer Algorithm", 2003, preprint with
example C++ implementation. Very detailed implementation-specific paper which
was used for the implementation here. Highly recommended for implementing a
sieve-based LMO.
L<http://cs.swan.ac.uk/~csoliver/ok-sat-library/OKplatform/ExternalSources/sources/NumberTheory/ChristianBau/>
+W. J. Cody, K. E. Hillstrom, and Henry C. Thacher Jr., "Chebyshev
Approximations for the Riemann Zeta Function", L<Mathematics of Computation>,
v25, n115, pp 537-547, July 1971.
=item *
-David M. Smith, "Multiple-Precision Exponential Integral and Related
Functions", I<ACM Transactions on Mathematical Software>, v37, n4, 2011.
L<http://myweb.lmu.edu/dmsmith/toms2011.pdf>
+Henri Cohen, "A Course in Computational Algebraic Number Theory", Springer,
1996. Practical computational number theory from the team lead of
L<Pari|http://pari.math.u-bordeaux.fr/>. Lots of explicit algorithms.
=item *
-Vincent Pegoraro and Philipp Slusallek, "On the Evaluation of the
Complex-Valued Exponential Integral", I<Journal of Graphics, GPU, and Game
Tools>, v15, n3, pp 183-198, 2011.
L<http://www.cs.utah.edu/~vpegorar/research/2011_JGT/paper.pdf>
+Marc Deléglise and Joöl Rivat, "Computing the summation of the Möbius
function", I<Experimental Mathematics>, v5, n4, pp 291-295, 1996. Enhances the
Möbius computation in Lioen/van de Lune, and gives a very efficient way to
compute the Mertens function. L<http://projecteuclid.org/euclid.em/1047565447>
=item *
-William H. Press et al., "Numerical Recipes", 3rd edition.
+Pierre Dusart, "Autour de la fonction qui compte le nombre de nombres
premiers", PhD thesis, 1998. In French. The mathematics is readable and
highly recommended reading if you're interesting in prime number bounds.
L<http://www.unilim.fr/laco/theses/1998/T1998_01.html>
=item *
-W. J. Cody and Henry C. Thacher, Jr., "Chebyshev approximations for the
exponential integral Ei(x)", I<Mathematics of Computation>, v23, pp 289-303,
1969.
L<http://www.ams.org/journals/mcom/1969-23-106/S0025-5718-1969-0242349-2/>
+Pierre Dusart, "Estimates of Some Functions Over Primes without R.H.",
preprint, 2010. Updates to the best non-RH bounds for prime count and nth
prime. L<http://arxiv.org/abs/1002.0442/>
=item *
-W. J. Cody and Henry C. Thacher, Jr., "Rational Chebyshev Approximations for
the Exponential Integral E_1(x)", I<Mathematics of Computation>, v22, pp
641-649, 1968.
+Pierre-Alain Fouque and Mehdi Tibouchi, "Close to Uniform Prime Number
Generation With Fewer Random Bits", pre-print, 2011. Describes random prime
distributions, their algorithm for creating random primes using few random
bits, and comparisons to other methods. Definitely worth reading for the
discussions of uniformity. L<http://eprint.iacr.org/2011/481>
=item *
-W. J. Cody, K. E. Hillstrom, and Henry C. Thacher Jr., "Chebyshev
Approximations for the Riemann Zeta Function", L<Mathematics of Computation>,
v25, n115, pp 537-547, July 1971.
+Walter M. Lioen and Jan van de Lune, "Systematic Computations on Mertens'
Conjecture and Dirichlet's Divisor Problem by Vectorized Sieving", in I<From
Universal Morphisms to Megabytes>, Centrum voor Wiskunde en Informatica, pp.
421-432, 1994. Describes a nice way to compute a range of Möbius values.
L<http://walter.lioen.com/papers/LL94.pdf>
=item *
@@ -3517,31 +3536,31 @@ Ueli M. Maurer, "Fast Generation of Prime Numbers and
Secure Public-Key Cryptogr
=item *
-Pierre-Alain Fouque and Mehdi Tibouchi, "Close to Uniform Prime Number
Generation With Fewer Random Bits", pre-print, 2011. Describes random prime
distributions, their algorithm for creating random primes using few random
bits, and comparisons to other methods. Definitely worth reading for the
discussions of uniformity. L<http://eprint.iacr.org/2011/481>
+Gabriel Mincu, "An Asymptotic Expansion", I<Journal of Inequalities in Pure
and Applied Mathematics>, v4, n2, 2003. A very readable account of Cipolla's
1902 nth prime approximation.
L<http://www.emis.de/journals/JIPAM/images/153_02_JIPAM/153_02.pdf>
=item *
-Douglas A. Stoll and Patrick Demichel , "The impact of ζ(s) complex zeros on
π(x) for x E<lt> 10^{10^{13}}", L<Mathematics of Computation>, v80, n276, pp
2381-2394, October 2011.
L<http://www.ams.org/journals/mcom/2011-80-276/S0025-5718-2011-02477-4/home.html>
+L<OEIS: Primorial|http://oeis.org/wiki/Primorial>
=item *
-L<OEIS: Primorial|http://oeis.org/wiki/Primorial>
+Vincent Pegoraro and Philipp Slusallek, "On the Evaluation of the
Complex-Valued Exponential Integral", I<Journal of Graphics, GPU, and Game
Tools>, v15, n3, pp 183-198, 2011.
L<http://www.cs.utah.edu/~vpegorar/research/2011_JGT/paper.pdf>
=item *
-Walter M. Lioen and Jan van de Lune, "Systematic Computations on Mertens'
Conjecture and Dirichlet's Divisor Problem by Vectorized Sieving", in I<From
Universal Morphisms to Megabytes>, Centrum voor Wiskunde en Informatica, pp.
421-432, 1994. Describes a nice way to compute a range of Möbius values.
L<http://walter.lioen.com/papers/LL94.pdf>
+William H. Press et al., "Numerical Recipes", 3rd edition.
=item *
-Marc Deléglise and Joöl Rivat, "Computing the summation of the Möbius
function", I<Experimental Mathematics>, v5, n4, pp 291-295, 1996. Enhances the
Möbius computation in Lioen/van de Lune, and gives a very efficient way to
compute the Mertens function. L<http://projecteuclid.org/euclid.em/1047565447>
+Hans Riesel, "Prime Numbers and Computer Methods for Factorization",
Birkh?user, 2nd edition, 1994. Lots of information, some code, easy to follow.
=item *
-Manuel Benito and Juan L. Varona, "Recursive formulas related to the summation
of the Möbius function", I<The Open Mathematics Journal>, v1, pp 25-34, 2007.
Among many other things, shows a simple formula for computing the Mertens
functions with only n/3 Möbius values (not as fast as Deléglise and Rivat, but
really simple).
L<http://www.unirioja.es/cu/jvarona/downloads/Benito-Varona-TOMATJ-Mertens.pdf>
+David M. Smith, "Multiple-Precision Exponential Integral and Related
Functions", I<ACM Transactions on Mathematical Software>, v37, n4, 2011.
L<http://myweb.lmu.edu/dmsmith/toms2011.pdf>
=item *
-John Brillhart, D. H. Lehmer, and J. L. Selfridge, "New Primality Criteria and
Factorizations of 2^m +/- 1", Mathematics of Computation, v29, n130, Apr 1975,
pp 620-647.
L<http://www.ams.org/journals/mcom/1975-29-130/S0025-5718-1975-0384673-1/S0025-5718-1975-0384673-1.pdf>
+Douglas A. Stoll and Patrick Demichel , "The impact of ζ(s) complex zeros on
π(x) for x E<lt> 10^{10^{13}}", L<Mathematics of Computation>, v80, n276, pp
2381-2394, October 2011.
L<http://www.ams.org/journals/mcom/2011-80-276/S0025-5718-2011-02477-4/home.html>
=back
diff --git a/t/92-release-pod-coverage.t b/t/92-release-pod-coverage.t
index 3d235d8..5554639 100644
--- a/t/92-release-pod-coverage.t
+++ b/t/92-release-pod-coverage.t
@@ -30,6 +30,8 @@ foreach my $m (@modules) {
};
$param->{trustme} = [mpu_public_regex(), mpu_factor_regex()]
if $m eq 'Math::Prime::Util::PP';
+ $param->{trustme} = [qw/miller rabin all_factors/]
+ if $m eq 'Math::Prime::Util';
pod_coverage_ok( $m, $param );
}
--
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
