Shootout/Nsieve Bits
< Shootout
Jump to navigation
Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
A ShootoutEntry for the nsieve-bits problem.
Each program should count the prime numbers from 2 to M, using the same na�ve Sieve of Eratosthenes algorithm:
- create an array of M bit flags
- for each index number
- if the flag value at that index is true
j** set all the flag values at multiples of that index false
- increment the count
Calculate 3 prime counts, for M = 2N � 10000, 2N-1 � 10000, and 2N-2 � 10000.
Benchmarks
Linux/x86, N=10
|| Entry || Time || || Fast 3 || 0.656 || || Fast 2 || 0.720 || || Fast 1 || 1.028 || || Original|| 1.031 ||
(Proposed) Fast 3 entry
Careful attention to strictness ensures all args are unboxed (taking the idea from the NsieveEntry). Squeezes another 10%. This should be the 2nd or 3rd fastest entry overall -- finally beating OCaml, D and SML :)
--
-- The Great Computer Language Shootout
-- http://shootout.alioth.debian.org/
--
-- Haskell Shootout entries - http://haskell.org/hawiki/ShootoutEntry
-- Contributed by (c) Simon Marlow 2005
-- Modified by Don Stewart
--
import Data.Bits; import Data.Array.IO; import Data.Array.Base
import System; import IO; import Text.Printf
main = (\n -> mapM_ (sieve . shiftL 10000 . (-) n) [0..2]) . read . head =<< getArgs
sieve m = do r <- newArray (0,m) False >>= \(a::IOUArray Int Bool) -> for a m 2 0
printf "Primes up to %8d %8d\n" (m::Int) (r::Int)
for arr m i c | arr `seq` m `seq` i `seq` c `seq` False = undefined -- strict
for arr m i c = if i > m then return c else do
x <- unsafeRead arr i
if x then for arr m (i+1) c
else let for' j | j > m = for arr m (i+1) (c+1)
| otherwise = unsafeWrite arr j True >> for' (j+i)
in for' (i*2)
Fast 2 entry
Short, and uses unsafe reads for realistic speed Use -O2 -optc-O3.
--
-- The Great Computer Language Shootout
-- http://shootout.alioth.debian.org/
-- Contributed by (c) Simon Marlow 2005
-- Modified by Don Stewart
--
import Data.Bits; import Data.Array.IO; import Data.Array.Base
import System; import IO; import Text.Printf
main = (\n -> mapM_ (sieve.(10000 *).shiftL 1) [n,n-1,n-2]) . read . head =<< getArgs
sieve m = do
arr <- newArray (0,m) False :: IO (IOUArray Int Bool)
let for i c
| c `seq` False = undefined -- strictness hack
| otherwise = if i > m then return c else do
x <- unsafeRead arr i
if x then for (i+1) c
else let for' j | j > m = for (i+1) (c+1)
| otherwise = unsafeWrite arr j True >> for' (j+i)
in for' (i*2)
r <- for 2 0
printf "Primes up to %8d %8d\n" (m::Int) (r::Int) :: IO ()
Fast 1 entry
Shorter, might be slightly faster too.
-- The Great Computer Language Shootout
-- http://shootout.alioth.debian.org/
-- Contributed by (c) Simon Marlow 2005
-- Modified by Don Stewart
import Data.Bits; import Data.Array.IO; import System; import IO; import Text.Printf
main = (\n -> mapM_ (sieve.(10000 *).shiftL 1) [n,n-1,n-2]) . read . head =<< getArgs
sieve m = do
arr <- newArray (0,m) False :: IO (IOUArray Int Bool)
let for i c
| c `seq` False = undefined -- strictness hack
| otherwise = if i > m then return c else do
x <- readArray arr i
if x then for (i+1) c
else let for' j | j > m = for (i+1) (c+1)
| otherwise = writeArray arr j True >> for' (j+i)
in for' (i*2)
r <- for 2 0
printf "Primes up to %8d %8d\n" (m::Int) (r::Int) :: IO ()
Original entry
{-# OPTIONS -O2 -optc-O3 #-}
-- The Great Computer Language Shootout
-- http://shootout.alioth.debian.org/
-- Contributed by (c) Simon Marlow 2005
import Data.Array.IO
import System
import IO
import Monad
import Data.Bits
import Text.Printf
main = do
as <- getArgs
case as of
[m] -> do let n = read m :: Int
test n
when (n >= 1) $ test (n-1)
when (n >= 2) $ test (n-2)
_ -> do hPutStrLn stderr "usage: nsieve-bits M"
exitWith (ExitFailure 1)
test :: Int -> IO ()
test n = do
let m = (1 `shiftL` n) * 10000
arr <- newArray (0,m) False :: IO (IOUArray Int Bool)
let for i count
| count `seq` False = undefined -- strictness hack
| i > m = return count
| otherwise = do
x <- readArray arr i
if x
then for (i+1) count
else let for' j | j > m = for (i+1) (count+1)
| otherwise = do
writeArray arr j True
for' (j + i)
in for' (i*2)
r <- for 2 0
printf "Primes up to %8d %8d\n" (m::Int) (r::Int)