Legendre prime counting function: Difference between revisions
→{{header|Erlang}}: add Elm contribution above...
(→{{header|Ruby}}: Add Ruby) |
GordonBGood (talk | contribs) (→{{header|Erlang}}: add Elm contribution above...) |
||
Line 804:
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|Elm}}==
Currently, Elm does not have linear arrays and has no mutation whatsoever, even array content mutation protected by "monadic function chains" as for Haskell, so many algorithms can't be easily implemented such as the Legendre Partial Sieving algorithm which requires random access to linear arrays whose contents are mutated according to previous passes. However, given a prime number generator based on persistent data structures such as the List version [[https://rosettacode.org/wiki/Sieve_of_Eratosthenes#Elm|from the Sieve of Eratosthenes task page]], one can translate the algorithm of the "bottom-up" recursive version without the "TinyPhi" Look Up Table (LUT) optmization which would need a linear array to implement, as in the following code:
<syntaxhighlight lang="elm">module Main exposing (main)
import Browser exposing (element)
import Task exposing (Task, succeed, perform, andThen)
import Html exposing (div, text)
import Time exposing (now, posixToMillis)
type CIS a = CIS a (() -> CIS a) -- infinite Co-Inductive Stream...
uptoCIS2List : comparable -> CIS comparable -> List comparable
uptoCIS2List n cis =
let loop (CIS hd tl) lst =
if hd > n then List.reverse lst
else loop (tl()) (hd :: lst)
in loop cis []
-- require a range of primes by Sieve of Eratosthenes...
primesTreeFolding : () -> CIS Int
primesTreeFolding() =
let
merge (CIS x xtl as xs) (CIS y ytl as ys) =
case compare x y of
LT -> CIS x <| \ () -> merge (xtl()) ys
EQ -> CIS x <| \ () -> merge (xtl()) (ytl())
GT -> CIS y <| \ () -> merge xs (ytl())
pmult bp =
let adv = bp + bp
pmlt p = CIS p <| \ () -> pmlt (p + adv)
in pmlt (bp * bp)
allmlts (CIS bp bptl) =
CIS (pmult bp) <| \ () -> allmlts (bptl())
pairs (CIS frst tls) =
let (CIS scnd tlss) = tls()
in CIS (merge frst scnd) <| \ () -> pairs (tlss())
cmpsts (CIS (CIS hd tl) tls) =
CIS hd <| \ () -> merge (tl()) <| cmpsts <| pairs (tls())
testprm n (CIS hd tl as cs) =
if n < hd then CIS n <| \ () -> testprm (n + 2) cs
else testprm (n + 2) (tl())
oddprms() =
CIS 3 <| \ () -> testprm 5 <| cmpsts <| allmlts <| oddprms()
in CIS 2 <| \ () -> oddprms()
countPrimesTo : Float -> Float -- only use integral values!
countPrimesTo n =
if n < 3 then if n < 2 then 0 else 1 else
let nnf = toFloat (floor n) -- erase fractional part!
sqrtn = sqrt nnf |> truncate
oprms = primesTreeFolding() |> uptoCIS2List sqrtn |> List.drop 1
opsz = List.length oprms
lvl opi opilmt plst m acc =
if opi >= opilmt then acc else
case plst of
[] -> acc -- should never happen
(op :: optl) ->
let opl = toFloat op
nm = m * opl in
if nnf <= nm * opl then acc + toFloat (opilmt - opi) else
let q = nnf / nm |> floor |> toFloat
nacc = acc + q - toFloat (floor (q / 2))
sacc = if opi <= 0 then 0 else lvl 0 opi oprms nm 0
in lvl (opi + 1) opilmt optl m (nacc - sacc)
in nnf - toFloat (floor (nnf / 2)) - lvl 0 opsz oprms 1 0 + toFloat opsz
-- run the required task tests...
timemillis : () -> Task Never Int -- a side effect function
timemillis() = now |> andThen (\ t -> succeed (posixToMillis t))
test : () -> Cmd Msg -- side effect function chain (includes "perform")...
test() =
timemillis()
|> andThen (\ strt ->
let rsltstrs = List.range 0 9 |> List.map ( \ n ->
"π(10^" ++ String.fromInt n ++ ") = " ++
String.fromFloat (countPrimesTo (toFloat (10^n))))
in timemillis()
|> andThen (\ stop ->
succeed (List.append rsltstrs ["This took "
++ String.fromInt (stop - strt)
++ " milliseconds."])))
|> perform Done
-- following code has to do with outputting to a web page using MUV/TEA...
type alias Model = List String
type Msg = Done Model
main : Program () Model Msg
main = -- starts with empty list of strings; views model of filled list...
element { init = \ _ -> ( [], test() )
, update = \ (Done mdl) _ -> ( mdl , Cmd.none )
, subscriptions = \ _ -> Sub.none
, view = div [] << List.map (div [] << List.singleton << text) }</syntaxhighlight>
{{out}}
<pre>π(10^0) = 0
π(10^1) = 4
π(10^2) = 25
π(10^3) = 168
π(10^4) = 1229
π(10^5) = 9592
π(10^6) = 78498
π(10^7) = 664579
π(10^8) = 5761455
π(10^9) = 50847534
This took 341 milliseconds.</pre>
=={{header|Erlang}}==
| |||