Revision history for Perl module Math::Prime::Util
0.33 2013-11-18
[API Changes]
- all_factors now includes 1 and n, making it identical to Pari's
divisors(n) function, but no longer identical to Math::Factor::XS's
factors(n) function. This change allows consistency between
divisor_sum(n,0) and scalar all_factors(n).
[ADDED]
- factor_exp returns factors as ([p,e],[p,e],...)
- liouville -1^(Omega(n)), OEIS A008836
- partitions partition function p(n), OEIS A000041
[FUNCTIONALITY AND PERFORMANCE]
- all_factors in scalar context returns sigma_0(n).
- exp_mangoldt defaults to XS for speed.
- Fixed Pure Perl 33- to 64-bit is_pseudoprime.
- prime_count uses Lehmer below a threshold (8000M), LMO above.
This keeps good performance while still using low memory. A small
speedup for small (3-6M) inputs has been added. Overall memory use
has been reduced by 2-4x for large inputs.
- Perl RiemannZeta changes:
- Borwein Zeta calculations done in BigInt instead of BigFloat (speed).
- Patch submitted for the frustrating Math::BigFloat defect RT 43692.
With the patch applied, we get much, much better accuracy.
- Accuracy updates, especially with fixed BigFloat.
- Lucas sequence called with bigints will return bigint objects.
- prime_iterator_object should now work with Iterator::Simple.
- chebyshev_theta and chebyshev_psi use segmented sieves.
- More aggressive pruning of tests with 64-bit Perl 5.6. I'd like to
just kill support for systems that can't even add two numbers
correctly, but too many other modules want 5.6 support, and lots of
our functionality *does* work (e.g. primes, prime count, etc.).
0.32 2013-10-13
[ADDED]
- is_proven_prime
- is_proven_prime_with_cert
- carmichael_lambda
- znorder
- prime_iterator_object
- miller_rabin_random
[NEW FEATURES]
- Added Math::Prime::Util::PrimeIterator. A more feature-rich iterator
than the simple closure one from prime_iterator. Experimental.
- Make very simple LMO primecount work, and switch prime_count to use it.
It is slower for large inputs, but uses much less memory. For smaller
inputs it it as fast or faster. Lehmer code modified to constrain
memory use at the expense of speed (starts taking effect at ~ 10^16).
Thanks to Kim Walisch for discussions about this. Note that this is
a very simple implementation -- better code could run 10x faster and
use even less memory.
- divisor_sum can take an integer 'k' in the second argument to compute
sigma_k. This is much faster than using subs, especially when the
result can be computed in XS using native precision. For integer
second arguments, the result will automatically be a bigint if needed.
It is also much faster for larger inputs.
- factor() can be called in scalar context to give the number of
prime factors. The XS function was ignoring the context, and now
is more consistent. It also slightly speeds up looking at the
number of factors, e.g. Omega(x) A001222.
[FUNCTIONALITY AND PERFORMANCE]
- Use MPU::GMP::pn_primorial if we have it.
- Input validation accepts bigint objects and converts them to scalars
entirely in XS.
- random_nbit_prime now uses Fouque and Tibouchi A1 for 65+ bits.
Slightly better uniformity and typically a bit faster.
- Incorporate Montgomery reduction for primality testing, thanks to
Wojciech Izykowski. This is a 1.3 to 1.5x speedup for is_prob_prime,
is_prime, and is_strong_pseudoprime for numbers > 2^32 on x86_64.
This also help things like prime_iterator for values > 2^32.
- Montgomery reduction used in Lucas and Frobenius tests. Up to 2x
speedup for 33 to 64-bit inputs on x86_64/gcc platforms.
- Some fixes around near maxint primes, forprimes, etc. Includes
more workarounds for Math::BigInt::GMP's constructor sign bug.
- Bytes::Random::Secure is loaded only when random prime functionality
is used. Shaves a few milliseconds and bytes off of startup.
- Speedups for Perl (no GMP) primality and random primes.
[MISC]
- Primality functions moved to their own file primality.c.
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