Sieve of Eratosthenes: Difference between revisions
→{{header|Elm}}: reorganize, add concise timed Array versions...
(Improve sieving) |
GordonBGood (talk | contribs) (→{{header|Elm}}: reorganize, add concise timed Array versions...) |
||
Line 6,450:
=={{header|Elm}}==
===Elm with immutable arrays===
Line 6,845 ⟶ 6,616:
[ 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 ]
Found 35 primes </pre>
===Concise Elm Immutable Array Version===
Although functional, the above code is written in quite an imperative style, so the following code is written in a more concise functional style and includes timing information for counting the number of primes to a million:
<syntaxhighlight lang="elm">module Main exposing (main)
import Browser exposing (element)
import Task exposing (Task, succeed, perform, andThen)
import Html exposing (Html, div, text)
import Time exposing (now, posixToMillis)
import Array exposing (repeat, get, set)
cLIMIT : Int
cLIMIT = 1000000
primesArray : Int -> List Int
primesArray n =
if n < 2 then [] else
let
sz = n + 1
loopbp bp arr =
let s = bp * bp in
if s >= sz then arr else
let tst = get bp arr |> Maybe.withDefault True in
if tst then loopbp (bp + 1) arr else
let
cullc c iarr =
if c >= sz then iarr else
cullc (c + bp) (set c True iarr)
in loopbp (bp + 1) (cullc s arr)
cmpsts = loopbp 2 (repeat sz False)
cnvt (i, t) = if t then Nothing else Just i
in cmpsts |> Array.toIndexedList
|> List.drop 2 -- skip the values for zero and one
|> List.filterMap cnvt -- primes are indexes of not composites
type alias Model = List String
type alias Msg = Model
test : (Int -> List Int) -> Int -> Cmd Msg
test primesf lmt =
let
to100 = primesf 100 |> List.map String.fromInt |> String.join ", "
to100str = "The primes to 100 are: " ++ to100
timemillis() = now |> andThen (succeed << posixToMillis)
in timemillis() |> andThen (\ strt ->
let cnt = primesf lmt |> List.length
in timemillis() |> andThen (\ stop ->
let answrstr = "Found " ++ (String.fromInt cnt) ++ " primes to "
++ (String.fromInt cLIMIT) ++ " in "
++ (String.fromInt (stop - strt)) ++ " milliseconds."
in succeed [to100str, answrstr] ) ) |> perform identity
main : Program () Model Msg
main =
element { init = \ _ -> ( [], test primesArray cLIMIT )
, update = \ msg _ -> (msg, Cmd.none)
, subscriptions = \ _ -> Sub.none
, view = div [] << List.map (div [] << List.singleton << text) }</syntaxhighlight>
{{out}}
<pre>The primes up to 100 are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.
Found 78498 primes to 1000000 in 958 milliseconds.</pre>
The above output is the contents of the HTML web page as shown with Google Chrome version 1.23 running on an AMD 7840HS CPU at 5.1 GHz (single thread boosted).
===Concise Elm Immutable Array Odds-Only Version===
The following code can replace the `primesArray` function in the above program and called from the testing and display code (two places):
<syntaxhighlight lang="elm">primesArrayOdds : Int -> List Int
primesArrayOdds n =
if n < 2 then [] else
let
sz = (n - 1) // 2
loopi i arr =
let s = (i + i) * (i + 3) + 3 in
if s >= sz then arr else
let tst = get i arr |> Maybe.withDefault True in
if tst then loopi (i + 1) arr else
let
bp = i + i + 3
cullc c iarr =
if c >= sz then iarr else
cullc (c + bp) (set c True iarr)
in loopi (i + 1) (cullc s arr)
cmpsts = loopi 0 (repeat sz False)
cnvt (i, t) = if t then Nothing else Just <| i + i + 3
oddprms = cmpsts |> Array.toIndexedList |> List.filterMap cnvt
in 2 :: oddprms</syntaxhighlight>
{{out}}
<pre>The primes up to 100 are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.
Found 78498 primes to 1000000 in 371 milliseconds.</pre>
The above output is the contents of the HTML web page as shown with Google Chrome version 1.23 running on an AMD 7840HS CPU at 5.1 GHz (single thread boosted).
===Richard Bird Tree Folding Elm Version===
The Elm language doesn't efficiently handle the Sieve of Eratosthenes (SoE) algorithm because it doesn't have directly accessible linear arrays (the Array module used above is based on a persistent tree of sub arrays) and also does Copy On Write (COW) for every write to every location as well as a logarithmic process of updating as a "tree" to minimize the COW operations. Thus, there is better performance implementing the Richard Bird Tree Folding functional algorithm, as follows:
{{trans|Haskell}}
<syntaxhighlight lang="elm">module Main exposing (main)
import Browser exposing (element)
import Task exposing (Task, succeed, perform, andThen)
import Html exposing (Html, div, text)
import Time exposing (now, posixToMillis)
cLIMIT : Int
cLIMIT = 1000000
type CIS a = CIS a (() -> CIS a)
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 []
countCISTo : comparable -> CIS comparable -> Int
countCISTo n cis =
let loop (CIS hd tl) cnt =
if hd > n then cnt else loop (tl()) (cnt + 1)
in loop cis 0
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()
type alias Model = List String
type alias Msg = Model
test : (() -> CIS Int) -> Int -> Cmd Msg
test primesf lmt =
let
to100 = primesf() |> uptoCIS2List 100
|> List.map String.fromInt |> String.join ", "
to100str = "The primes to 100 are: " ++ to100
timemillis() = now |> andThen (succeed << posixToMillis)
in timemillis() |> andThen (\ strt ->
let cnt = primesf() |> countCISTo lmt
in timemillis() |> andThen (\ stop ->
let answrstr = "Found " ++ (String.fromInt cnt) ++ " primes to "
++ (String.fromInt cLIMIT) ++ " in "
++ (String.fromInt (stop - strt)) ++ " milliseconds."
in succeed [to100str, answrstr] ) ) |> perform identity
main : Program () Model Msg
main =
element { init = \ _ -> ( [], test primesTreeFolding cLIMIT )
, update = \ msg _ -> (msg, Cmd.none)
, subscriptions = \ _ -> Sub.none
, view = div [] << List.map (div [] << List.singleton << text) }</syntaxhighlight>
{{out}}
<pre>The primes up to 100 are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.
Found 78498 primes to 1000000 in 201 milliseconds.</pre>
The above output is the contents of the HTML web page as shown with Google Chrome version 1.23 running on an AMD 7840HS CPU at 5.1 GHz (single thread boosted).
===Elm Priority Queue Version===
Using a Binary Minimum Heap Priority Queue is a constant factor faster than the above code as the data structure is balanced rather than "heavy to the right" and requires less memory allocations/deallocation in the following code, which implements enough of the Priority Queue for the purpose. Just substitute the following code for `primesTreeFolding` and pass `primesPQ` as an argument to `test` rather than `primesTreeFolding`:
<syntaxhighlight lang="elm">type PriorityQ comparable v =
Mt
| Br comparable v (PriorityQ comparable v)
(PriorityQ comparable v)
emptyPQ : PriorityQ comparable v
emptyPQ = Mt
peekMinPQ : PriorityQ comparable v -> Maybe (comparable, v)
peekMinPQ pq = case pq of
(Br k v _ _) -> Just (k, v)
Mt -> Nothing
pushPQ : comparable -> v -> PriorityQ comparable v
-> PriorityQ comparable v
pushPQ wk wv pq =
case pq of
Mt -> Br wk wv Mt Mt
(Br vk vv pl pr) ->
if wk <= vk then Br wk wv (pushPQ vk vv pr) pl
else Br vk vv (pushPQ wk wv pr) pl
siftdown : comparable -> v -> PriorityQ comparable v
-> PriorityQ comparable v -> PriorityQ comparable v
siftdown wk wv pql pqr =
case pql of
Mt -> Br wk wv Mt Mt
(Br vkl vvl pll prl) ->
case pqr of
Mt -> if wk <= vkl then Br wk wv pql Mt
else Br vkl vvl (Br wk wv Mt Mt) Mt
(Br vkr vvr plr prr) ->
if wk <= vkl && wk <= vkr then Br wk wv pql pqr
else if vkl <= vkr then Br vkl vvl (siftdown wk wv pll prl) pqr
else Br vkr vvr pql (siftdown wk wv plr prr)
replaceMinPQ : comparable -> v -> PriorityQ comparable v
-> PriorityQ comparable v
replaceMinPQ wk wv pq = case pq of
Mt -> Mt
(Br _ _ pl pr) -> siftdown wk wv pl pr
primesPQ : () -> CIS Int
primesPQ() =
let
sieve n pq q (CIS bp bptl as bps) =
if n >= q then
let adv = bp + bp in let (CIS nbp _ as nbps) = bptl()
in sieve (n + 2) (pushPQ (q + adv) adv pq) (nbp * nbp) nbps
else let
(nxtc, _) = peekMinPQ pq |> Maybe.withDefault (q, 0) -- default when empty
adjust tpq =
let (c, adv) = peekMinPQ tpq |> Maybe.withDefault (0, 0)
in if c > n then tpq
else adjust (replaceMinPQ (c + adv) adv tpq)
in if n >= nxtc then sieve (n + 2) (adjust pq) q bps
else CIS n <| \ () -> sieve (n + 2) pq q bps
oddprms() = CIS 3 <| \ () -> sieve 5 emptyPQ 9 <| oddprms()
in CIS 2 <| \ () -> oddprms()</syntaxhighlight>
{{out}}
<pre>The primes up to 100 are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.
Found 78498 primes to 1000000 in 124 milliseconds.</pre>
The above output is the contents of the HTML web page as shown with Google Chrome version 1.23 running on an AMD 7840HS CPU at 5.1 GHz (single thread boosted).
=={{header|Emacs Lisp}}==
| |||