Revision history for Perl module Math::Prime::Util 0.31 2013-08-07 - Change proof certificate documentation to reflect the new text format. - Some platforms were using __int128 when it wasn't supported. Only x86_64 and Power64 use it now. - Small speedup for ranged totient internals. - Patch MPU::GMP 0.13 giving us not quite what we expected from a small certificate. Fixed in MPU::GMP 0.14, worked around here regardless. 0.30 2013-08-06 [API Changes] - Primality proofs now use the new "MPU Certificate" format, which is text rather than a nested Perl data structure. This is much better for external interaction, especially with non-Perl tools. It is not quite as convenient for all-Perl manipulation. [Functions Added] - is_frobenius_underwood_pseudoprime - is_almost_extra_strong_lucas_pseudoprime - lucas_sequence - pplus1_factor [Enhancements] - Documentation and PP is_prime changed to use extra strong Lucas test from the strong test. This matches what the newest MPU::GMP does. This has no effect at all for numbers < 2^64. No counter-example is known for the standard, strong, extra strong, or almost extra strong (increment 1 or 2) tests. The extra strong test is faster than the strong test and produces fewer pseudoprimes. It retains the residue class properties of the strong Lucas test (where the SPSP-2 pseudoprimes favor residue class 1 and the Lucas pseudoprimes favor residue class -1), hence should retain the BPSW test strength. - XS code for all 4 Lucas tests. - Clean up is_prob_prime, also ~10% faster for n >= 885594169. - Small mulmod speedup for non-gcc/x86_64 platforms, and for any platform with gcc 4.4 or newer. [Bug Fixes] - Fixed a rare refcount / bignum / callback issue in next_prime. 0.29 2013-05-30 [Functions Added] - is_pseudoprime (Fermat probable prime test) - is_lucas_pseudoprime (standard Lucas-Selfridge test) - is_extra_strong_lucas_pseudoprime (Mo/Jones/Grantham E.S. Lucas test) - Fix a signed vs. unsigned char issue in ranged moebius. Thanks to the Debian testers for finding this. - XS is_prob_prime / is_prime now use a BPSW-style test (SPRP2 plus extra strong Lucas test) for values over 2^32. This results in up to 2.5x faster performance for large 64-bit values on most machines. All PSP2s have been verified with Jan Feitsma's database. - forprimes now uses a segmented sieve. This (1) allows arbitrary 64-bit ranges with good memory use, and (2) allows nesting on threaded perls. - prime_count_approx for very large values (> 10^36) was very slow without Math::MPFR. Switch to Li+correction for large values if Math::MPFR is not available. - Workaround for MSVC compiler. 0.28 2013-05-23 - An optimization to nth_prime caused occasional threaded Win32 faults. Adjust so this is avoided. - Yet another XS micro-speedup (PERL_NO_GET_CONTEXT) - forprimes { block } [begin,]end. e.g. forprimes { say } 100; $sum = 0; forprimes { $sum += $_ } 1000,50000; say $sum; forprimes { say if is_prime($_+2) } 10000; # print twin primes - my $it = prime_iterator(10000); say $it->(); This is experimental (that is, the interface may change). 0.27 2013-05-20 - is_prime, is_prob_prime, next_prime, and prev_prime now all go straight to XS if possible. This makes them much faster for small inputs without having to use the -nobigint flag. - XS simple number validation to lower function call overhead. Still a lot more overhead compared to directly calling the XS functions, but it shaves a little bit of time off every call. - Speedup pure Perl factoring of small numbers. - is_prob_prime / is_prime about 10% faster for composites. - Allow '+N' as the second parameter to primes.pl. This allows: primes.pl 100 +30 to return the primes between 100 and 130. Or: primes.pl 'nth_prime(1000000000)' +2**8 - Use EXTENDED_TESTING to turn on extra tests. 0.26 2013-04-21 [Pure Perl Factoring] - real p-1 -- much faster and more effective - Fermat (no better than HOLF) - speedup for pbrent - simple ECM - redo factoring mix [Functions Added] prime_certificate produces a certificate of primality. verify_prime checks a primality certificate. - Pure perl primality proof now uses BLS75 instead of Lucas, so some numbers will be much faster [n-1 only needs factoring to (n/2)^1/3]. - Math::Prime::Util::ECAffinePoint and ECProjectivePoint modules for dealing with elliptic curves. 0.25 2013-03-19 - Speed up p-1 stage 2 factoring. Combined with some minor changes to the general factoring combination, ~20% faster for 19 digit semiprimes. - New internal macro to loop over primary sieve starting at 2. Simplifies code in quite a few places. - Forgot to skip one of the tests with broken 5.6.2. 0.24 2013-03-10 - Fix compilation with old pre-C99 strict compilers (decl after statement). - euler_phi on a range wasn't working right with some ranges. - More XS prime count improvements to speed and space. Add some tables to the sieve count so it runs a bit faster. Transition from sieve later. - PP prime count for 10^9 and larger is ~2x faster and uses much less memory. Similar impact for nth_prime 10^8 or larger. - Let factor.pl accept expressions just like primes.pl. 0.23 2013-03-05 - 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 2013-02-26 - 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 2013-02-22 - 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 2013-02-03 - 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 2013-02-01 - 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 2013-01-14 - 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 2012-12-20 - 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 2012-12-11 - randbits >= 32 on some 32-bit systems was messing us up. Restrict our internal randbits to wordsize-1. 0.15 2012-12-09 [Enhancements to Ei, li, Zeta, 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. [Other Changes] - 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 2012-11-29 [Compilation / 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 [Functions Added] - jordan_totient generalization of Euler Totient - divisor_sum run coderef for every divisor [Other Changes] - XS AKS extended from half-word to full-word. - 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 2012-11-19 - Fix an issue with prime count, and make prime count available as a standalone program using primesieve. 0.12 2012-11-17 [Programs Added] - bin/primes.pl - bin/factor.pl [Functions Added] - 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 [Other Changes] - 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 2012-07-23 - 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 2012-07-16 - 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. [Functions Added] - 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 [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. [Support all 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) [Support some functionality of:] - Math::Big (MPU's primes is *much* faster) - Bit::Vector (MPU's primes is ~10x faster) 0.09 2012-06-25 - 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 2012-06-22 - 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 2012-06-17 - 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 2012-06-14 - Change to New/Safefree from malloc. Oops. 0.05 2012-06-11 - 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 2012-06-07 - 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 2012-06-06 - 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 2012-06-05 - 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 2012-06-04 - Initial release