This is an automated email from the git hooks/post-receive script. ppm-guest pushed a commit to annotated tag v0.31 in repository libmath-prime-util-perl.
commit a7281dcb418ab5accc00e44396f354f98534b076 Author: Dana Jacobsen <d...@acm.org> Date: Tue Aug 6 17:13:09 2013 -0700 10-15% speedup for ranged totient internals --- Changes | 2 ++ TODO | 4 +++- util.c | 26 +++++++++++++++----------- 3 files changed, 20 insertions(+), 12 deletions(-) diff --git a/Changes b/Changes index 0446afb..3f6ab5e 100644 --- a/Changes +++ b/Changes @@ -7,6 +7,8 @@ Revision history for Perl module Math::Prime::Util - Some platforms were using __int128 when it wasn't supported. Only x86_64 and Power64 use it now. + - Small speedup for ranged totient internals. + 0.30 2013-08-06 [API Changes] diff --git a/TODO b/TODO index dc0f142..146dc4c 100644 --- a/TODO +++ b/TODO @@ -26,7 +26,9 @@ - More efficient Mertens. The current version has poor growth. -- More efficient totient segment. Do we really need primes to n/2? +- It may be possible to have a more efficient ranged totient. We're using + the sieve up to n/2, which is better than most people seem to use, but I'm + not completely convinced we can't do better. - Implement S2 calculation for LMO prime count. diff --git a/util.c b/util.c index f0742f4..523ce65 100644 --- a/util.c +++ b/util.c @@ -837,22 +837,26 @@ signed char* _moebius_range(UV lo, UV hi) UV* _totient_range(UV lo, UV hi) { UV* totients; - UV i, sievehi; + UV i, hidiv2; if (hi < lo) croak("_totient_range error hi %lu < lo %lu\n", hi, lo); New(0, totients, hi-lo+1, UV); if (totients == 0) croak("Could not get memory for %"UVuf" totients\n", hi); - for (i = lo; i <= hi; i++) - totients[i-lo] = i; - sievehi = hi/2; - for (i=P2GTLO(2*2,2,lo); i <= hi; i += 2) totients[i-lo] -= totients[i-lo]/2; - START_DO_FOR_EACH_PRIME(3, sievehi) { - for (i = P2GTLO(2*p,p,lo); i <= hi; i += p) - totients[i-lo] -= totients[i-lo]/p; + for (i = lo; i <= hi; i++) { + UV v = i; + if (i % 2 == 0) v -= v/2; + if (i % 3 == 0) v -= v/3; + if (i % 5 == 0) v -= v/5; + totients[i-lo] = v; + } + hidiv2 = hi/2; + START_DO_FOR_EACH_PRIME(2, hi) { + if (p >= lo) + totients[p-lo] = p-1; + if (p >= 7 && p <= hidiv2) + for (i = P2GTLO(2*p,p,lo); i <= hi; i += p) + totients[i-lo] -= totients[i-lo]/p; } END_DO_FOR_EACH_PRIME - for (i = lo; i <= hi; i++) - if (totients[i-lo] == i) - totients[i-lo] = i-1; return totients; } -- 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