(phixonline)-->
with javascript_semantics
--
-- While a phix dictionary can handle keys of {x,a}, for this
-- task performance was dreadful (7,612,479 entries, >3mins),
-- so instead memophix maps known x to an index to memophia
-- which holds the full [1..a] for each x, dropping to a much
-- more respectable (albeit not super-fast) 14s
--
constant memophix = new_dict()
sequence memophia = {} -- 1..a (max 3401) for each x
function phi(integer x, a)
if a=0 then return x end if
integer adx = getd(x,memophix), res
if adx=NULL then
memophia = append(memophia,repeat(-1,a))
adx = length(memophia)
setd(x,adx,memophix)
else
object ma = memophia[adx]
integer l = length(ma)
if a>l then
memophia[adx] = 0 -- kill refcount
memophia[adx] = ma & repeat(-1,a-l)
else
res = ma[a]
if res>=0 then return res end if
end if
ma = 0 -- kill refcount
end if
res = phi(x, a-1) - phi(floor(x/get_prime(a)), a-1)
memophia[adx][a] = res
return res
end function
function pi(integer n)
if n<2 then return 0 end if
integer a = pi(floor(sqrt(n)))
return phi(n, a) + a - 1
end function
atom t0 = time()
for i=0 to iff(platform()=JS?8:9) do
printf(1,"10^%d %d\n",{i,pi(power(10,i))})
-- printf(1,"10^%d %d\n",{i,length(get_primes_le(power(10,i)))})
end for
?elapsed(time()-t0)