- updated to 0.73
see /usr/share/doc/packages/perl-Math-Prime-Util/Changes
0.73 2018-11-15

[ADDED]

- inverse_totient(n) the image of euler_phi(n)

[FIXES]

- Try to work around 32-bit platforms in semiprime approximations.
Cannot reproduce on any of my 32-bit test platforms.

- Fix RT 127605, memory use in for... iterators.


0.72 2018-11-08

[ADDED]

- nth_semiprime(n) the nth semiprime
- nth_semiprime_approx(n) fast approximate nth semiprime
- semiprime_count_approx(n) fast approximate semiprime count
- semi_primes as primes but for semiprimes
- forsetproduct {...} \@a,\@b,... Cartesian product of list refs

[FIXES]

- Some platforms are extremely slow for is_pillai. Speed up tests.

- Ensure random_factored_integer factor list is sorted min->max.

- forcomposites didn't check lastfor on every callback.

- Sun's compilers, in a valid interpretation of the code, generated
divide by zero code for pillai testing.

[FUNCTIONALITY AND PERFORMANCE]

- chebyshev_theta and chebyshev_psi redone and uses a table.
Large inputs are significantly faster.

- Convert some FP functions to use quadmath if possible. Without
quadmath there should be no change. With quadmath functions like
LogarithmicIntegral and LambertW will be slower but more accurate.

- semiprime_count for non-trivial inputs uses a segmented sieve and
precalculates primes for larger values so can run 2-3x faster.

- forsemiprimes uses a sieve so large ranges are much faster.

- ranged moebius more efficient for small intervals.

- Thanks to GRAY for his module Set::Product which has clean and
clever XS code, which I used to improve my code.

- forfactored uses multicall. Up to 2x faster.

- forperm, forcomb, forderange uses multicall. 2-3x faster.

- Frobenius-Khashin algorithm changed from 2013 version to 2016/2018.


0.71 2018-08-28

[ADDED]

- forfactored { ... } a,b loop n=a..b setting $_=n, @_=factor(n)
- forsquarefree { ... } a,b as forfactored, but only square-free n
- forsemiprimes { ... } a,b as forcomposites, but only semiprimes
- random_factored_integer(n) random [1..n] w/ array ref of factors
- semiprime_count([lo],hi) counts semiprimes in range

[FIXES]

- Monolithic sieves beyond 30*2^32 (~ 1.2 * 10^11) overflowed.

- is_semiprime was wrong for five small values since 0.69. Fixed.

[FUNCTIONALITY AND PERFORMANCE]

- is_primitive_root much faster (doesn't need to calulate totient,
and faster rejection when n has no primitive root).

- znprimroot and znorder use Montgomery, 1.2x to 2x faster.

- slightly faster sieve_range for native size inputs (use factor_one).

- bin/primes.pl faster for palindromic primes and works for 10^17

[OTHER]

- Added ability to use -DBENCH_SEG for benchmarking sieves using
prime_count and ntheory::_segment_pi without table optimizations.

- Reorg of main factor loop. Should be identical from external view.

- Internal change to is_semiprime and is_catalan_pseudoprime.


0.70 2017-12-02

[FIXES]

- prime_count(a,b) incorrect for a={3..7} and b < 66000000.
First appeared in v0.65 (May 2017).
Reported by Trizen. Fixed.

- Also impacted were nth_ramanujan_prime and _lower/_upper for
small input values.

[FUNCTIONALITY AND PERFORMANCE]

- Some utility functions used prime counts. Unlink for more isolation.

- prime_count_approx uses full precision for bigint or string input.

- LogarithmicIntegral and ExponentialIntegral will try to use
our GMP backend if possible.

- Work around old Math::BigInt::FastCalc (as_int() doesn't work right).

- prime_memfree also calls GMP's memfree function. This will clear the
cached constants (e.g. Pi, Euler).

- Calling srand or csrand will also result in the GMP backend CSPRNG
functions being called. This gives more consistent behavior.

[OTHER]

- Turned off threads testing unless release or extended testing is used.
A few smokers seem to have threads lib that die before we event start.

- Removed all Math::MPFR code and references. The latest GMP backend
has everything we need.

- The MPU_NO_XS and MPU_NO_GMP environment variables are documented.


0.69 2017-11-08

[ADDED]

- is_totient(n) true if euler_phi(x) == n for some x

[FUNCTIONALITY AND PERFORMANCE]

- is_square_free uses abs(n), like Pari and moebius.

- is_primitive_root could be wrong with even n on some platforms.

- euler_phi and moebius with negative range inputs weren't consistent.

- factorialmod given a large n and m where m was a composite with
large square factors was incorrect. Fixed.

- numtoperm will accept negative k values (k is always mod n!)

- Split XS mapping of many primality tests. Makes more sense and
improves performance for some calls.

- Split final test in PP cluster sieve.

- Support some new Math::Prime::Util::GMP functions from 0.47.

- C spigot Pi is 30-60% faster on x86_64 by using 32-bit types.

- Reworked some factoring code.

- Remove ISAAC (Perl and C) since we use ChaCha.

- Each thread allocs a new const array again instead of sharing.


0.68 2017-10-19

[API Changes]

- forcomb with one argument iterates over the power set, so k=0..n
instead of k=n. The previous behavior was undocumented. The new
behavior matches Pari/GP (forsubset) and Perl6 (combinations).

[ADDED]

- factorialmod(n,m) n! mod m calculated efficiently
- is_fundamental(d) true if d a fundamental discriminant

[FUNCTIONALITY AND PERFORMANCE]

- Unknown bigint classes no longer return two values after objectify.
Thanks to Daniel Șuteu for finding this.

- Using lastfor inside a formultiperm works correctly now.

- randperm a little faster for k < n cases, and can handle big n
values without running out of memory as long as k << n.
E.g. 5000 random native ints without dups: @r = randperm(~0,5000);

- forpart with primes pulls min/max values in for a small speedup.

- forderange 10-20% faster.

- hammingweight for bigints 3-8x faster.

- Add Math::GMPq and Math::AnyNum as possible bigint classes. Inputs
of these types will be relied on to stringify correctly, and if this
results in an integer string, to intify correctly. This should give
a large speedup for these types.

- Factoring native integers is 1.2x - 2x faster. This is due to a
number of changes.

- Add Lehman factoring core. Since this is not exported or used by
default, the API for factor_lehman may change.

- All new Montgomery math. Uses mulredc asm from Ben Buhrow.
Faster and smaller. Most primality and factoring code 10% faster.

- Speedup for factoring by running more Pollard-Rho-Brent, revising
SQUFOF, updating HOLF, updating recipe.


0.67 2017-09-23

[ADDED]

- lastfor stops forprimes (etc.) iterations
- is_square(n) returns 1 if n is a perfect square
- is_polygonal(n,k) returns 1 if n is a k-gonal number

[FUNCTIONALITY AND PERFORMANCE]

- shuffle prototype is @ instead of ;@, so matches List::Util.

- On Perl 5.8 and earlier we will call PP instead of trying
direct-to-GMP. Works around a bug in XS trying to turn the
result into an object where 5.8.7 and earlier gets lost.

- We create more const integers, which speeds up common uses of
permutations.

- CSPRNG now stores context per-thread rather than using a single
mutex-protected context. This speeds up anything using random
numbers a fair amount, especially with threaded Perls.

- With the above two optimizations, randperm(144) is 2.5x faster.

- threading test has threaded srand/irand test added back in, showing
context is per-thread. Each thread gets its own sequence and calls
to srand/csrand and using randomness doesn't impact other threads.