Revisions of perl-Math-Prime-Util
Stephan Kulow (coolo)
accepted
request 730893
from
Tina Müller (tinita)
(revision 4)
- 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.
Stephan Kulow (coolo)
accepted
request 523853
from
Stephan Kulow (coolo)
(revision 3)
automatic update
Stephan Kulow (coolo)
accepted
request 401562
from
Stephan Kulow (coolo)
(revision 2)
automatic update
Displaying all 4 revisions
