Legendre prime counting function: Difference between revisions

Line 1,497:

===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 4.5 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.

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

<syntaxhighlight lang="ecmascript">import "./math" for Int

var ~~limit~~ = ~~1e9~~.~~sqrt.floor~~

var pi = Fn.new { |n|

⚫

if (n < 3) return (n < 2) ? 0 : 1

var primes = Int.primeSieve(~~limit~~)

var primes = Int.primeSieve(n.sqrt.floor)

⚫

var memoPhi = {}

var a = primes.count

⚫

var memoPhi = {}

var phi // recursive ~~function~~

var phi // recursive closure

phi = Fn.new { |x, a|

if (a == 0) return x

if (a <= 1) return (a < 1) ? x : x - (x >> 1)

var ~~key~~ = ~~Int.cantorPair(x,~~ a)

var pa = primes[a-1]

if (~~memoPhi.containsKey(key)~~) return ~~memoPhi[key]~~

if (x <= pa) return 1

var pa = ~~primes[~~a~~-1]~~

var key = Int.cantorPair(x, a)

if (memoPhi.containsKey(key)) return memoPhi[key]

return memoPhi[key] = phi.call(x, a-1) - phi.call((x/pa).floor, a-1)

}

var pi // recursive function

pi = Fn.new { |n|

⚫

if (n < 2) return 0

var a = pi.call(n.sqrt.floor)

return phi.call(n, a) + a - 1

}

Line 1,544:

Line 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.

Marginally quicker (5.4 seconds) than the memoized version and, of course, uses less memory.

<syntaxhighlight lang="ecmascript">import "./math" for Int