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

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


Branch: CURRENT, Version: 0.60, Package name: p5-Math-Prime-Util-0.60, 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 run:
[lang/perl5] [security/p5-Bytes-Random-Secure]

Required to build:
[pkgtools/cwrappers]

Master sites: (Expand)

SHA1: 8567f0193d4ffc96df28e66af435fdfe6f0ab7c5
RMD160: ddbf0b8cac76cb919dc83fb05f8c8c270f2fedc0
Filesize: 522.492 KB

Version history: (Expand)


CVS history: (Expand)


   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.
   2016-07-26 08:50:24 by Wen Heping | Files touched by this commit (2) | Package updated
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.
   2016-06-08 21:25:20 by Thomas Klausner | Files touched by this commit (2236) | Package updated
Log message:
Bump PKGREVISION for perl-5.24.
   2016-02-14 12:44:19 by Wen Heping | Files touched by this commit (2) | Package updated
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!
   2015-11-04 00:33:46 by Alistair G. Crooks | Files touched by this commit (262)
Log message:
Add SHA512 digests for distfiles for math category

Problems found locating distfiles:
	Package dfftpack: missing distfile dfftpack-20001209.tar.gz
	Package eispack: missing distfile eispack-20001130.tar.gz
	Package fftpack: missing distfile fftpack-20001130.tar.gz
	Package linpack: missing distfile linpack-20010510.tar.gz
	Package minpack: missing distfile minpack-20001130.tar.gz
	Package odepack: missing distfile odepack-20001130.tar.gz
	Package py-networkx: missing distfile networkx-1.10.tar.gz
	Package py-sympy: missing distfile sympy-0.7.6.1.tar.gz
	Package quadpack: missing distfile quadpack-20001130.tar.gz

Otherwise, existing SHA1 digests verified and found to be the same on
the machine holding the existing distfiles (morden).  All existing
SHA1 digests retained for now as an audit trail.
   2015-06-12 12:52:19 by Thomas Klausner | Files touched by this commit (3152)
Log message:
Recursive PKGREVISION bump for all packages mentioning 'perl',
having a PKGNAME of p5-*, or depending such a package,
for perl-5.22.0.
   2014-09-04 09:09:56 by Wen Heping | Files touched by this commit (2) | Package updated
Log message:
Update to 0.43

Upstream changes please visit:
http://cpansearch.perl.org/src/DANAJ/Ma … 43/Changes