This is an automated email from the git hooks/post-receive script.
ppm-guest pushed a commit to annotated tag v0.40
in repository libmath-prime-util-perl.
commit 9cfeab9ddabd779b0ef8504bc28e8013d6338d12
Author: Dana Jacobsen <d...@acm.org>
Date: Wed Apr 16 17:40:34 2014 -0700
speedups for legendre_phi with very large a
---
Changes | 1 +
lmo.c | 9 +++++++++
2 files changed, 10 insertions(+)
diff --git a/Changes b/Changes
index b39cc29..45c1912 100644
--- a/Changes
+++ b/Changes
@@ -24,6 +24,7 @@ Revision history for Perl module Math::Prime::Util
- Tighten nth_prime_lower and nth_prime_upper for very small values.
- Fix legendre_phi when given tiny x and large a (odd test case).
+ Some speedups for huge a, from R. Andrew Ohana.
0.39 2014-03-01
diff --git a/lmo.c b/lmo.c
index eab3d92..5f98e0f 100644
--- a/lmo.c
+++ b/lmo.c
@@ -340,6 +340,14 @@ UV legendre_phi(UV x, UV a)
{
if (x <= PHIC)
return tablephi(x, (a > PHIC) ? PHIC : a);
+
+ /* Shortcuts for large values, from R. Andrew Ohana */
+ if (a > (x >> 1)) return 1;
+ if (a > 203280221) { /* prime_count(2**32) */
+ UV pc = _XS_LMO_pi(x);
+ return (a > pc) ? 1 : pc - a + 1;
+ }
+
/* TODO: tune these */
if ( (x > PHIC && a > 200) || (x > 1000000000 && a > 30) ) {
uint16_t* cache;
@@ -353,6 +361,7 @@ UV legendre_phi(UV x, UV a)
Safefree(cache);
return res;
}
+
return _phi_recurse(x, a);
}
/****************************************************************************/
--
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
