Databases
StackOverflow2013
Postsdbo
POGetting functional sieve of Eratosthenes fast
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POGetting functional sieve of Eratosthenes fast
    primarykey
    data
    text
    <p>I read <a href="https://stackoverflow.com/questions/2325914/haskell-f-turners-sieve/5702990">this other post about a F# version of this algorithm</a>. I found it very elegant and tried to combine some ideas of the answers.</p> <p>Although I optimized it to make fewer checks (check only numbers around 6) and leave out unnecessary caching, it is still painfully slow. Calculating the 10,000<sup>th</sup> prime already take more than 5 minutes. Using the imperative approach, I can test all 31-bit integers in not that much more time.</p> <p>So my question is if I am missing something that makes all this so slow. For example in <a href="https://stackoverflow.com/questions/4629734/the-sieve-of-eratosthenes-in-f">another post</a> someone was speculating that <code>LazyList</code> may use locking. Does anyone have an idea?</p> <p>As StackOverflow's rules say not to post new questions as answers, I feel I have to start a new topic for this.</p> <p>Here's the code:</p> <pre><code>#r "FSharp.PowerPack.dll" open Microsoft.FSharp.Collections let squareLimit = System.Int32.MaxValue |&gt; float32 |&gt; sqrt |&gt; int let around6 = LazyList.unfold (fun (candidate, (plus, next)) -&gt; if candidate &gt; System.Int32.MaxValue - plus then None else Some(candidate, (candidate + plus, (next, plus))) ) (5, (2, 4)) let (|SeqCons|SeqNil|) s = if Seq.isEmpty s then SeqNil else SeqCons(Seq.head s, Seq.skip 1 s) let rec lazyDifference l1 l2 = if Seq.isEmpty l2 then l1 else match l1, l2 with | LazyList.Cons(x, xs), SeqCons(y, ys) -&gt; if x &lt; y then LazyList.consDelayed x (fun () -&gt; lazyDifference xs l2) elif x = y then lazyDifference xs ys else lazyDifference l1 ys | _ -&gt; LazyList.empty let lazyPrimes = let rec loop = function | LazyList.Cons(p, xs) as ll -&gt; if p &gt; squareLimit then ll else let increment = p &lt;&lt;&lt; 1 let square = p * p let remaining = lazyDifference xs {square..increment..System.Int32.MaxValue} LazyList.consDelayed p (fun () -&gt; loop remaining) | _ -&gt; LazyList.empty loop (LazyList.cons 2 (LazyList.cons 3 around6)) </code></pre>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USCommunity
    1. USprimfaktor
    plurals
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    3. PL
      singulars
      1. LTLinked
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POGetting functional sieve of Eratosthenes fast
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POGetting functional sieve of Eratosthenes fast
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POGetting functional sieve of Eratosthenes fast
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThe slowness is in your `(|SeqCons|SeqNil|)` active pattern, which takes about O(n^2) time. I don't think there's a way to pattern match on sequences, so you're probably better converting it to a LazyList instead. See brian's awesome answer here: http://stackoverflow.com/questions/1306140/f-why-is-using-a-sequence-so-much-slower-than-using-a-list-in-this-example/1306267#1306267
      singulars
      1. POGetting functional sieve of Eratosthenes fast
      1. USJuliet
    2. COYou might find this of interest. http://stackoverflow.com/questions/4629734/the-sieve-of-eratosthenes-in-f/4631738#4631738
      singulars
      1. POGetting functional sieve of Eratosthenes fast
      1. USgradbot
    3. COObjectively, this is an unsolved problem. There is no known way to implement a competitively-efficient pure Sieve of Eratosthenes. You can optimize it a bit but you will never approach the performance of an imperative solution, so it is an academic exercise. If you want to write fast code to solve these kinds of problems, you must embrace impurity. Moreover, I believe the performance gap between pure and impure will never be closed because purity abstracts away precisely the information you need in order to write fast code.
      singulars
      1. POGetting functional sieve of Eratosthenes fast
      1. USJon Harrop
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload