Revision history for Perl extension Math::Prime::Util.

0.13  19 November 2012

    - Fix an issue with prime count, and make prime count available as a
      standalone program using primesieve.

0.12  17 November 2012

    - Add bin/primes.pl and bin/factor.pl

    - Add functions:
           primorial               product of primes <= n
           pn_primorial            product of first n primes
           prime_set_config        set config options
           RiemannZeta             export and make accurate for small reals
           is_provable_prime       prove primes after BPSW
           is_aks_prime            prove prime via AKS

    - Add 'assume_rh' configuration option (default: false) which can be set
      to allow functions to assume the Riemann Hypothesis.

    - Use the Schoenfeld bound for Pi(x) (x large) if assume_rh is true.

    - valgrind testing

    - Use long doubles for math functions.

    - Some fixes and speedups for ranged primes().

    - In the PP code, use 2 MR bases for more numbers when possible.

    - Fixup of racing SQUFOF, and switch to use it in factor().

    - Complete rewrite of XS p-1 factor routine, includes second stage.

    - bug fix for prime_count on edge of cache.

    - prime_count will use Lehmer prime counting algorithm for largish
      sizes (above 4 million).  This is MUCH faster than sieving.

    - nth_prime now uses the fast Lehmer prime count below the lower limit,
      then sieves up from there.  This makes a big speed difference for inputs
      over 10^6 or so -- over 100x faster for 10^9 and up.

0.11  23 July 2012
    - Turn off threading tests on Cygwin, as threads on some Cygwin platforms
      give random panics (my Win7 64-bit works fine, XP 32-bit does not).
    - Use pow instead of exp2 -- some systems don't have exp2.
    - Fix compile issues on MSC, thanks to Sisyphus.
    - some bigint/bignum changes (next_prime and math functions).
    - speed up and enhance some tests.
    - Test version of racing SQUFOF (not used in main code yet).  Also add
      a little more up-front trial division for main factor routine.


0.10  16 July 2012
    - Add:
           prime_get_config              to get configuration options
           is_strong_pseudoprime         better name for miller_rabin
           is_strong_lucas_pseudoprime   strong lucas-selfridge psp test
           random_nbit_prime             for n-bit primes
           random_maurer_prime           provable n-bit primes
           moebius                       Mo:bius function
           euler_phi                     Euler's phi aka totient

    - full bigint support for everything.  Use '-nobigint' as an import to
      shortcut straight to XS for better speed on some of the very fast functions.
      This involved moving a lot of functions into Util.pm.

    - added BPSW primality test for large (>2^64) is_prob_prime and is_prime.

    - Add tests for pp and bignum, cleanup of many tests.

    - New bounds for prime_count and nth_prime.  Dusart 2010 for larger
      values, tuned nth_prime_upper for small values.  Much tighter.

    - Minor changes:
        - Make miller_rabin return 0 if given even number.
        - The XS miller_rabin code now works with large base > n.
        - factor always returns sorted results 
        - miller_rabin() deprecated.  Use is_strong_pseudoprime instead.

    - We now should support most of the functionality of:
         Math::Prime::XS         (MPU: more functions, a bit faster)
         Math::Prime::FastSieve  (MPU: more functions, a bit faster)
         Math::Prime::TiedArray  (MPU: a *lot* faster)
         Math::Factor::XS        (MPU: bignums, faster, missing multiplicity)
         Math::Big::Factors      (MPU: orders of magnitude faster)
         Math::Primality         (MPU: more portable, fast native, slow bigint)
                                 (MPU+MPU::GMP: faster)
         Crypt::Primes           (MPU: more portable, slower & no fancy options)

      as well as a tiny bit of:
         Math::Big               (MPU's primes is *much* faster)
         Bit::Vector             (MPU's primes is ~10x faster)

0.09  25 June 2012
    - Pure Perl code added.  Passes all tests.  Used only if the XSLoader
      fails.  It's 1-120x slower than the C code.  When forced to use the
      PP code, the test suite is 38x slower on 64-bit, 16x slower on 32-bit
      (in 64-bit, the test suite runs some large numbers through routines
      like prime_count and nth_prime that are much faster in C).
    - Modifications to threading test:
        - some machines were failing because they use non-TS rand.  Fix by
          making our own rand.
        - Win32 was failing because of unique threading issues.  It barfs
          if you free memory on a different thread than allocated it.
    - is_prime could return 1 in some cases.  Fixed to only return 0 or 2.

0.08  22 June 2012
    - Added thread safety and tested good concurrency.
    - Accuracy improvement and measurements for math functions.
    - Remove simple sieve -- it wasn't being used, and was just around for
      performance comparisons.
    - Static presieve for 7, 11, and 13.  1k of ROM used for prefilling sieve
      memory, meaning we can skip the 7, 11, and 13 loops.  ~15% speedup.
    - Add all_factors function and added tests to t/50-factoring.t.
    - Add tied array module Math::Prime::Util::PrimeArray.
    - 5.6.2 64-bit now disables the 64-bit factoring tests instead of failing
      the module.  The main issue is that we can't verify the factors since Perl
      can't properly multiply them.

0.07  17 June 2012
    - Fixed a bug in next_prime found by Lou Godio (thank you VERY much!).
      Added more tests for this.  This had been changed in another area but
      hadn't been brought into next_prime.

0.06  14 June 2012
    - Change to New/Safefree from malloc.  Oops.

0.05  11 June 2012
    - Speed up mulmod: asm for GCC + x86_64, native 64-bit for 32-bit Perl
      is uint64_t is available, and range tests for others.  This speeds up
      some of the factoring as well as Miller-Rabin, which in turn speeds up
      is_prime.  is_prime is used quite commonly, so this is good.
    - nth_prime routines should now all croak on overflow in the same way.
    - Segmented prime_count, things like this are reasonably efficient:
            say prime_count( 10**16,  10**16 + 2**20 )
    - Add Ei(x), li(x), and R(x) functions.
    - prime_count_approx uses R(x), making it vastly more accurate.
    - Let user override rand for random_prime.
    - Add many more tests with the help of Devel::Cover.

0.04  7 June 2012
    - Didn't do tests on 32-bit machine before release.  Test suite caught
      problem with next_prime overflow.
    - Try to use 64-bit modulo math even when Perl is 32-bit.  It can make
      is_prime run up to 10x faster (which impacts next_prime, factoring, etc.)
    - replace all assert with croak indicating an internal error.
    - Add random_prime and random_ndigit_prime
    - renamed prime_free to prime_memfree.

0.03  6 June 2012
    - Speed up factoring.
    - fixed powmod routine, speedup for smaller numbers
    - Add Miller-Rabin and deterministic probable prime functions.  These
      are now used for is_prime and factoring, giving a big speedup for
      numbers > 32-bit.
    - Add HOLF factoring (just for demo)
    - Next prime returns 0 on overflow

0.02  5 June 2012
    - Back off new_ok to new/isa_ok to keep Test::More requirements low.
    - Some documentation updates.
    - I accidently used long in SQUFOF, which breaks LLP64.
    - Test for broken 64-bit Perl.
    - Fix overflow issues in segmented sieving.
    - Switch to using UVuf for croaks.  What I should have done all along.
    - prime_count uses a segment sieve with 256k chunks (~7.9M numbers).
      Not memory intensive any more, and faster for large inputs.  The time
      growth is slightly over linear however, so expect to wait a long
      time for 10^12 or more.
    - nth_prime also transitioned to segmented sieve.

0.01  4 June 2012
    - Initial release