Legendre prime counting function: Difference between revisions

<br>

<br>

 

=={{header|C++}}==

 

The above function enjoys quite a large gain in speed of about a further ten times over the immediately preceding version 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. This version of prime counting function might be considered to be reasonably useful for counting primes up to a 1e16 in almost two minutes as long as the computer used has the required free memory of about 800 Megabytes. This Crystal version is about twice as slow as the Nim version from which it was translated because Nim's default GCC back-end is better at optimization (at least for this algorithm) than the LLVM back-end used by Crystal and also there is more numeric calculation checking such as numeric overflow used in Crystal that can't be turned off. At that, this version is about the same speed as when translated to Rust, which also uses a LLVM back-end.

 

=={{header|Erlang}}==

The above time as run on an Intel i5-6500 (3.6 GHz single-threaded boost) isn't particularly fast but includes some DotNet initialization and JIT compilation overhead, and is about as fast as a highly optimized page-segmented wheel-factorized Sieve of Eratosthenes; 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).

 

 

Just substitute the following F# code for the `countPrimes` function above to enjoy the gain in speed:

'''The Non-Recursive Partial Sieving Algorithm'''

 

{{trans|Nim}}

<syntaxhighlight lang="fsharp">let masks = Array.init 8 ((<<<) 1uy) // quick bit twiddling

 

The above function enjoys quite a large gain in speed of about a further ten times over the immediately preceding version (although one can't see that gain for these trivial ranges as it is buried in the constant overheads) 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 a hundred milliseconds. This version of prime counting function might be considered to be reasonably useful for counting primes up to a 1e16 in about a hundred seconds as long as the computer used has the required free memory of about 800 Megabytes. This F# version is about twice as slow as the Nim version from which it was translated due to the benefits of native code compilation and more optimizations for Nim rather than JIT compilation for F#. At that, this version is about the same speed as when translated to Rust and Crystal once the range is increased where constant overheads aren't a factor, which both use native code compilers.

 

=={{header|Go}}==

Same as first version.

</pre>

 

 

 

 

 

}

}

}

}

}

}</syntaxhighlight>

 

{{out}}

<pre>

</pre>

 

'''The Non-Recursive Partial Sieving Algorithm'''

 

if n < 3 then (if n < 2 then 0 else 1) else

let

 

But we can simplify that to p:inv when we know that primes are not being tested.

 

=={{header|jq}}==

0.003234 seconds (421 allocations: 14.547 KiB)

</pre>

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

5761455

50847534</pre>

 

=={{header|Nim}}==

for i in 0..9:

echo "π(10^$1) = $2".format(i, π(n))

 

{{out}}

 

As counting range is increased above these trivial ranges, a better algorithm such as that of LMO will likely perform much better than this and use much less memory (to proportional to the cube root of the range), although at the cost of greater code complexity and more lines of code (about 500 LOC). The trade-off between algorithms of the Legendre type and those of the Meissel type is that the latter decreases the time complexity but at the cost of more time spent sieving; modern follow-on work to LMO produces algorithms which are able to tune the balance between Legendre-type and Meissel-type algorithm in trading off the execution time costs between the different parts of the given algorithm for the best in performance, with the latest in Kim Walisch's tuning of Xavier Gourdon's work being about five to ten times faster than LMO (plus includes multi-threading abilities).

 

=={{header|Perl}}==

</pre>

<small>(It is about 4 times slower under pwa/p2js so output is limited to 10^8, unless you like staring at a blank screen for 52s)</small>

 

=={{header|Picat}}==

</pre>

 

=={{header|Sidef}}==

<syntaxhighlight lang="ruby">func legendre_phi(x, a) is cached {

 

[inline]

[inline] // floating point divide faster than integer divide!

 

[direct_array_access]

fn count_primes_to(n u64) i64 {

mut smalls := []u32{ len: arrlen, cap: arrlen, init: u32(it) }

mut roughs := []u32{ len: arrlen, cap: arrlen, init: u32(it + it + 1) }

mut larges := []i64{ len: arrlen, cap: arrlen,

init: i64(((n / u64(it + it + 1) - 1) / 2)) }

mut cullbuf := []u8{len: cullbuflen, cap: cullbuflen, init: u8(0)}

 

mut rilmt := arrlen // number of roughs start with full size!

sqri := (i + i) * (i + 1)

if sqri > mxndx { break } // breaks here!

 

mut nri := 0 // transfer from `ori` to `nri` indexes:

for ori in 0 .. rilmt { // update `roughs` and `larges` for partial sieve...

larges[nri] = larges[ori] -

nri++ // advance output `roughs` index!

}

mut si := mxndx // update `smalls` for partial sieve...

for pm := ((rtlmt / bp) - 1) | 1; pm >= bp; pm -= 2 {

for ; si >= e; si-- { smalls[si] -= (c - u32(nbps)) }

}

p := u64(roughs[ri])

m := n / p

if ei <= ri { break } // break out when only multiple equal to `p`

ans -= i64((ei - ri) * (nbps + ri - 1)) // adjust for over addition below!

This took 2 milliseconds.</pre>

 

 

=={{header|Wren}}==

 

To sieve a billion numbers and then count the primes up to 10^k would take about 53 seconds in Wren so, as expected, the Legendre method represents a considerable speed up.

 

var pi = Fn.new { |n|

 

The memoized version requires a cache of around 6.5 million map entries, which at 8 bytes each (all numbers are 64 bit floats in Wren) for both the key and the value, equates in round figures to memory usage of 104 MB on top of that needed for the prime sieve. The following version strips out memoization and, whilst somewhat slower at 5.4 seconds, may be preferred in a constrained memory environment.

 

var pi = Fn.new { |n|

{{trans|Vlang}}

This non-memoized, non-recursive version is far quicker than the first two versions, running in about 114 milliseconds. Nowhere near as quick as V, of course, but acceptable for Wren which is interpreted and only has one built-in numeric type, a 64 bit float.

 

var masks = [1, 2, 4, 8, 16, 32, 64, 128]

 

var countPrimes = Fn.new { |n|

var rtlmt = n.sqrt.floor

var mxndx = Int.quo(rtlmt - 1, 2)

var nri = 0

for (ori in 0...rilmt) {

var t = (d <= rtlmt) ? larges[smalls[d >> 1] - nbps] :

smalls[half.call(Int.quo(n, d))]

larges[nri] = larges[ori] - t + nbps

nri = nri + 1

}