This is an automated email from the git hooks/post-receive script.

ppm-guest pushed a commit to annotated tag v0.26
in repository libmath-prime-util-perl.

commit 0eef4fe37f9a8431b5ccb06b4f63f3dd870caad7
Author: Dana Jacobsen <d...@acm.org>
Date:   Wed Mar 20 18:49:43 2013 -0700

    Documentation updates
---
 lib/Math/Prime/Util.pm | 165 +++++++++++++++++++++++++++++--------------------
 1 file changed, 97 insertions(+), 68 deletions(-)

diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm
index 248e61f..702c42a 100644
--- a/lib/Math/Prime/Util.pm
+++ b/lib/Math/Prime/Util.pm
@@ -2136,10 +2136,15 @@ Two scripts are also included and installed by default:
 
 =over 4
 
-=item primes.pl displays primes between start and end values, with many
-options for filtering (e.g. twin, safe, circular, good, lucky, etc.).
+=item *
+
+primes.pl displays primes between start and end values or expressions,
+with many options for filtering (e.g. twin, safe, circular, good, lucky,
+etc.).  Use C<--help> to see all the options.
+
+=item *
 
-=item factor.pl operates similar to the GNU C<factor> program.  It supports
+factor.pl operates similar to the GNU C<factor> program.  It supports
 bigint and expression inputs.
 
 =back
@@ -2229,13 +2234,13 @@ it will return 0 for composite and 1 for probably 
prime, using a strong BPSW
 test.  If L<Math::Prime::Util::GMP> is installed, some quick primality proofs
 are run on larger numbers, so will return 2 for many of those also.
 
-Also see the L</"is_prob_prime"> function, which will never do additional
-tests, and the L</"is_provable_prime"> function which will try very hard to
+Also see the L</is_prob_prime> function, which will never do additional
+tests, and the L</is_provable_prime> function which will try very hard to
 return only 0 or 2 for any input.
 
 For native precision numbers (anything smaller than C<2^64>, all three
 functions are identical and use a deterministic set of Miller-Rabin tests.
-While L</"is_prob_prime"> and L</"is_prime"> return probable prime results
+While L</is_prob_prime> and L</is_prime> return probable prime results
 for larger numbers, they use the strong Baillie-PSW test, which has had
 no counterexample found since it was published in 1980 (though certainly they
 exist).
@@ -2308,9 +2313,9 @@ under 1 minute, C<Pi(10^15)> in under 5 minutes, and 
C<Pi(10^16)> in under
 In contrast, even primesieve using 12 cores would take over a week on this
 same computer to determine C<Pi(10^16)>.
 
-Also see the function L</"prime_count_approx"> which gives a very good
-approximation to the prime count, and L</"prime_count_lower"> and
-L</"prime_count_upper"> which give tight bounds to the actual prime count.
+Also see the function L</prime_count_approx> which gives a very good
+approximation to the prime count, and L</prime_count_lower> and
+L</prime_count_upper> which give tight bounds to the actual prime count.
 These functions return quickly for any input, including bigints.
 
 
@@ -2532,8 +2537,8 @@ which is a segmented version of Lioen and van de Lune 
(1994) algorithm 3.2.
   say "Mertens(10M) = ", mertens(10_000_000);   # = 1037
 
 Returns M(n), the Mertens function for a non-negative integer input.  This
-function is defined as C<sum(moebius(1..n))>.  This is a much more efficient
-solution for larger inputs.  For example, computing Mertens(100M) takes:
+function is defined as C<sum(moebius(1..n))>, but calculated more efficiently
+for large inputs.  For example, computing Mertens(100M) takes:
 
    time    approx mem
      0.4s      0.1MB   mertens(100_000_000)
@@ -2548,14 +2553,14 @@ The current method is a simple C<n^1/2> version of 
Deléglise and Rivat (1996),
 which involves calculating all moebius values to C<n^1/2>, which in turn will
 require prime sieving to C<n^1/4>.
 
-Various methods exist for this, using differing quantities of μ(n).  The
+Various algorithms exist for this, using differing quantities of μ(n).  The
 simplest way is to efficiently sum all C<n> values.  Benito and Varona (2008)
 show a clever and simple method that only requires C<n/3> values.  Deléglise
 and Rivat (1996) describe a segmented method using only C<n^1/3> values.  The
-current implementation does a simple non-segmented C<n^1/2> version of this.
-Kuznetsov (2011) gives an alternate method that he indicates is even faster.
-Lastly, one of the advanced prime count algorithms could be theoretically used
-to create a faster solution.
+current implementation does a simple non-segmented C<n^1/2> version of their
+method.  Kuznetsov (2011) gives an alternate method that he indicates is even
+faster.  Lastly, one of the advanced prime count algorithms could be
+theoretically used to create a faster solution.
 
 
 =head2 euler_phi
@@ -2591,11 +2596,13 @@ the Dedikind psi function, where C<psi(n) = J(2,n) / 
J(1,n)>.
 
   say "exp(lambda($_)) = ", exp_mangoldt($_) for 1 .. 100;
 
-Returns Λ(n), the Mangoldt function (also known as von Mangoldt's function) for
-an integer value.  It is equal to log p if n is prime or a power of a prime,
+Returns exp(Λ(n)), the exponential of the Mangoldt function (also known
+as von Mangoldt's function) for an integer value.
+It is equal to log p if n is prime or a power of a prime,
 and 0 otherwise.  We return the exponential so all results are integers.
- Hence the return value for C<exp_mangoldt> is:
-   C<p>   if C<n = p^m> for some prime C<p> and integer C<m E<gt>= 1>
+Hence the return value for C<exp_mangoldt> is:
+
+   p   if n = p^m for some prime p and integer m >= 1
    1   otherwise.
 
 
@@ -2605,11 +2612,12 @@ and 0 otherwise.  We return the exponential so all 
results are integers.
 
 Returns θ(n), the first Chebyshev function for a non-negative integer input.
 This is the sum of the logarithm of each prime where C<p E<lt>= n>.  An
-alternate computation is as the logarithm of n primorial, hence:
+alternate computation is as the logarithm of n primorial.
+Hence these functions:
+
+  use List::Util qw/sum/;  use Math::BigFloat;
 
-  use List::Util qw/sum/;
   sub c1a { 0+sum( map { log($_) } @{primes(shift)} ) }
-  use Math::BigFloat;
   sub c1b { Math::BigFloat->new(primorial(shift))->blog }
 
 yield similar results, albeit slower and using more memory.
@@ -2625,9 +2633,9 @@ integer k.  An alternate computation is as the summatory 
Mangoldt function.
 Another alternate computation is as the logarithm of lcm(1,2,...,n).
 Hence these functions:
 
-  use List::Util qw/sum/;
+  use List::Util qw/sum/;  use Math::BigFloat;
+
   sub c2a { 0+sum( map { log(exp_mangoldt($_)) } 1 .. shift ) }
-  use Math::BigFloat;
   sub c2b { Math::BigFloat->new(consecutive_integer_lcm(shift))->blog }
 
 yield similar results, albeit slower and using more memory.
@@ -2659,7 +2667,7 @@ the 5th Jordan totient (OEIS A059378):
 
   divisor_sum( $n, sub { my $d=shift; $d**5 * moebius($n/$d); } );
 
-though in the last case we have a function L</"jordan_totient"> to compute
+though in the last case we have a function L</jordan_totient> to compute
 it more efficiently.
 
 This function is useful for calculating things like aliquot sums, abundant
@@ -2743,7 +2751,7 @@ then select a random prime from the partition.  This 
gives some loss of
 uniformity but results in many fewer bits of randomness being consumed as
 well as being much faster.
 
-If an C<irand> function has been set via L</"prime_set_config">, it will be
+If an C<irand> function has been set via L</prime_set_config>, it will be
 used to construct any ranged random numbers needed.  The function should
 return a uniformly random 32-bit integer, which is how the irand functions
 exported by L<Math::Random::Secure>, L<Math::Random::MT>,
@@ -2844,7 +2852,7 @@ either method so make the point moot.  Third, due to key 
size growth and
 advances in factoring and attacks, for practical purposes, using large random
 primes offer security equivalent to using strong primes.
 
-Similar to L</"random_nbit_prime">, the result will be a BigInt if the
+Similar to L</random_nbit_prime>, the result will be a BigInt if the
 number of bits is greater than the native bit size.  For better performance
 with large bit sizes, install L<Math::Prime::Util::GMP>.
 
@@ -2854,7 +2862,7 @@ with large bit sizes, install L<Math::Prime::Util::GMP>.
 
 Construct an n-bit provable prime, using the FastPrime algorithm of
 Ueli Maurer (1995).  This is the same algorithm used by L<Crypt::Primes>.
-Similar to L</"random_nbit_prime">, the result will be a BigInt if the
+Similar to L</random_nbit_prime>, the result will be a BigInt if the
 number of bits is greater than the native bit size.  For better performance
 with large bit sizes, install L<Math::Prime::Util::GMP>.
 
@@ -2958,7 +2966,8 @@ 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.
+to require more than the first Rho + SQUFOF to find a factor, and I have not
+seen anything go to the last step.
 
 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
@@ -3309,22 +3318,22 @@ you don't want to use MPU:
 
 =over 4
 
-=item L<Math::Prime::FastSieve>
-This is the alternative module I use for basic functionality with small
-integers.  It's fast and simple, and has a good set of features.
+=item * L<Math::Prime::FastSieve> is the alternative module I use for basic
+functionality with small integers.  It's fast and simple, and has a good
+set of features.
 
-=item L<Math::Primality>
-This is the alternative module I use for primality testing on bigints.
+=item * L<Math::Primality> is the alternative module I use for primality
+testing on bigints.
 
-=item L<Math::Pari>
-If you want the kitchen sink and can install it and handle using it.  There
-are still some functions it doesn't do well (e.g. prime count and nth_prime).
+=item * L<Math::Pari> if you want the kitchen sink and can install it and
+handle using it.  There are still some functions it doesn't do well
+(e.g. prime count and nth_prime).
 
 =back
 
 
 L<Math::Prime::XS> has C<is_prime> and C<primes> functionality.  There is no
-bigint support.  The C<is_prime> function is a well-written trial division,
+bigint support.  The C<is_prime> function uses well-written trial division,
 meaning it is very fast for small numbers, but terribly slow for large
 64-bit numbers.  The prime sieve is an unoptimized non-segmented SoE which
 which returns an array.  It works well for 32-bit values, but speed and
@@ -3359,7 +3368,7 @@ for security.
 What Crypt::Primes has that MPU does not is support for returning a generator.
 
 L<Math::Factor::XS> calculates prime factors and factors, which correspond to
-the L</"factor"> and L<"all_factors"> functions of MPU.  These functions do
+the L</factor> and L</all_factors> 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).  It has additional
@@ -3376,7 +3385,7 @@ L<Math::Big::Factors> supports factorization using wheel 
factorization (smart
 trial division).  It supports bigints.  Unfortunately it is extremely slow on
 any input that isn't comprised entirely of small factors.  Even 7 digit inputs
 can take hundreds or thousands of times longer to factor than MPU or
-L<Math::Factor::XS>.  19-digit semiprimes will take hours vs. MPU's single
+L<Math::Factor::XS>.  19-digit semiprimes will take I<hours> vs. MPU's single
 milliseconds.
 
 L<Math::Factoring> is a placeholder module for bigint factoring.  Version 0.02
@@ -3400,7 +3409,7 @@ bigints.  In fact, Math::Primality was made originally 
with bigints in mind,
 while MPU was originally targeted to native integers, but both have added
 better support for the other.  The main differences are extra functionality
 (MPU has more functions) and performance.  With native integer inputs, MPU
-is generally much faster, especially with L</"prime_count">.  For bigints,
+is generally much faster, especially with L</prime_count>.  For bigints,
 MPU is slower unless the L<Math::Prime::Util::GMP> module is installed, in
 which case they have somewhat similar speeds.  L<Math::Primality> also installs
 a C<primes.pl> program, but it has much less functionality than the one
@@ -3412,7 +3421,7 @@ primes, twin primes, Sophie-Germain primes, lucky primes, 
moebius, divisor
 count, factor count, Euler totient, primorials, etc.  Math::NumSeq is mainly
 set up for accessing these values in order, rather than for arbitrary values,
 though some sequences support that.  The primary advantage I see is the
-uniform access mechanism for a <I>lot</I> of sequences.  For those methods that
+uniform access mechanism for a I<lot> of sequences.  For those methods that
 overlap, MPU is usually much faster.  Importantly, most all the sequences in
 Math::NumSeq are limited to 32-bit indices.
 
@@ -3424,7 +3433,9 @@ will eventually win out).  Trying to hit some of the 
highlights:
 
 =over 4
 
-=item isprime Similar to MPU's L<is_prob_prime> or L<is_prime> functions.
+=item isprime
+
+Similar to MPU's L<is_prob_prime> or L<is_prime> functions.
 MPU is deterministic for native integers, and uses a strong
 BPSW test for bigints (with a quick primality proof tried as well).  The
 default version of Pari used by L<Math::Pari> (2.1.7) uses 10 random M-R
@@ -3434,37 +3445,53 @@ newer 2.3.5 library makes C<isprime> use an APRCL 
primality proof, which
 can take longer (though will be much faster than the BLS75 proof used in
 MPU's L<is_provable_prime> routine).
 
-=item primepi Similar to MPU's L<prime_count> function.  Pari uses a naive
+=item primepi
+
+Similar to MPU's L<prime_count> function.  Pari uses a naive
 counting algorithm with its precalculated primes, so this is not very useful.
 
-=item primes Doesn't support ranges, requires bumping up the precalculated
+=item primes
+
+Doesn't support ranges, requires bumping up the precalculated
 primes for larger numbers, which means knowing in advance the upper limit
 for primes.  Support for numbers larger than 400M requires making with Pari
 version 2.3.5.  If that is used, sieving is about 2x faster than MPU, but
 doesn't support segmenting.
 
-=item factorint Similar to MPU's L<factor> though with a different return (I
+=item factorint
+
+Similar to MPU's L<factor> though with a different return (I
 find the result value quite inconvenient to work with, but others may like
 its vector of factor/exponent format).  Slower than MPU for all 64-bit inputs
 on an x86_64 platform, it may be faster for large values on other platforms.
 Bigints are slightly faster with Math::Pari for "small" values, and MPU slows
 down rapidly (the difference is noticeable with 30+ digit numbers).
 
-=item eulerphi Similar to MPU's L<euler_phi>.  MPU is 2-5x faster for native
+=item eulerphi
+
+Similar to MPU's L<euler_phi>.  MPU is 2-5x faster for native
 integers.  There is also support for a range, which can be much 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 moebius Similar to MPU's L<moebius>.  Comparisons are similar to
-C<eulerphi>.
+=item moebius
+
+Similar to MPU's L<moebius>.  Comparisons are similar to C<eulerphi>.
+
+=item sumdiv
 
-=item sumdiv Similar to MPU's L<divisor_sum>.  The standard sum (sigma_1) is
+Similar to MPU's L<divisor_sum>.  The standard sum (sigma_1) is
 very fast in MPU.  Giving it a sub makes it much slower, and for numbers
-with very many factors, Pari is <I>much</I> faster.
+with very many factors, Pari is I<much> faster.
+
+=item eint1
+
+Similar to MPU's L<ExponentialIntegral>.
 
-=item eint1 Similar to MPU's L<ExponentialIntegral>.
+=item zeta
 
-=item zeta A more substantial version of MPU's L<RiemannZeta> function.
+A more feature-rich version MPU's L<RiemannZeta> function (supports negative
+and complex inputs).
 
 =back
 
@@ -3616,8 +3643,7 @@ faster with Math::Prime::Util.  For 30+ digit numbers, 
L<Math::Pari> is much
 faster.  Without the L<Math::Prime::Util::GMP> module, almost all actions on
 numbers greater than native scalars will be much faster in Pari.
 
-The presentation here:
- L<http://math.boisestate.edu/~liljanab/BOISECRYPTFall09/Jacobsen.pdf>
+L<This slide 
presentation|http://math.boisestate.edu/~liljanab/BOISECRYPTFall09/Jacobsen.pdf>
 has a lot of data on 64-bit and GMP factoring performance I collected in 2009.
 Assuming you do not know anything about the inputs, trial division and
 optimized Fermat or Lehman work very well for small numbers (<= 10 digits),
@@ -3630,15 +3656,18 @@ L<yafu|http://sourceforge.net/projects/yafu/>,
 L<msieve|http://sourceforge.net/projects/msieve/>,
 L<gmp-ecm|http://ecm.gforge.inria.fr/>,
 L<GGNFS|http://sourceforge.net/projects/ggnfs/>,
-and L<Pari|http://pari.math.u-bordeaux.fr/>.
+and L<Pari|http://pari.math.u-bordeaux.fr/>.  The latest yafu should cover most
+uses, with GGNFS likely only providing a benefit for numbers large enough to
+warrant distributed processing.
 
 
 The primality proving algorithms leave much to be desired.  If you have
-numbers larger than C<2^128>, I recommend Pari's C<isprime(n, 2)> which
-will run a fast APRCL test, or
-L<GMP-ECPP|http://http://sourceforge.net/projects/gmp-ecpp/>.  Either one
+numbers larger than C<2^128>, I recommend C<isprime(n, 2)> from Pari 2.3+
+which will run a fast APRCL test,
+L<GMP-ECPP|http://http://sourceforge.net/projects/gmp-ecpp/>, or
+L<Primo|http://www.ellipsa.eu/>.  Any of those
 will be much faster than the Lucas or BLS algorithms used in MPU for large
-inputs.
+inputs.  For very large numbers, Primo is the one to use.
 
 
 =head1 AUTHORS
@@ -3649,7 +3678,7 @@ Dana Jacobsen E<lt>d...@acm.orge<gt>
 =head1 ACKNOWLEDGEMENTS
 
 Eratosthenes of Cyrene provided the elegant and simple algorithm for finding
-the primes.
+primes.
 
 Terje Mathisen, A.R. Quesada, and B. Van Pelt all had useful ideas which I
 used in my wheel sieve.
@@ -3671,7 +3700,7 @@ Silverman's code.
 
 =item *
 
-Pierre Dusart, "Estimates of Some Functions Over Primes without R.H.", 
preprint, 2010.  L<http://arxiv.org/abs/1002.0442/>
+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 *
 
@@ -3679,7 +3708,7 @@ Pierre Dusart, "Autour de la fonction qui compte le 
nombre de nombres premiers",
 
 =item *
 
-Gabriel Mincu, "An Asymptotic Expansion", <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>
+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 *
 
@@ -3707,11 +3736,11 @@ W. J. Cody, K. E. Hillstrom, and Henry C. Thacher Jr., 
"Chebyshev Approximations
 
 =item *
 
-Ueli M. Maurer, "Fast Generation of Prime Numbers and Secure Public-Key 
Cryptographic Parameters", 1995.  
L<http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.26.2151>
+Ueli M. Maurer, "Fast Generation of Prime Numbers and Secure Public-Key 
Cryptographic Parameters", 1995.  Generating random provable primes by building 
up the prime.  
L<http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.26.2151>
 
 =item *
 
-Pierre-Alain Fouque and Mehdi Tibouchi, "Close to Uniform Prime Number 
Generation With Fewer Random Bits", pre-print, 2011.  
L<http://eprint.iacr.org/2011/481>
+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 *
 
@@ -3719,7 +3748,7 @@ Douglas A. Stoll and Patrick Demichel , "The impact of 
ζ(s) complex zeros on π
 
 =item *
 
-L<OEIS: Primorial|http://oeis.org/wiki/Primorial>.
+L<OEIS: Primorial|http://oeis.org/wiki/Primorial>
 
 =item *
 
@@ -3731,7 +3760,7 @@ Marc Deléglise and Joöl Rivat, "Computing the summation 
of the Möbius functio
 
 =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.  
Presents a nice algorithm to compute the Mertens functions with only n/3 Möbius 
values.  
L<http://www.unirioja.es/cu/jvarona/downloads/Benito-Varona-TOMATJ-Mertens.pdf>
+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>
 
 =back
 

-- 
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

Reply via email to