Log message:
Update to 0.58
Upstream changes:
0.58 2016-05-21
[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 Quasi-Carmichael 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 128-bit 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.
5-20x 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 3-4x faster than the GMP code for inputs > 300k,
and much faster than the older PP code.
- fromdigits much faster for large base-10 arrays. Timing is better than
split plus join when output is a bigint.
|
Log message:
Update to 0.57
Upstream changes:
0.57 2016-01-03
[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 2015-12-13
[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 anti-lexico).
0.55 2015-10-19
- Fixed test that was using a 64-bit number on 32-bit machines.
[FUNCTIONALITY AND PERFORMANCE]
- Speed up PP versions of sieve_prime_cluster, twin_primes,
twin_prime_count, nth_twin_prime, primes.
0.54 2015-10-14
[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 2015-09-05
[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 2015-08-09
[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 sieve-walking 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^32-1, after which it silently
rolls over. Previously it worked to 2^31-1 then croaked.
- PrimeIterator now uses small segments instead of always next_prime.
A little more memory, but 2-4x 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 Shawe-Taylor 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 2015-06-21
[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 2015-05-03
[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 single-base hashed M-R for 32-bit inputs, inspired by
Fori禳ek and Jan�ina 2015 as well as last year's tests with
2-base (2^49) and 3-base (2^64) hashed solutions for MPU. Primality
testing is 20-40% faster for this size.
- Small speedups for znlog.
- PP nth_prime on 32-bit 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 2-10x tighter bounds.
- Tighten prime count bounds using Axler, Kotnik, Bç¾¹the. Thanks to
Charles R Greathouse IV for pointing me to these.
0.49 2014-11-30
- Make versions the same in all packages.
0.48 2014-11-28
[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 2014-11-18
[ADDED]
- is_mersenne_prime(p) returns 1 iff 2^p-1 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 64-bit platforms is faster for 32-bit inputs.
- AKS is faster for larger than half-word inputs, especially on 64-bit
machines with gcc's 128-bit 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 2014-10-21
[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 non-Math::BigInt (e.g. Math::GMP).
- Improve test coverage.
[PP Updates]
- Large speedup for divisors with bigints in 64-100 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 2014-09-26
[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 15-19 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!
|
Log message:
Update to 0.29
Add missing DEPENDS
Upstream changes:
0.29 30 May 2013
- 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.
- 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)
0.28 23 May 2013
- 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 20 May 2013
- 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 21 April 2013
- Pure Perl factoring:
- real p-1 -- much faster and more effective
- Fermat (no better than HOLF)
- speedup for pbrent
- simple ECM
- redo factoring mix
- New functions:
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 19 March 2013
- 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 10 March 2013
- 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 5 March 2013
- 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 26 February 2013
- 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 22 February 2013
- 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 3 February 2013
- 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 1 February 2013
- 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 14 January 2013
- 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 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.
|