Legendre prime counting function: Difference between revisions
→{{header|jq}}: add JavaScript version above...
GordonBGood (talk | contribs) (→{{header|Mathematica}}/{{header|Wolfram Language}}: add Kotlin implementations above...) |
GordonBGood (talk | contribs) (→{{header|jq}}: add JavaScript version above...) |
||
Line 1,585:
10^9 50847534
</pre>
=={{header|JavaScript}}==
There doesn't seem to be much point to contributing memoized (Hash table) versions as they seem to be the result of the task author not realizing that there is a simple way of keeping the computation complexity from having exponential growth with counting range by limiting the "splitting" of the "phi" calculation when the result must be just one. Accordingly, the following JavaScript versions are [translated and improved from the non-memoizing Nim versions](https://rosettacode.org/wiki/Legendre_prime_counting_function#Non-Memoized_Versions), which explanations can be referenced for an understanding of how they work:
'''The Basic Recursive Legendre Algorithm'''
{{trans|Nim}}
<syntaxhighlight lang="javascript">"use strict";
function countPrimesTo(lmt) {
if (lmt < 3) { if (lmt < 2) return 0; else return 1; }
const sqrtlmt = Math.sqrt(lmt) >>> 0;
const oprms = function() {
const mxndx = (sqrtlmt - 3) >>> 1;
const arr = new Float64Array(mxndx + 1);
for (let i = 0 >>> 0; i <= mxndx; ++i) arr[i] = (i + i + 3) >>> 0;
let bp = 3 >>> 0;
while (true) {
let i = (bp - 3) >>> 1; let sqri = ((i + i) * (i + 3) + 3) >>> 0;
if (sqri > mxndx) break;
if (arr[i] != 0) for (; sqri <= mxndx; sqri += bp) arr[sqri] = 0;
bp += 2;
}
return arr.filter(v => v != 0);
}();
function phi(x, a) {
if (a <= 0) return x - Math.trunc(x / 2);
const na = (a - 1) >>> 0; const p = oprms[na];
if (x <= p) return 1;
return phi(x, na) - phi(Math.trunc(x / p), na);
}
return phi(lmt, oprms.length) + oprms.length;
}
const start = Date.now();
for (let i = 0; i <= 9; ++i) console.log(`π(10**${i}) =`, countPrimesTo(10**i));
const elpsd = Date.now() - start;
console.log("This took", elpsd, "milliseconds.")</syntaxhighlight>
{{out}}
<pre>π(10**0) = 0
π(10**1) = 4
π(10**2) = 25
π(10**3) = 168
π(10**4) = 1229
π(10**5) = 9592
π(10**6) = 78498
π(10**7) = 664579
π(10**8) = 5761455
π(10**9) = 50847534
This took 712 milliseconds.</pre>
The time is as run on an Intel i5-6500 (3.6 GHz single-threaded boost) using node.js version 17.3.1.
Although this is about ten times faster than if it were using memoization (and uses much less memory), it is only reasonably usable for trivial ranges such as this (trivial in terms of prime counting functions).
'''The Less Recursive "Bottom-Up" with a TinyPhi LUT Algorithm'''
Just substitute the following JavaScript code for the `countPrimesTo` function above to enjoy the gain in speed:
{{trans|Nim}}
<syntaxhighlight lang="javascript">const TinyPhiPrimes = [ 2, 3, 5, 7, 11, 13 ];
const TinyPhiOddDegree = TinyPhiPrimes.length - 1;
const TinyPhiOddCirc = TinyPhiPrimes.reduce((acc, p) => acc * p) / 2;
const TinyPhiTot = TinyPhiPrimes.reduce((acc, p) => acc * (p - 1), 1)
const TinyPhiLUT = function() {
const arr = new Uint16Array(TinyPhiOddCirc); arr.fill(1);
for (const p of TinyPhiPrimes) {
if (p <= 2) continue; arr[p >> 1] = 0;
for (let c = (p * p) >> 1; c < TinyPhiOddCirc; c += p) arr[c] = 0 >>> 0; }
for (let i = 0 | 0, acc = 0 | 0; i < TinyPhiOddCirc; ++i) {
acc += arr[i]; arr[i] = acc; }
return arr; }();
function tinyPhi(x) {
const ndx = Math.trunc(( x - 1) / 2);
const numtots = Math.trunc(ndx / TinyPhiOddCirc);
const rem = (ndx - numtots * TinyPhiOddCirc) >>> 0;
return numtots * TinyPhiTot + TinyPhiLUT[rem];
}
function countPrimesTo(lmt) {
if (lmt < 169) {
if (lmt < 3) { if (lmt < 2) return 0; else return 1; }
// adjust for the missing "degree" base primes
if (lmt <= 13) return ((lmt - 1) >>> 1) + (lmt < 9 ? 1 : 0);
return 5 + TinyPhiLUT[(lmt - 1) >>> 1];
}
const sqrtlmt = Math.sqrt(lmt) >>> 0;
const oprms = function() {
const mxndx = (sqrtlmt - 3) >>> 1;
const arr = new Float64Array(mxndx + 1);
for (let i = 0 >>> 0; i <= mxndx; ++i) arr[i] = (i + i + 3) >>> 0;
let bp = 3 >>> 0;
while (true) {
let i = (bp - 3) >>> 1; let sqri = ((i + i) * (i + 3) + 3) >>> 0;
if (sqri > mxndx) break;
if (arr[i] != 0) for (; sqri <= mxndx; sqri += bp) arr[sqri] = 0;
bp += 2;
}
return arr.filter(v => v != 0); }();
function lvl(pilmt, m) {
let ans = 0;
for (let pi = TinyPhiOddDegree; pi < pilmt; ++pi) {
const p = oprms[pi]; const nm = m * p;
if (lmt <= nm * p) return ans + pilmt - pi;
ans += tinyPhi(Math.trunc(lmt / nm));
if (pi > TinyPhiOddDegree) ans -= lvl(pi, nm);
}
return ans;
}
return tinyPhi(lmt) - lvl(oprms.length, 1) + oprms.length;
}</syntaxhighlight>
Use of the above function gets a gain in speed of about a further fifteen times over the above version due to less recursion and the use of the "Tiny_Phi" Look Up Table (LUT) for smaller "degrees" of primes which greatly reduces the number of integer divisions. This version of prime counting function might be considered to be reasonably useful for counting primes up to a trillion (1e12) in a few tens of seconds.
'''The Non-Recursive Partial Sieving Algorithm'''
Just substitute the following JavaScript code for the `countPrimesTo` function above to enjoy the gain in speed:
{{trans|Nim}}
<syntaxhighlight lang="javascript">const masks = new Uint8Array(8); // faster than bit twiddling!
for (let i = 0; i < 8; ++i) masks[i] = (1 << i) >>> 0;
function countPrimesTo(lmt) {
if (lmt < 3) { if (lmt < 2) return 0; else return 1; }
function half(x) { return (x - 1) >>> 1; }
function divide(nm, d) { return (nm / d) >>> 0; }
const sqrtlmt = Math.trunc(Math.sqrt(lmt));
const mxndx = (sqrtlmt - 1) >>> 1; const cbsz = (mxndx + 8) >>> 3;
const cullbuf = new Uint8Array(cbsz);
const smalls = new Uint32Array(mxndx + 1);
for (let i = 0; i <= mxndx; ++i) smalls[i] = i >>> 0;
const roughs = new Uint32Array(mxndx + 1);
for (let i = 0; i <= mxndx; ++i) roughs[i] = (i + i + 1) >>> 0;
const larges = new Float64Array(mxndx + 1);
for (let i = 0; i <= mxndx; ++i) larges[i] =
Math.trunc((Math.trunc(lmt / (i + i + 1)) - 1) / 2);
// partial sieve loop, adjusting larges/smalls, compressing larges/roughs...
let nobps = 0 >>> 0; let rilmt = mxndx; let bp = 3 >>> 0;
while (true) { // break when square root is reached
const i = bp >>> 1; let sqri = ((i + i) * (i + 1)) >>> 0;
if (sqri > mxndx) break; // partial sieving pass if bp is prime:
if ((cullbuf[i >> 3] & masks[i & 7]) == 0) {
cullbuf[i >> 3] |= masks[i & 7]; // cull bp!
for (; sqri <= mxndx; sqri += bp)
cullbuf[sqri >> 3] |= masks[sqri & 7]; // cull bp mults!
// now adjust `larges` for latest partial sieve pass...
var ori = 0 // compress input rough index to output one
for (let iri = 0; iri <= rilmt; ++iri) {
const r = roughs[iri]; const rci = r >>> 1; // skip roughs just culled!
if ((cullbuf[rci >> 3] & masks[rci & 7]) != 0) continue;
const d = bp * r;
larges[ori] = larges[iri] -
( (d <= sqrtlmt) ? larges[smalls[d >>> 1] - nobps]
: smalls[half(divide(lmt, d))] ) +
nobps; // base primes count over subtracted!
roughs[ori++] = r;
}
let si = mxndx // and adjust `smalls` for latest partial sieve pass...
for (let bpm = (sqrtlmt / bp - 1) | 1; bpm >= bp; bpm -= 2) {
const c = smalls[bpm >>> 1] - nobps;
const ei = ((bpm * bp) >>> 1);
while (si >= ei) smalls[si--] -= c;
}
nobps++; rilmt = ori - 1;
}
bp += 2;
}
// combine results to here; correcting for over subtraction in combining...
let ans = larges[0]; for (let i = 1; i <= rilmt; ++i) ans -= larges[i];
ans += Math.trunc((rilmt + 1 + 2 * (nobps - 1)) * rilmt / 2);
// add final adjustment for pairs of current roughs to cube root of range...
let ri = 0
while (true) { // break when reaches cube root of counting range...
const p = roughs[++ri]; const q = Math.trunc(lmt / p);
const ei = smalls[half(divide(q, p))] - nobps;
if (ei <= ri) break; // break here when no more pairs!
for (let ori = ri + 1; ori <= ei; ++ori)
ans += smalls[half(divide(q, roughs[ori]))];
ans -= (ei - ri) * (nobps + ri - 1);
}
return ans + 1; // add one for only even prime of two!
}</syntaxhighlight>
The above code enjoys quite a large gain in speed of about a further ten times (and increasing with range) over the immediately preceding version for larger "non-trivial" ranges (since there is an appreciable environment overhead in initialization and JIT compilation) due to not using recursion at all and the greatly reduced computational complexity of O(n**(3/4)/((log n)**2)) instead of the almost-linear-for-large-counting-ranges O(n/((log n)**2)) for the previous two versions, although the previous two versions differ in performance by a constant factor due to the overheads of recursion and division; for instance, this version can calculate the number of primes to 1e11 in about 125 milliseconds. This version of prime counting function might be considered to be reasonably useful for counting primes up to a 1e16 in under three minutes as long as the computer used has the required free memory of about 800 Megabytes. This JavaScript version is about three times as slow as the Nim version from which it was translated for large ranges where the initialization overhead is not significant due to being run by the JavaScript engine and JIT compiled.
=={{header|jq}}==
| |||