Legendre prime counting function: Difference between revisions
Content added Content deleted
GordonBGood (talk | contribs) (→Non-Memoized Version: Add an even faster version by reducing recursion...) |
(→{{header|Wren}}: Added a non-memoized version.) |
||
| Line 1,274: | Line 1,274: | ||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
{{libheader|Wren-math}} |
{{libheader|Wren-math}} |
||
===Memoized=== |
|||
This runs in about 5.7 seconds which is not too bad for the Wren interpreter. As map keys cannot be lists, the Cantor pairing function has been used to represent [x, a] which is considerably faster than using a string based approach for memoization. |
This runs in about 5.7 seconds which is not too bad for the Wren interpreter. As map keys cannot be lists, the Cantor pairing function has been used to represent [x, a] which is considerably faster than using a string based approach for memoization. |
||
| Line 1,317: | Line 1,318: | ||
10^8 5761455 |
10^8 5761455 |
||
10^9 50847534 |
10^9 50847534 |
||
</pre> |
|||
===Non-memoized=== |
|||
Inspired by the non-memoized Nim version. |
|||
Marginally quicker (5.4 seconds) than the memoized version and, of course, uses less memory. |
|||
<syntaxhighlight lang="ecmascript">import "./math" for Int |
|||
var pi = Fn.new { |n| |
|||
if (n < 3) return (n < 2) ? 0 : 1 |
|||
var primes = Int.primeSieve(n.sqrt.floor) |
|||
var a = primes.count |
|||
var phi // recursive closure |
|||
phi = Fn.new { |x, a| |
|||
if (a <= 1) return (a < 1) ? x : x - (x >> 1) |
|||
var pa = primes[a-1] |
|||
if (x <= pa) return 1 |
|||
return phi.call(x, a-1) - phi.call((x/pa).floor, a-1) |
|||
} |
|||
return phi.call(n, a) + a - 1 |
|||
} |
|||
var n = 1 |
|||
for (i in 0..9) { |
|||
System.print("10^%(i) %(pi.call(n))") |
|||
n = n * 10 |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Same as first version. |
|||
</pre> |
</pre> |
||