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

0.22 26 February 2012

    - Move main factor loop out of xs and into factor.c.

    - Totient and Moebius now have complete XS implementations.

    - Ranged totient uses less memory when segmented.

    - Switch thread locking to pthreads condition variables.

0.21 22 February 2012

    - Switch to using Bytes::Random::Secure for random primes.  This is a
      big change in that it is the first non-CORE module used.  However, it
      gets rid of lots of possible stupidness from system rand.

    - Spelling fixes in documentation.

    - primes.pl: Add circular and Panaitopol primes.

    - euler_phi and moebius now will compute over a range.

    - Add mertens function: 1000+ times faster than summing moebius($_).

    - Add exp_mangoldt function: exponential of von Mangoldt's function.

    - divisor_sum defaults to sigma if no sub is given (i.e. it sums).

    - Performance:
       - Speedup factoring small numbers.  With -nobigint factoring from
         1 to 10M, it's 1.2x faster.  1.5x faster than Math::Factor::XS.
       - Totient and Möbius over a range are much faster than separate calls.
       - divisor_sum is 2x faster.
       - primes.pl is much faster with Pillai primes.
       - Reduce overhead in euler_phi -- about 2x faster for individual calls.

0.20  3 February 2012

    - Speedup for PP AKS, and turn off test on 32-bit machines.

    - Replaced fast sqrt detection in PP.pm with a slightly slower version.
      The bloom filter doesn't work right in 32-bit Perl.  These two changes
      should speed up testing on some machines by a huge amount.

    - Fix is_perfect_power in XS AKS.

0.19  1 February 2012

    - Update MR bases with newest from http://miller-rabin.appspot.com/.

    - Fixed some issues when using bignum and Calc BigInt backend, and bignum
      and Perl 5.6.

    - Added tests for bigint is_provable_prime.

    - Added a few tests to give better coverage.

    - Adjust some validation subroutines to cut down on overhead.

0.18  14 January 2012

    - Add random_strong_prime.

    - Fix builds with Solaris 9 and older.

    - Add some debug info to perhaps find out why old ActiveState Perls are
      dying in Math::BigInt::Calc, as if they were using really old versions
      that run out of memory trying to calculate '2 ** 66'.
      http://code.activestate.com/ppm/Math-Prime-Util/

0.17  20 December 2012

    - Perl 5.8.1 - 5.8.7 miscalculates 12345 ** 4, which I used in a test.

    - Fix (hopefully) for MSC compilation.

    - Unroll sieve loop for another 20% or so speedup.  It won't have much
      practical application now that we use Lehmer's method for counts, but
      there are some cases that can still show speedups.

    - Changed the rand functionality yet again.  Sorry.  This should give
      better support for plugging in crypto RNG's when used from other
      modules.

0.16  11 December 2012

    - randbits >= 32 on some 32-bit systems was messing us up.  Restrict our
      internal randbits to wordsize-1.

0.15  9 December 2012

    - Lots of internal changes to Ei, li, Zeta, and R functions:
       - Native Zeta and R have slightly more accurate results.
       - For bignums, use Math::MPFR if possible.  MUCH faster.
         Also allows extended precision while still being fast.
       - Better accuracy for standard bignums.
       - All four functions do:
          - XS if native input.
          - MPFR to whatever accuracy is desired, if Math::MPFR installed.
          - BigFloat versions if no MPFR and BigFloat input.
          - standard version if no MPFR and not a BigFloat.

    - Add tests for primorial, jordan_totient, and divisor_sum.

    - Revamp of the random_prime internals.  Also fixes some issues with
      random n-bit and maurer primes.

    - The random prime and primorial functions now will return a Math::BigInt
      object if the result is greater than the native size.  This includes
      loading up the Math::BigInt library if necessary.

0.14  29 November 2012

    - Compilation and test issues:
          Fix compilation on NetBSD
          Try to fix compilation on Win32 + MSVC
          Speed up some testing, helps a lot with Cygwin on slow machines
          Speed up a lot of slow PP areas, especially used by test suite

    - XS AKS extended from half-word to full-word.

    - Add functions:
           jordan_totient          generalization of Euler Totient
           divisor_sum             run coderef for every divisor

    - Allow environment variables MPU_NO_XS and MPU_NO_GMP to turn off XS and
      GMP support respectively if they are defined and equal to 1.

    - Lehmer prime count for Pure Perl code, including use in nth_prime.
         prime count 10^9 using sieve:
            71.9s   PP sieve
             0.47s  XS sieve
         prime count 10^9 using Lehmer:
             0.70s  PP lehmer
             0.03s  XS lehmer

    - Moved bignum Zeta and R to separate file, only loaded when needed.
      Helpful to get the big rarely-used tables out of the main loading.

    - Quote arguments to Math::Big{Int,Float} in a few places it wasn't.
      Math::Big* coerces the input to a signed value if it isn't a string,
      which causes us all sorts of grief.

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