This is an automated email from the git hooks/post-receive script. ppm-guest pushed a commit to annotated tag v0.36 in repository libmath-prime-util-perl.
commit 2696cc6ed4931d76ef1f310838df796859a82613 Author: Dana Jacobsen <d...@acm.org> Date: Mon Dec 30 01:15:42 2013 -0800 Add moebius/exp_mangoldt to util.c --- Changes | 6 ++++-- util.c | 32 ++++++++++++++++++++++++++++++++ util.h | 2 ++ 3 files changed, 38 insertions(+), 2 deletions(-) diff --git a/Changes b/Changes index 2eff5b0..3358497 100644 --- a/Changes +++ b/Changes @@ -21,6 +21,10 @@ Revision history for Perl module Math::Prime::Util [FUNCTIONALITY AND PERFORMANCE] + - Win32 fixes from bulk88 / bulkdd. Thanks! + + - Lots of XS interface reorgs. + - Speedup for input number validation: speedup for all functions, especially noticeable with fast functions (e.g. small n is_prime(n)). @@ -43,8 +47,6 @@ Revision history for Perl module Math::Prime::Util - znorder uses Carmichael Lambda instead of Euler Phi. Faster. - - carmichael_lambda switched to XS->Perl from Perl->XS. - 0.35 2013-12-08 diff --git a/util.c b/util.c index 336a333..855b592 100644 --- a/util.c +++ b/util.c @@ -825,6 +825,7 @@ UV* _totient_range(UV lo, UV hi) { UV* totients; UV i; if (hi < lo) croak("_totient_range error hi %lu < lo %lu\n", hi, lo); + /* TODO: When is it faster to just do individual calls? */ New(0, totients, hi-lo+1, UV); if (totients == 0) croak("Could not get memory for %"UVuf" totients\n", hi); @@ -980,6 +981,37 @@ UV carmichael_lambda(UV n) { return lambda; } +int moebius(UV n) { + UV factors[MPU_MAX_FACTORS+1]; + UV i, nfactors; + if (n <= 1) return (int)n; + + if ( (!(n% 4) && n >= 4) || (!(n% 9) && n >= 9) || + (!(n%25) && n >= 25) || (!(n%49) && n >= 49) ) + return 0; + + nfactors = factor(n, factors); + for (i = 1; i < nfactors; i++) + if (factors[i] == factors[i-1]) + return 0; + return (nfactors % 2) ? -1 : 1; +} + +UV exp_mangoldt(UV n) { + if (n <= 1) return 1; + else if ((n & (n-1)) == 0) return 2; /* Power of 2 */ + else if ((n & 1) == 0) return 1; /* Even number (not 2) */ + else { + UV i, factors[MPU_MAX_FACTORS+1]; + UV nfactors = factor(n, factors); + for (i = 1; i < nfactors; i++) + if (factors[i] != factors[0]) + return 1; + return factors[0]; + } +} + + UV znorder(UV a, UV n) { UV fac[MPU_MAX_FACTORS+1]; UV exp[MPU_MAX_FACTORS+1]; diff --git a/util.h b/util.h index 1cb51d5..6cb0cbb 100644 --- a/util.h +++ b/util.h @@ -32,6 +32,8 @@ extern int kronecker_su(IV a, UV b); extern int kronecker_ss(IV a, IV b); extern UV totient(UV n); +extern int moebius(UV n); +extern UV exp_mangoldt(UV n); extern UV carmichael_lambda(UV n); extern UV znprimroot(UV n); extern UV znorder(UV a, UV n); -- Alioth's /usr/local/bin/git-commit-notice on /srv/git.debian.org/git/pkg-perl/packages/libmath-prime-util-perl.git _______________________________________________ Pkg-perl-cvs-commits mailing list Pkg-perl-cvs-commits@lists.alioth.debian.org http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/pkg-perl-cvs-commits