# [libmath-prime-util-perl] 19/25: Restructure step 7 phi summation to streamline inner loop

```This is an automated email from the git hooks/post-receive script.

ppm-guest pushed a commit to annotated tag v0.35
in repository libmath-prime-util-perl.```
```
commit 1ff0a217e8d3745b443ee6c203fec6e5ae1a1050
Author: Dana Jacobsen <d...@acm.org>
Date:   Fri Dec 6 17:12:36 2013 -0800

Restructure step 7 phi summation to streamline inner loop
---
lmo.c | 17 +++++++++--------
1 file changed, 9 insertions(+), 8 deletions(-)

diff --git a/lmo.c b/lmo.c
index cd54252..167db82 100644
--- a/lmo.c
+++ b/lmo.c
@@ -571,18 +571,19 @@ UV _XS_LMO_pi(UV n)
if (start < ss.prime_index[k])
ss.prime_index[k] = start;
}
-    /* Step 7:  For KM <= K < Pi_M:  For primes[k+2] <= x <= M,
-     * sum phi(n / (x*primes[k+1]), k). */
+    /* Step 7:  For KM <= K < Pi_M:  For primes[k+2] <= x <= M, sum
+     * phi(n / (x*primes[k+1]), k).  The inner for loop can be parallelized. */
for (; k < step7_max; k++) {
remove_primes(k, k, &ss, primes);
if (ss.prime_index[k] >= k+2) {
UV pk = primes[k+1];
-        for (j = ss.prime_index[k]; j >= k+2; j--) {
-          UV divisor = pk * primes[j];
-          if (divisor <= least_divisor) break;
-          sum1 += sieve_phi(n / divisor);
-        }
-        ss.prime_index[k] = j;
+        UV endj = ss.prime_index[k];
+        while (endj > 7 && endj-7 >= k+2 && pk*primes[endj-7] > least_divisor)
endj -= 8;
+        while (            endj   >= k+2 && pk*primes[endj  ] > least_divisor)
endj--;
+        /* Now that we know how far to go, do the summations */
+        for (j = ss.prime_index[k]; j > endj; j--)
+          sum1 += sieve_phi(n / (pk*primes[j]));
+        ss.prime_index[k] = endj;
}
}
/* Restrict work for the above loop when we know it will be empty. */

--
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
```