Legendre prime counting function: Difference between revisions
→{{header|Wren}}: Impoved 'memoization' version.
GordonBGood (talk | contribs) (→Non-Memoized Version: Nim - add partial sieving version for less computational complexity...) |
(→{{header|Wren}}: Impoved 'memoization' version.) |
||
Line 1,497:
{{libheader|Wren-math}}
===Memoized===
This runs in about
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.
<syntaxhighlight lang="ecmascript">import "./math" for Int
var
var primes = Int.primeSieve(
var memoPhi = {}▼
var a = primes.count
▲ var memoPhi = {}
var phi // recursive
phi = Fn.new { |x, a|
if (a
var
if (
var
if (memoPhi.containsKey(key)) return memoPhi[key]
return memoPhi[key] = phi.call(x, a-1) - phi.call((x/pa).floor, a-1)
}
▲ if (n < 2) return 0
return phi.call(n, a) + a - 1
}
Line 1,544 ⟶ 1,543:
Inspired by the non-memoized Nim version.
The memoized version requires a cache of around 6.5 million numbers, which at 8 bytes each (all numbers are 64 bit floats in Wren), equates in round figures to memory usage of 52 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.
<syntaxhighlight lang="ecmascript">import "./math" for Int
| |||