Log message:
Update to 0.65
Upstream changes:
0.65 20170503
[API Changes]
 Config options irand and primeinc are deprecated. They will carp if set.
[FUNCTIONALITY AND PERFORMANCE]
 Add Math::BigInt::Lite to list of known bigint objects.
 sum_primes fix for certain ranges with results near 2^64.
 is_prime, next_prime, prev_prime do a lockfree check for a findincache
optimization. This is a big help on on some platforms with many threads.
 C versions of LogarithmicIntegral and inverse_li rewritten.
inverse_li honors the documentation promise within FP representation.
Thanks to Kim Walisch for motivation and discussion.
 Slightly faster XS nth_prime_approx.
 PP nth_prime_approx uses inverse_li past 1e12, which should run
at a reasonable speed now.
 Adjusted crossover points for segment vs. LMO interval prime_count.
 Slightly tighter prime_count_lower, nth_prime_upper, and Ramanujan bounds.
0.64 20170417
[FUNCTIONALITY AND PERFORMANCE]
 inverse_li switched to Halley instead of binary search. Faster.
 Don't call pre0.46 GMP backend directly for miller_rabin_random.
0.63 20170416
[FUNCTIONALITY AND PERFORMANCE]
 Moved miller_rabin_random to separate interface.
Make catching of negative bases more explicit.
0.62 20170416
[API Changes]
 The 'irand' config option is removed, as we now use our own CSPRNG.
It can be seeded with csrand() or srand(). The latter is not exported.
 The 'primeinc' config option is deprecated and will go away soon.
[ADDED]
 irand() Returns uniform random 32bit integer
 irand64() Returns uniform random 64bit integer
 drand([fmax]) Returns uniform random NV (floating point)
 urandomb(n) Returns uniform random integer less than 2^n
 urandomm(n) Returns uniform random integer in [0, n1]
 random_bytes(nbytes) Return a string of CSPRNG bytes
 csrand(data) Seed the CSPRNG
 srand([UV]) Insecure seed for the CSPRNG (not exported)
 entropy_bytes(nbytes) Returns data from our entropy source
 :rand Exports srand, rand, irand, irand64
 nth_ramanujan_prime_upper(n) Upper limit of nth Ramanujan prime
 nth_ramanujan_prime_lower(n) Lower limit of nth Ramanujan prime
 nth_ramanujan_prime_approx(n) Approximate nth Ramanujan prime
 ramanujan_prime_count_upper(n) Upper limit of Ramanujan prime count
 ramanujan_prime_count_lower(n) Lower limit of Ramanujan prime count
 ramanujan_prime_count_approx(n) Approximate Ramanujan prime count
[FUNCTIONALITY AND PERFORMANCE]
 vecsum is faster when returning a bigint from native inputs (we
construct the 128bit string in C, then call _to_bigint).
 Add a simple Legendre prime sum using uint128_t, which means only for
modern 64bit compilers. It allows reasonably fast prime sums for
larger inputs, e.g. 10^12 in 10 seconds. Kim Walisch's primesum is
much more sophisticated and over 100x faster.
 is_pillai about 10x faster for composites.
 Much faster Ramanujan prime count and nth prime. These also now use
vastly less memory even with large inputs.
 small speed ups for cluster sieve.
 faster PP is_semiprime.
 Add prime option to forpart restrictions for all prime / nonprime.
 is_primitive_root needs two args, as documented.
 We do random seeding ourselves now, so remove dependency.
 Random primes functions moved to XS / GMP, 310x faster.
0.61 20170312
[ADDED]
 is_semiprime(n) Returns 1 if n has exactly 2 prime factors
 is_pillai(p) Returns 0 or v wherev v! % n == n1 and n % v != 1
 inverse_li(n) Integer inverse of Logarithmic Integral
[FUNCTIONALITY AND PERFORMANCE]
 is_power(1,k) now returns true for odd k.
 RiemannZeta with GMP was not subtracting 1 from results > 9.
 PP Bernoulli algorithm changed to Seidel from BrentHarvey. 2x speedup.
Math::BigNum is 10x faster, and our GMP code is 2000x faster.
 LambertW changes in C and PP. Much better initial approximation, and
switch iteration from Halley to Fritsch. 2 to 10x faster.
 Try to use GMP LambertW for bignums if it is available.
 Use Montgomery math in more places:
= sqrtmod. 1.21.7x faster.
= is_primitive_root. Up to 2x faster for some inputs.
= p1 factoring stage 1.
 Tune AKS r/s selection above 32bit.
 primes.pl uses twin_primes function for ~3x speedup.
 native chinese can handle some cases that used to overflow. Use Shell
sort on moduli to prevent pathologicalbutreasonable test case.
 chinese directly to GMP
 Switch to Bytes::Random::Secure::Tiny  fewer dependencies.
 PP nth_prime_approx has better MSE and uses inverse_li above 10^12.
 All random prime functions will use GMP versions if possible and
if a custom irand has not been configured.
They are much faster than the PP versions at smaller bit sizes.
 is_carmichael and is_pillai small speedups.

Log message:
Update to 0.58
Upstream changes:
0.58 20160521
[API Changes]
 prev_prime($n) where $n <= 2 now returns undef instead of 0. This
may enable catching range errors, and is technically more correct.
 nth_prime(0) now returns undef instead of 0. This should help catch
cases where the base wasn't understood. The change is similar for
all the nth_* functions (e.g. nth_twin_prime).
 sumdigits(n,base) will interpret n as a number in the given base,
rather than the Pari/GP method of converting decimal n to that base
then summing. This allows sumdigits to easily sum hex strings.
The old behavior is easily done with vecsum(todigits(n, base)).
 binary() was not intended to be released (todigits and todigitstring
are supersets), but the documentation got left in. Remove docs.
[ADDED]
 addmod(a, b, n) a + b mod n
 mulmod(a, b, n) a * b mod n
 divmod(a, b, n) a / b mod n
 powmod(a, b, n) a ^ b mod n
 sqrtmod(a, n) modular square root
 is_euler_pseudoprime(n,a[...]) Euler test to given bases
 is_primitive_root(r, n) is r a primitive root mod n
 is_quasi_carmichael(n) is n a QuasiCarmichael number
 hclassno(n) Hurwitz class number H(n) * 12
 sieve_range(n, width, depth) sieve to given depth, return offsets
[FUNCTIONALITY AND PERFORMANCE]
 Fixed incorrect table entries for 2^16th Ramanujan prime count and
nth_ramanujan_prime(23744).
 foroddcomposites with certain arguments would start with 10 instead of 9.
 lucasu and lucasv should return bigint types.
 vecsum will handle 128bit sums internally (performance increase).
 Speedup is_carmichael.
 Speedup znprimroot, 10% for small inputs, 10x for large composites.
 Speedup znlog ~2x. It is now Rho racing an interleaved BSGS.
 Change AKS to Bernstein 2003 theorem 4.1.
520x faster than Bornemann, 20000+x faster than V6.
 sum_primes now uses tables for native sizes (performance increase).
 ramanujan_tau uses Cohen's hclassno method instead of the sigma
calculation. This is 34x faster than the GMP code for inputs > 300k,
and much faster than the older PP code.
 fromdigits much faster for large base10 arrays. Timing is better than
split plus join when output is a bigint.

Log message:
Update to 0.57
Upstream changes:
0.57 20160103
[ADDED]
 formultiperm { ... } \@n loop over multiset permutations
 todigits(n[,base[,len]]) convert n to digit array
 todigitstring(n[,base[,len]]) convert n to string
 fromdigits(\@d[,base]) convert digit array ref to number
 fromdigits(str[,base]) convert string to number
 ramanujan_prime_count counts Ramanujan primes in range
 vecany { expr } @n true if any expr is true
 vecall { expr } @n true if all expr are true
 vecnone { expr } @n true if no expr are true
 vecnotall { expr } @n true if not all expr are true
 vecfirst { expr } @n returns first element with expr true
[FUNCTIONALITY AND PERFORMANCE]
 nth_ramanujan_prime(997) was wrong. Fixed.
 Tighten Ramanujan prime bounds. Big speedups for large nth Rp.
0.56 20151213
[ADDED]
 is_carmichael(n) Returns 1 if n is a Carmichael number
 forcomp { ... } n[,{...}] loop over compositions
[FUNCTIONALITY AND PERFORMANCE]
 Faster, nonrecursive divisors_from_factors routine.
 gcdext(0,0) returns (0,0,0) to match GMP and Pari/GP.
 Use better prime count lower/upper bounds from Bç¾¹the 2015.
 forpart and forcomp both use lexicographic order (was antilexico).
0.55 20151019
 Fixed test that was using a 64bit number on 32bit machines.
[FUNCTIONALITY AND PERFORMANCE]
 Speed up PP versions of sieve_prime_cluster, twin_primes,
twin_prime_count, nth_twin_prime, primes.
0.54 20151014
[ADDED]
 sieve_prime_cluster(low,high[,...]) find prime clusters
[Misc]
 Certain small primes used to return false with Frobenius and AES Lucas
tests when given extra arguments. Both are unusual cases never used
by the main system. Fixed.
0.53 20150905
[ADDED]
 ramanujan_tau(n) Ramanujan's Tau function
 sumdigits(n[,base]) sum digits of n
[FUNCTIONALITY AND PERFORMANCE]
 Don't use Math::MPFR unless underlying MPFR library is at least 3.x.
 Use new Math::Prime::Util::GMP::sigma function for divisor_sum.
 Use new Math::Prime::Util::GMP::sieve_twin_primes(a,b).
0.52 20150809
[ADDED]
 is_square_free(n) Check for repeated factors
[FUNCTIONALITY AND PERFORMANCE]
 print_primes with 2 args was sending to wrong fileno.
 Double speed of sum_primes.
 Rewrote some internal sievewalking code, speeds up next_prime,
forprimes, print_primes, and more.
 Small speedup for forcomposites / foroddcomposites.
 Small speedup for is_prime with composite 32+ bit inputs.
 is_frobenius_khashin_pseudoprime now uses Montgomery math for speed.
 PrimeArray now treats skipping forward by relatively small amounts as
forward iteration. This makes it much more efficient for many cases,
but does open up some pathological cases.
 PrimeArray now allows exporting @primes (and a few others), which
saves some typing.
 PrimeArray now works for indices up to 2^321, after which it silently
rolls over. Previously it worked to 2^311 then croaked.
 PrimeIterator now uses small segments instead of always next_prime.
A little more memory, but 24x faster.
 factor, divisor, fordivisors and some others should better keep
bigint types (e.g. Math::GMPz input yields Math::GMPz output).
 Faster GCD on some platforms.
 Peter Dettman supplied a patch for ShaweTaylor prime generation to
make it deterministically match reference implementations. Thanks!
[Misc]
 Check for old MPFR now using C library version, not module version.
 prime_count_{lower,upper} now uses MPFR to give full precision.
 Montgomery math and uint128_t enabled on Darwin/clang.
0.51 20150621
[ADDED]
 sum_primes(lo,hi) Summation of primes in range
 print_primes(lo,hi[,fd]) Print primes to stdout or fd
 is_catalan_pseudoprime(n) Catalan primality test
 is_frobenius_khashin_pseudoprime(n) Khashin's 2013 Frobenius test
[FUNCTIONALITY AND PERFORMANCE]
 Slightly faster PP sieving using better code from Perlmonks.
 Lucas sequence works with even valued n.
 Used idea from Colin Wright to speed up is_perrin_pseudoprime 5x.
We can check smaller congruent sequences for composites as a prefilter.
 is_frobenius_pseudoprime no longer checks for perfect squares, and
doesn't bail to BPSW if P,Q,D exceed n. This makes it produce some
pseudoprimes it did not before (but ought to have).
[Misc]
 Work with old MPFR (some test failures in older Win32 systems).
 Don't assert in global destructor if a MemFree object is destroyed.
0.50 20150503
[ADDED]
 harmfrac(n) (num,den) of Harmonic number
 harmreal(n) Harmonic number as BigFloat
 sqrtint(n) Integer square root of n
 vecextract(\@arr, mask) Return elements from arr selected by mask
 ramanujan_primes(lo,hi) Ramanujan primes R_n in [lo,hi]
 nth_ramanujan_prime(n) the nth Ramanujan prime R_n
 is_ramanujan_prime(n) 1 if n is a Ramanujan prime, 0 otherwise
[FUNCTIONALITY AND PERFORMANCE]
 Implement singlebase hashed MR for 32bit inputs, inspired by
Foriç¦³ek and Janï¿½ina 2015 as well as last year's tests with
2base (2^49) and 3base (2^64) hashed solutions for MPU. Primality
testing is 2040% faster for this size.
 Small speedups for znlog.
 PP nth_prime on 32bit fixed for values over 2^32.
[Misc]
 Changes to nth_prime_{lower,upper}. They use the Axler (2013) bounds,
and the XS code will also use inverse prime count bounds for small
values. This gives 210x tighter bounds.
 Tighten prime count bounds using Axler, Kotnik, Bç¾¹the. Thanks to
Charles R Greathouse IV for pointing me to these.
0.49 20141130
 Make versions the same in all packages.
0.48 20141128
[ADDED]
 lucasu(P, Q, k) U_k for Lucas(P,Q)
 lucasv(P, Q, k) V_k for Lucas(P,Q)
[Misc]
 Use Axler (2014) bounds for prime count where they improve on Dusart.
0.47 20141118
[ADDED]
 is_mersenne_prime(p) returns 1 iff 2^p1 is prime
[FUNCTIONALITY AND PERFORMANCE]
 Standalone compilation (e.g. factoring without Perl installed) is easier.
 For next_prime and prev_prime with bigints, stay in XS as long as
possible to cut overhead. Up to 1.5x faster.
 Factoring on 64bit platforms is faster for 32bit inputs.
 AKS is faster for larger than halfword inputs, especially on 64bit
machines with gcc's 128bit types.
 is_provable_prime goes through XS first, so can run *much* faster for
small inputs.
[OTHER]
 NetBSD improperly exports symbols in string.h, including popcount.
Rename our internal function to work around it.
 is_power now takes an optional scalar reference third argument which
will be set to the root if found. It also works for negative n.
 Changes to trim a little memory use. lucas_sequence goes from
PP>[XS,GMP,PP] to XS[>PP[>GMP]]. ecm_factor is moved out of root.
Moved some primality proving logic out of root.
 primes.pl when given one argument will show primes up to that number.
0.46 20141021
[API Changes]
 is_pseudoprime has the same signature as is_strong_pseudoprime now.
This means it requires one or more bases and has no default base.
The documentation had never mentioned the default, so this should
have little impact, and the common signature makes more sense.
[ADDED]
 hammingweight(n) Population count (count binary 1s)
 vecreduce {...} @v Reduce/fold, exactly like List::Util::reduce
[Misc]
 Syntax fix from Salvatore.
 vecmin / vecmax in XS, if overflows UV do via strings to avoid PP.
 Add example for verifying prime gaps, similar to Nicely's cglp4.
 divisor_sum wasn't running XS code for k=0. Refactor PP code,
includes speedup when input is a nonMath::BigInt (e.g. Math::GMP).
 Improve test coverage.
[PP Updates]
 Large speedup for divisors with bigints in 64100 bit range.
 Revamp RiemannZeta. Fixes some bignum output, but requires RT fixes.
 Optimization for PP comparison to ~0.
 PP factoring is faster, especially for small inputs.
0.45 20140926
[ADDED]
 forcomb { ... } n, k combinations iterator
 forperm { ... } n permutations iterator
 factorial(n) n!
 is_bpsw_prime(n) primality test with no pretests, just ES BPSW
 is_frobenius_pseudoprime Frobenius quadratic primality test
 is_perrin_pseudoprime Perrin primality test (unrestricted)
 vecmin(@list) minimum of list of integers
 vecmax(@list) maximum of list of integers
 vecprod(@list) product of list of integers
 bernfrac(n) (num,den) of Bernoulli number
 bernreal(n) Bernoulli number as BigFloat
 stirling(n,m,[type]) Stirling numbers of first or second kind
 LambertW(k) Solves for W in k = W*exp(W)
 Pi([digits]) Pi as NV or with requested digits
[FUNCTIONALITY AND PERFORMANCE]
 znorder algorithm changed from Das to Cohen for ~1% speedup.
 factoring sped up a bit for 1519 digits.
 speedup for divisor_sum with very large exponents.
[OTHER]
 Alias added for the module name "ntheory". The module has grown
enough that it seems more appropriate.
 Big build change: Try a GMP compilation and add Math::Prime::Util::GMP
to dependency list if it succeeds.
 Fixed a memory leak in segment_primes / segment_twin_primes introduced
in previous release. Thanks Valgrind!
