[Shootout-list] Re: GHC Sieve

[Aaron Denney]

--Q68bSM7Ycu6FN28Q
Content-Type: text/plain; charset=iso-8859-1
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On 2004-10-13, Peter Hinely <phinely@hawaii.edu> wrote:
> Isaac Gouy wrote:
>> iirc someone already noticed that the GHC program only calculates the
>> primes once, rather than 1200 times :-)
>>
>> http://shootout.alioth.debian.org/bench/sieve/detail.php
>
> It looks like the GHC sieve entry hasn't been fixed yet.  Please
> someone
> submit a fix or disqualify it.

Attached.

I'd really like it if instead of trying to convince the compiler not to
do obvious optimizations, we could change the tests so that they don't
do stupid stuff like that.  Instead of calculating primes in 2..8192
N times, why not just calculate primes in 2..8192*N?

Rather than doing a the same matrix multiplication N times, why not
raise it to the Nth power (requiring the na=EFve way, rather than the
"smart" divide and conquer speedup, of course)?

--=20
Aaron Denney
-><-

--Q68bSM7Ycu6FN28Q
Content-Type: text/plain; charset=us-ascii
Content-Description: sieve.ghc.hs
Content-Disposition: attachment; filename="sieve.ghc.hs"

-- $Id: sieve.ghc.html,v 1.6 2004/10/03 00:44:58 bfulgham Exp $
-- http://www.bagley.org/~doug/shootout/
-- from Roland Dowdeswell
-- adjusted by Aaron Denney, borrowing strictness attempt 
-- from Malcom Wallace's matrix multiplication
module Main where

import System(getArgs)

main = getArgs >>= putStrLn . ("Count: "++) . show . mytest . read . headOr1
  where headOr1 x = if length x /= 1 then "1" else head x

-- Here we try to force it to recompute at each step.
mytest n = length $ strictlast $ map sieve $ replicate n ([2..8192])

strictlast [x] = x
strictlast (x:xs) | force x = strictlast xs
force [] = True
force (x:xs) = x `seq` force xs

-- we use Int rather than let Haskell default to Integer,
-- because we are trying to remain competetive with other
-- languages that do not do arbitrary precision math by
-- default...
sieve :: [Int] -> [Int]
sieve [] = []
sieve (h:t) = h : sieve [x| x<-t, x`mod`h /= 0]

--Q68bSM7Ycu6FN28Q--