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 6be3cee015b8a43ae6fbd84e96d09d416cac7f91
Author: Dana Jacobsen <d...@acm.org>
Date: Thu Apr 17 16:34:40 2014 -0700
Add one more big-a optimization to legendre_phi
---
TODO | 3 +++
lmo.c | 14 ++++++++++++--
2 files changed, 15 insertions(+), 2 deletions(-)
diff --git a/TODO b/TODO
index 021d8b0..ae9e8e2 100644
--- a/TODO
+++ b/TODO
@@ -68,3 +68,6 @@
- Ensure a fast path for Math::GMP from MPU -> MPU:GMP -> GMP, and back.
- znlog better implementation
+
+- We don't use legendre_phi for other functions any more, but it'd be nice
+ to speed it up using some ideas from the Ohana 2011 SAGE code.
diff --git a/lmo.c b/lmo.c
index 5f98e0f..4004ba3 100644
--- a/lmo.c
+++ b/lmo.c
@@ -338,18 +338,28 @@ static IV _phi(UV x, UV a, int sign, const uint32_t*
const primes, const uint32_
}
UV legendre_phi(UV x, UV a)
{
+ /* If 'x' is very small, give a quick answer with any '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 > prime_count(2^32), then we can need not be concerned with composite
+ * x values with all factors > 2^32, as x is limited to 64-bit. */
if (a > 203280221) { /* prime_count(2**32) */
UV pc = _XS_LMO_pi(x);
return (a > pc) ? 1 : pc - a + 1;
}
+ /* If a is large enough, check the ratios */
+ if (a > 1000000 && x < a*21) { /* x always less than 2^32 */
+ if ( _XS_LMO_pi(x) < a) return 1;
+ }
+
+ /* TODO: R. Andrew Ohana's 2011 SAGE code is faster as the a value
+ * increases. It uses a primelist as in the caching code below, as
+ * well as a binary search prime count on it (like in our lehmer). */
- /* TODO: tune these */
- if ( (x > PHIC && a > 200) || (x > 1000000000 && a > 30) ) {
+ if ( a > 254 || (x > 1000000000 && a > 30) ) {
uint16_t* cache;
uint32_t* primes;
uint32_t lastidx;
--
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
