Revision history for Perl extension 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