Revision history for Perl extension Math::Prime::Util. 0.23 5 March 2013 - Replace XS Zeta for x > 5 with series from Cephes. It is 1 eps more accurate for a small fraction of inputs. More importantly, it is much faster in range 5 < x < 10. This only affects non-integer inputs. - PP Zeta code replaced (for no-MPFR, non-bignums) with new series. The new code is much more accurate for small values, and *much* faster. - Add consecutive_integer_lcm function, just like MPU::GMP's (though we define ci_lcm(0) = 0, which should get propogated). - Implement binary search on RiemannR for XS nth_prime when n > 2e11. Runs ~2x faster for 1e12, 3x faster for 1e13. Thanks to Programming Praxis for the idea and motivation. - Add the first and second Chebyshev functions (theta and psi). - put isqrt(n) in util.h, use it everywhere. put icbrt(n) in lehmer.h, use it there. - Start on Lagarias-Miller-Odlyzko prime count. - A new data structure for the phi(x,a) function used by all the fast prime count routines. Quite a bit faster and most importantly, uses half the memory of the old structure. - Performance: - Divisor sum with no sub is ~10x faster. - Speed up PP version of exp_mangoldt, create XS version. - Zeta much faster as mentioned above. - faster nth_prime as mentioned above. - AKS about 10% faster. - Unroll a little more in sieve inner loop. A couple percent faster. - Faster prime_count and nth_prime due to new phi(x,a) (about 1.25x). 0.22 26 February 2013 - 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 2013 - 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 2013 - 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. Having a non-working detector led to really bad performance. Hence this and the AKS change should speed up testing on some 32-bit machines by a huge amount. - Fix is_perfect_power in XS AKS. 0.19 1 February 2013 - 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 2013 - 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