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

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

commit 0fcc6dc66c51c336f2271ed71b53f7f52af44156
Author: Dana Jacobsen <d...@acm.org>
Date:   Mon Jul 16 23:03:23 2012 -0600

    Big documentation update for PP
---
 TODO                      |   3 +
 lib/Math/Prime/Util.pm    |  14 +--
 lib/Math/Prime/Util/PP.pm | 222 ++++++++--------------------------------------
 3 files changed, 49 insertions(+), 190 deletions(-)

diff --git a/TODO b/TODO
index 7ac403a..9e91c36 100644
--- a/TODO
+++ b/TODO
@@ -23,3 +23,6 @@
   version does it in a painful way.  Something simpler to be had?
 
 - finish test suite for bignum.  Work on making it faster.
+
+- After the factoring changes, we need to use Devel::Cover again to ferret
+  out numbers that pass the early tests.
diff --git a/lib/Math/Prime/Util.pm b/lib/Math/Prime/Util.pm
index 6007c34..25315dc 100644
--- a/lib/Math/Prime/Util.pm
+++ b/lib/Math/Prime/Util.pm
@@ -1343,10 +1343,12 @@ your program.
 =head1 BIGNUM SUPPORT
 
 By default all functions support bigints.  The module will not turn on bigint
-support for you -- you will need to use bigint or pass in a L<Math::BigInt>
-object as your input.  Some care is taken to keep all bignum operations using
-the same class as was passed in, allowing the module to work properly with
-Calc, FastCalc, GMP, Pari, etc.
+support for you -- you will need to C<use bigint>, C<use bignum>, or pass in
+a L<Math::BigInt> 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.
 
 
 Some of the functions, notably:
@@ -1939,7 +1941,9 @@ Given a positive non-zero floating point input, returns 
the floating
 point value of Riemann's R function.  Riemann's R function gives a very close
 approximation to the prime counting function.
 
-Accuracy should be at least 14 digits.  The current implementation isn't 
corrently storing constants as big floats, so is not giving increased accuracy 
like it should.
+Accuracy should be at least 14 digits.  The current implementation isn't
+correctly storing constants as big floats, so is not giving increased accuracy
+with big numbers like it should.
 
 
 =head1 EXAMPLES
diff --git a/lib/Math/Prime/Util/PP.pm b/lib/Math/Prime/Util/PP.pm
index ce6116b..0e83977 100644
--- a/lib/Math/Prime/Util/PP.pm
+++ b/lib/Math/Prime/Util/PP.pm
@@ -1412,10 +1412,11 @@ module is just the Pure Perl implementation.
 
 =head1 DESCRIPTION
 
-A set of utilities related to prime numbers.  These include multiple sieving
-methods, is_prime, prime_count, nth_prime, approximations and bounds for
-the prime_count and nth prime, next_prime and prev_prime, factoring utilities,
-and more.
+Pure Perl implementations of prime number utilities that are normally
+handled with XS or GMP.  Having the Perl implementations (1) provides examples,
+(2) allows the functions to run even if XS isn't available, and (3) gives
+big number support if L<Math::Prime::Util::GMP> isn't available.  This is a
+subset of L<Math::Prime::Util>'s functionality.
 
 All routines should work with native integers or multi-precision numbers.  To
 enable big numbers, use bigint or bignum:
@@ -1424,9 +1425,9 @@ enable big numbers, use bigint or bignum:
     say prime_count_approx(1000000000000000000000000)'
     # says 18435599767347543283712
 
-This is still experimental, and some functions will be very slow.  I recommend
-looking into L<Math::Pari> if you need serious bignum support for this type
-of functionality right now.
+This is still experimental, and some functions will be very slow.  The
+L<Math::Prime::Util::GMP> module has much faster versions of many of these
+functions.  Alternately, L<Math::Pari> has a lot of these types of functions.
 
 
 =head1 FUNCTIONS
@@ -1435,8 +1436,9 @@ of functionality right now.
 
   print "$n is prime" if is_prime($n);
 
-Returns 2 if the number is prime, 0 if not.  Also note there are
-probabilistic prime testing functions available.
+Returns 2 if the number is prime, 0 if not.  For numbers larger than C<2^64>
+it will return 0 for composite and 1 for probably prime, using a strong BPSW
+test.  Also note there are probabilistic prime testing functions available.
 
 
 =head2 primes
@@ -1464,9 +1466,9 @@ using wheel factorization, or a segmented sieve.
 
   $n = next_prime($n);
 
-Returns the next prime greater than the input number.  0 is returned if the
-next prime is larger than a native integer type (the last representable
-primes being C<4,294,967,291> in 32-bit Perl and
+Returns the next prime greater than the input number.  If the input is not a
+bigint, then 0 is returned if the next prime is larger than a native integer
+type (the last representable primes being C<4,294,967,291> in 32-bit Perl and
 C<18,446,744,073,709,551,557> in 64-bit).
 
 
@@ -1489,47 +1491,6 @@ count of primes between the ranges (e.g. C<(13,17)> 
returns 2, C<14,17>
 and C<13,16> return 1, and C<14,16> returns 0).
 
 
-=head2 prime_count_upper
-
-=head2 prime_count_lower
-
-  my $lower_limit = prime_count_lower($n);
-  die unless prime_count($n) >= $lower_limit;
-
-  my $upper_limit = prime_count_upper($n);
-  die unless prime_count($n) <= $upper_limit;
-
-Returns an upper or lower bound on the number of primes below the input number.
-These are analytical routines, so will take a fixed amount of time and no
-memory.  The actual C<prime_count> will always be on or between these numbers.
-
-A common place these would be used is sizing an array to hold the first C<$n>
-primes.  It may be desirable to use a bit more memory than is necessary, to
-avoid calling C<prime_count>.
-
-These routines use hand-verified tight limits below a range at least C<2^35>,
-and fall back to the Dusart bounds of
-
-    x/logx * (1 + 1/logx + 1.80/log^2x) <= Pi(x)
-
-    x/logx * (1 + 1/logx + 2.51/log^2x) >= Pi(x)
-
-above that range.
-
-
-=head2 prime_count_approx
-
-  print "there are about ",
-        prime_count_approx( 10 ** 18 ),
-        " primes below one quintillion.\n";
-
-Returns an approximation to the C<prime_count> function, without having to
-generate any primes.  The current implementation uses the Riemann R function
-which is quite accurate: an error of less than C<0.0005%> is typical for
-input values over C<2^32>.  A slightly faster (0.1ms vs. 1ms), but much less
-accurate, answer can be obtained by averaging the upper and lower bounds.
-
-
 =head2 nth_prime
 
   say "The ten thousandth prime is ", nth_prime(10_000);
@@ -1541,39 +1502,15 @@ This relies on generating primes, so can require a lot 
of time and space for
 large inputs.
 
 
-=head2 nth_prime_upper
-
-=head2 nth_prime_lower
-
-  my $lower_limit = nth_prime_lower($n);
-  die unless nth_prime($n) >= $lower_limit;
-
-  my $upper_limit = nth_prime_upper($n);
-  die unless nth_prime($n) <= $upper_limit;
-
-Returns an analytical upper or lower bound on the Nth prime.  This will be
-very fast.  The lower limit uses the Dusart 1999 bounds for all C<n>, while
-the upper bound uses one of the two Dusart 1999 bounds for C<n E<gt>= 27076>,
-the Robin 1983 bound for C<n E<gt>= 7022>, and the simple bound of
-C<n * (logn + loglogn)> for C<n E<lt> 7022>.
-
-
-=head2 nth_prime_approx
-
-  say "The one trillionth prime is ~ ", nth_prime_approx(10**12);
-
-Returns an approximation to the C<nth_prime> function, without having to
-generate any primes.  Uses the Cipolla 1902 approximation with two
-polynomials, plus a correction term for small values to reduce the error.
-
+=head2 is_strong_pseudoprime
 
 =head2 miller_rabin
 
-  my $maybe_prime = miller_rabin($n, 2);
-  my $probably_prime = miller_rabin($n, 2, 3, 5, 7, 11, 13, 17);
+  my $maybe_prime = is_strong_pseudoprime($n, 2);
+  my $probably_prime = is_strong_pseudoprime($n, 2, 3, 5, 7, 11, 13, 17);
 
 Takes a positive number as input and one or more bases.  The bases must be
-between C<2> and C<n - 2>.  Returns 2 is C<n> is definitely prime, 1 if C<n>
+greater than 1.  Returns 2 is C<n> is definitely prime, 1 if C<n>
 is probably prime, and 0 if C<n> is definitely composite.  Since this is
 just the Miller-Rabin test, a value of 2 is only returned for inputs of
 2 and 3, which are shortcut.  If 0 is returned, then the number really is a
@@ -1585,66 +1522,13 @@ tests (e.g. the strong BPSW test) or deterministic 
results for numbers less
 than some verified limit (such as the C<is_prob_prime> function in this 
module).
 
 
-=head2 is_prob_prime
-
-  my $prob_prime = is_prob_prime($n);
-  # Returns 0 (composite), 2 (prime), or 1 (probably prime)
-
-Takes a positive number as input and returns back either 0 (composite),
-2 (definitely prime), or 1 (probably prime).
-
-This is done with a tuned set of Miller-Rabin tests such that the result
-will be deterministic for 64-bit input.  Either 2, 3, 4, 5, or 7 Miller-Rabin
-tests are performed (no more than 3 for 32-bit input), and the result will
-then always be 0 (composite) or 2 (prime).  A later implementation may switch
-to a BPSW test, depending on speed.
-
-
-=head2 random_prime
-
-  my $small_prime = random_prime(1000);      # random prime <= limit
-  my $rand_prime = random_prime(100, 10000); # random prime within a range
-
-Returns a psuedo-randomly selected prime that will be greater than or equal
-to the lower limit and less than or equal to the upper limit.  If no lower
-limit is given, 2 is implied.  Returns undef if no primes exist within the
-range.  The L<rand> function is called one or more times for selection.
-
-This will return a uniform distribution of the primes in the range, meaning
-for each prime in the range, the chances are equally likely that it will be
-seen.
-
-The current algorithm does a random index selection for small numbers, which
-is deterministic.  For larger numbers, this can be very slow, so the
-obvious Monte Carlo method is used, where random numbers in the range are
-selected until one is prime.  That also gets slow as the number of digits
-increases, but not something that impacts us in 64-bit.
-
-If you want cryptographically secure primes, I suggest looking at
-L<Crypt::Primes> or something similar.  The current L<Math::Prime::Util>
-module does not use strong randomness, and its primes are ridiculously small
-by cryptographic standards.
-
-Perl's L<rand> function is normally called, but if the sub C<main::rand>
-exists, it will be used instead.  When called with no arguments it should
-return a float value between 0 and 1-epsilon, with 32 bits of randomness.
-Examples:
-
-  # Use Mersenne Twister
-  use Math::Random::MT::Auto qw/rand/;
-
-  # Use my custom random function
-  sub rand { ... }
-
-=head2 random_ndigit_prime
-
-  say "My 4-digit prime number is: ", random_ndigit_prime(4);
-
-Selects a random n-digit prime, where the input is an integer number of
-digits between 1 and the maximum native type (10 for 32-bit, 20 for 64-bit).
-One of the primes within that range (e.g. 1000 - 9999 for 4-digits) will be
-uniformly selected using the L<rand> function.
+=head2 is_strong_lucas_pseudoprime
 
+Takes a positive number as input, and returns 1 if the input is a strong
+Lucas pseudoprime using the Selfridge method of choosing D, P, and Q (some
+sources call this a strong Lucas-Selfridge pseudoprime).  This is one half
+of the BPSW primality test (the Miller-Rabin strong pseudoprime test with
+base 2 being the other half).
 
 
 =head1 UTILITY FUNCTIONS
@@ -1669,18 +1553,6 @@ C<prime_precalc>, it is not necessary to call this, but 
if you're done
 making calls, or want things cleanup up, you can use this.  The object method
 might be a better choice for complicated uses.
 
-=head2 Math::Prime::Util::MemFree->new
-
-  my $mf = Math::Prime::Util::MemFree->new;
-  # perform operations.  When $mf goes out of scope, memory will be recovered.
-
-This is a more robust way of making sure any cached memory is freed, as it
-will be handled by the last C<MemFree> object leaving scope.  This means if
-your routines were inside an eval that died, things will still get cleaned up.
-If you call another function that uses a MemFree object, the cache will stay
-in place because you still have an object.
-
-
 
 =head1 FACTORING FUNCTIONS
 
@@ -1689,26 +1561,11 @@ in place because you still have an object.
   my @factors = factor(3_369_738_766_071_892_021);
   # returns (204518747,16476429743)
 
-Produces the prime factors of a positive number input.  They may not be in
-numerical order.  The special cases of C<n = 0> and C<n = 1> will
-return C<n>, which guarantees multiplying the factors together will
-always result in the input value, though those are the only cases where
-the returned factors are not prime.
-
-The current algorithm is to use trial division for small numbers, while large
-numbers go through a sequence of small trials, SQUFOF, Pollard's Rho, Hart's
-one line factorization, and finally trial division for any survivors.  This
-process is repeated for each non-prime factor.
-
-
-=head2 all_factors
-
-  my @divisors = all_factors(30);   # returns (2, 3, 5, 6, 10, 15)
-
-Produces all the divisors of a positive number input.  1 and the input number
-are excluded (which implies that an empty list is returned for any prime
-number input).  The divisors are a power set of multiplications of the prime
-factors, returned as a uniqued sorted list.
+Produces the prime factors of a positive number input, in numerical order.
+The special cases of C<n = 0> and C<n = 1> will return C<n>, which
+guarantees multiplying the factors together will always result in the
+input value, though those are the only cases where the returned factors
+are not prime.
 
 
 =head2 trial_factor
@@ -1724,11 +1581,7 @@ For large inputs this will be very slow.
 
   my @factors = fermat_factor($n);
 
-Produces factors, not necessarily prime, of the positive number input.  The
-particular algorithm is Knuth's algorithm C.  For small inputs this will be
-very fast, but it slows down quite rapidly as the number of digits increases.
-It is very fast for inputs with a factor close to the midpoint
-(e.g. a semiprime p*q where p and q are the same number of digits).
+Currently unimplementated in Perl.
 
 =head2 holf_factor
 
@@ -1746,10 +1599,7 @@ same advantages and disadvantages as Fermat's method.
 
   my @factors = squfof_factor($n);
 
-Produces factors, not necessarily prime, of the positive number input.  An
-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 function typically runs very fast.
+Currently unimplementated in Perl.
 
 =head2 prho_factor
 
@@ -1853,10 +1703,10 @@ Performance improvement in this code is still possible. 
 The prime sieve is
 over 2x faster than anything I was able to find online, but it is still has
 room for improvement.
 
-Fundamentally some of these operations will be much faster in C than Perl.  I
-expect any of the CPAN XS modules supporting related features to be faster,
-however if those modules are available, then the XS code in
-L<Math::Prime::Util> should be.
+L<Math::Prime::Util::GMP> offers C<C+XS+GMP> support for most of the important
+functions, and will be vastly faster for most operations.  If you install that
+module, L<Math::Prime::Util> will load it automatically, meaning you should
+not have to think about what code is actually being used (C, GMP, or Perl).
 
 Memory use will generally be higher for the PP code, and in some cases B<much>
 higher.  Some of this may be addressed in a later release.
@@ -1869,6 +1719,8 @@ not matter.
 
 L<Math::Prime::Util>
 
+L<Math::Prime::Util::GMP>
+
 
 =head1 AUTHORS
 

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