<br><br><div><span class="gmail_quote">On 7/15/07, <b class="gmail_sendername">Donald Bruce Stewart</b> &lt;<a href="mailto:dons@cse.unsw.edu.au">dons@cse.unsw.edu.au</a>&gt; wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Oh, and I forgot you count up by two now. Here&#39;s the Haskell<br>transliteration (again).<br><br><br>&nbsp;&nbsp;&nbsp;&nbsp;{-# OPTIONS -O2 -optc-O -fbang-patterns #-}<br><br>&nbsp;&nbsp;&nbsp;&nbsp;import <a href="http://Control.Monad.ST">Control.Monad.ST</a>
<br>&nbsp;&nbsp;&nbsp;&nbsp;import <a href="http://Data.Array.ST">Data.Array.ST</a><br>&nbsp;&nbsp;&nbsp;&nbsp;import Data.Array.Base<br>&nbsp;&nbsp;&nbsp;&nbsp;import System<br>&nbsp;&nbsp;&nbsp;&nbsp;import Control.Monad<br>&nbsp;&nbsp;&nbsp;&nbsp;import Data.Bits<br><br>&nbsp;&nbsp;&nbsp;&nbsp;main = print (pureSieve 10000000)<br><br>&nbsp;&nbsp;&nbsp;&nbsp;pureSieve :: Int -&gt; Int
<br>&nbsp;&nbsp;&nbsp;&nbsp;pureSieve n = runST( sieve n )<br><br>&nbsp;&nbsp;&nbsp;&nbsp;sieve n = do<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a &lt;- newArray (3,n) True :: ST s (STUArray s Int Bool)<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;let cutoff = truncate (sqrt (fromIntegral n)) + 1<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;go a n cutoff 3 1
<br><br>&nbsp;&nbsp;&nbsp;&nbsp;go !a !m cutoff !n !c<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;| n &gt;= m&nbsp;&nbsp;&nbsp;&nbsp;= return c<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;| otherwise = do<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;e &lt;- unsafeRead a n<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if e then<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if n &lt; cutoff<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;then let loop !j
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;| j &lt; m&nbsp;&nbsp;&nbsp;&nbsp; = do<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x &lt;- unsafeRead a j<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;when x $ unsafeWrite a j False<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;loop (j+n)
<br><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;| otherwise = go a m cutoff (n+2) (c+1)<br><br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;in loop ( if n &lt; 46340 then n * n else n `shiftL` 1)<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else go a m cutoff (n+2) (c+1)<br>
<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; else go a m cutoff (n+2) c<br><br><br>Marginally faster:<br><br>&nbsp;&nbsp;&nbsp;&nbsp;$ time ./primes<br>&nbsp;&nbsp;&nbsp;&nbsp;664579<br>&nbsp;&nbsp;&nbsp;&nbsp;./primes&nbsp;&nbsp;0.34s user 0.00s system 89% cpu 0.385 total<br><br>Very cache-dependent though, so widely varying runtimes could be
<br>expected.<br><br>-- Don<br></blockquote></div><br>Hi Donald, quick question.&nbsp; So, one of the things that is very interesting about Haskell is it&#39;s potential for automatic threading, ie you write a trivial algorithm that looks like it runs in a single thread, and the runtime splits it across multiple cores automatically.
<br><br>It&#39;s fairly safe to say that maps, foldrs, foldls, and their derivatives are safe to parallelize?&nbsp; (For example, hand-waving argument, a foldr of (/) on [1,5,7,435,46,2] can be split into a foldr on [1,5,7] and a foldr on [435,46,2], then their results combined).
<br><br>To what extent is the technology you are using in your algorithm parallizable?&nbsp; (I actually cant tell, it&#39;s a genuine question).&nbsp; In the case that it is parallelizable, to what extent is it trivial for a runtime to know this?&nbsp; (Again, I dont have enough information to tell)
<br><br>