./math/p5-Math-Prime-Util, Perl5 utilities related to prime numbers

[ CVSweb ] [ Homepage ] [ RSS ] [ Required by ] [ Add to tracker ]


Branch: CURRENT, Version: 0.69, Package name: p5-Math-Prime-Util-0.69, Maintainer: pkgsrc-users

A set of utilities related to prime numbers. These include multiple sieving
methods, is_prime, prime_count, nth_prime, approximations and bounds for
the prime_count and nth prime, next_prime and prev_prime, factoring
utilities, and more.


Required to build:
[pkgtools/cwrappers]

Master sites: (Expand)

SHA1: 61bcc8f871fd43154cc09a8a853d2516e877fb0f
RMD160: 3150689afb090de221699c502fb3d445d8398e33
Filesize: 579.995 KB

Version history: (Expand)


CVS history: (Expand)


   2017-11-13 16:22:31 by Thomas Klausner | Files touched by this commit (2) | Package updated
Log message:
p5-Math-Prime-Util: update to 0.69.

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.
   2017-10-23 15:01:48 by Thomas Klausner | Files touched by this commit (2) | Package updated
Log message:
p5-Math-Prime-Util: update to 0.68.

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.
   2017-09-26 16:37:13 by Thomas Klausner | Files touched by this commit (2) | Package updated
Log message:
p5-Math-Prime-Util: update to 0.67.

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.
   2017-09-17 22:11:00 by Thomas Klausner | Files touched by this commit (2) | Package updated
Log message:
p5-Math-Prime-Util: update to 0.66.

0.66 2017-09-12

    [ADDED]

    - random_semiprime                random n-bit semiprime (even split)
    - random_unrestricted_semiprime   random n-bit semiprime
    - forderange { ... } n            derangements iterator
    - numtoperm(n,k)                  returns kth permutation of n elems
    - permtonum([...])                returns rank of permutation array ref
    - randperm(n[,k])                 random permutation of n elements
    - shuffle(...)                    random permutation of an array

    [FUNCTIONALITY AND PERFORMANCE]

    - Rewrite sieve marking based on Kim Walisch's new simple mod-30 sieve.
      Similar in many ways to my old code, but this is simpler and faster.

    - is_pseudoprime, is_euler_pseudoprime, is_strong_pseudoprime changed to
      better handle the unusual case of base >= n.

    - Speedup for is_carmichael.

    - is_frobenius_underwood_pseudoprime checks for jacobi == 0.  Faster.

    - Updated Montgomery inverse from Robert Gerbicz.

    - Tighter nth prime bounds for large inputs from Axler 2017-06.
      Redo Ramanujan bounds since they're based on nth prime bounds.

    - chinese objectifies result (i.e. big results are bigints).

    - Internal support for Baillie-Wagstaff (pg 1402) extra Lucas tests.

    - More standardized Lucas parameter selection.  Like other tests and the
      1980 paper, checks jacobi(D) in the loop, not gcd(D).

    - entropy_bytes, srand, and csrand moved to XS.

    - Add -secure import to disallow all manual seeding.
   2017-06-05 16:25:36 by Ryo ONODERA | Files touched by this commit (2298)
Log message:
Recursive revbump from lang/perl5 5.26.0
   2017-05-13 03:29:02 by Wen Heping | Files touched by this commit (2) | Package updated
Log message:
Update to 0.65

Upstream changes:
0.65 2017-05-03

    [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 lock-free check for a find-in-cache
      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 2017-04-17

    [FUNCTIONALITY AND PERFORMANCE]

    - inverse_li switched to Halley instead of binary search.  Faster.

    - Don't call pre-0.46 GMP backend directly for miller_rabin_random.

0.63 2017-04-16

    [FUNCTIONALITY AND PERFORMANCE]

    - Moved miller_rabin_random to separate interface.
      Make catching of negative bases more explicit.

0.62 2017-04-16

    [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 32-bit integer
    - irand64()                Returns uniform random 64-bit 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, n-1]
    - 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 128-bit string in C, then call _to_bigint).

    - Add a simple Legendre prime sum using uint128_t, which means only for
      modern 64-bit 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 / non-prime.

    - is_primitive_root needs two args, as documented.

    - We do random seeding ourselves now, so remove dependency.

    - Random primes functions moved to XS / GMP, 3-10x faster.

0.61 2017-03-12

    [ADDED]

    - is_semiprime(n)        Returns 1 if n has exactly 2 prime factors
    - is_pillai(p)           Returns 0 or v wherev v! % n == n-1 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 Brent-Harvey.  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.2-1.7x faster.
       = is_primitive_root.  Up to 2x faster for some inputs.
       = p-1 factoring stage 1.

    - Tune AKS r/s selection above 32-bit.

    - 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 pathological-but-reasonable 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.
   2016-11-28 13:36:05 by Wen Heping | Files touched by this commit (2) | Package updated
Log message:
Update to 0.60

Upstream changes:
0.60 2016-10-09

    [ADDED]

    - vecfirstidx { expr } @n             returns first index with expr true

    [FUNCTIONALITY AND PERFORMANCE]

    - Expanded and modified prime count sparse tables. Prime counts from 30k
      to 90M are 1.2x to 2.5x faster.  It has no appreciable effect on the
      speed of prime counts larger than this size.

    - fromdigits works with bigint first arg, no need to stringify.
      Slightly faster for bigints, but slower than desired.

    - Various speedups and changes for fromdigits, todigits, todigitstring.

    - vecprod in PP for negative high-bit would return double not bigint.

    - Lah numbers added as Stirling numbers of the third kind.  They've been
      in the GMP code for almost 2 years now.  Also for big results, directly
      call the GMP code and objectify the result.

    - Small performance change to AKS (r,s) selection tuning.

    - On x86_64, use Montgomery math for Pollard/Brent Rho.  This speeds up
      factoring significantly for large native inputs (e.g. 10-20 digits).

    - Use new GMP zeta and riemannr functions if possible, making some of
      our operations much faster without Math::MPFR.

    - print_primes with large args will try GMP sieve for big speedup.  E.g.
        use bigint;  print_primes(2e19,2e19+1e7);
      goes from 37 minutes to 7 seconds.  This also removes a mistaken blank
      line at the end for certain ranges.

    - PP primes tries to use GMP.  Only for calls from other PP code.

    - Slightly more accuracy in native ExponentialIntegral.

    - Slightly more accuracy in twin_prime_count_approx.

    - nth_twin_prime_approx was incorrect over 1e10 and over 2e16 would
      infinite loop due to Perl double conversion.

    - nth_twin_prime_approx a little faster and more accurate.
   2016-08-09 02:14:33 by Wen Heping | Files touched by this commit (2) | Package updated
Log message:
Update to 0.59

Upstream changes:
0.59 2016-08-03

    [ADDED]

    - is_prime_power         Returns k if n=p^k for p a prime.
    - logint(n,b)            Integer logarithm.  Largest e s.t. b^e <= n.
    - rootint(n,k)           Integer k-th root.
    - ramanujan_sum(k,n)     Ramanujan's sum

    [FUNCTIONALITY AND PERFORMANCE]

    - Fixes for quadmath:
      + Fix "infinity" in t/11-primes.t.
      + Fix native Pi to use quads.
      + Trim some threading tests.

    - Fix fromdigits memory error with large string.

    - Remove 3 threading tests that were causing issues with Perl -DDEBUGGING.

    - foroddcomposites with some odd start values could index incorrectly.

    - is_primitive_root(1,0) returns 0 instead of fp exception.

    - mertens() uses a little less memory.

    - 2x speedup for znlog with bigint values.

    - is_pseudoprime() and is_euler_pseudoprime() use Montgomery math so are
      much faster.  They seem to be ~5% faster than Miller-Rabin now.

    - is_catalan_pseudoprime 1.1x to 1.4x faster.

    - is_perrin_pseudoprime over 10x faster.
      Uses Adams/Shanks doubling and Montgomery math.
      Single core, odd composites: ~8M range/s.

    - Add restricted Perrin pseudoprimes using an optional argument.

    - Add bloom filters to reject non-perfect cubes, fifths, and sevenths.
      is_power about 2-3x faster for native inputs.

    - forcomposites / foroddcomposites about 1.2x faster past 64-bit.

    - exp_mangoldt rewritten to use is_prime_power.

    - Integer root code rewritten and now exported.

    - We've been hacking around the problem of older Perls autovivifying
      functions at compile time.  This makes functions that don't exist
      return true when asked if they're defined, which causes us distress.

      Store the available GMP functions before loading the PP code.

      XS code knows MPU::GMP version and calls as appropriate.  This works
      around the auto-vivication, and lets us choose to call the GMP
      function based on version instead of just existence.
      E.g. GMP's is_power was added in 0.19, but didn't support negative
      powers until 0.28.