project euler #1

E1.hs

{-# LANGUAGE BangPatterns, MagicHash #-}
module Main where

import Criterion.Main
import GHC.Base
import GHC.Prim
import Criterion.Config
import Criterion.Main
import Data.Monoid
import qualified Criterion.MultiMap as M

{-
  If we list all the natural numbers below 10 that are multiples of 3 or 5, we
  get 3, 5, 6 and 9. The sum of these multiples is 23.

  Find the sum of all the multiples of 3 or 5 below 1000.

  http://projecteuler.net/index.php?section=problems&id=1

  cabal install criterion -fchart
  ghc --make E1.hs -O3 -fforce-recomp -funbox-strict-fields -fvia-C -optc-O3
 ./E1 -u e1.csv
  pdftk e1-sol*.pdf cat output e1.pdf
-}


myConfig =
  defaultConfig
    { cfgPerformGC    = Last (return True)
    , cfgPlot         = M.singleton KernelDensity (PDF 470 175)
--    , cfgPlotSameAxis = Last (return True)
    , cfgVerbosity    = Last (return Verbose)
    }

main :: IO ()
main = do
    let (r1:rs) = map (\f -> f n) [sol1, sol3, sol4, sol5, sol6, sol7, sol8]
    assert (all (== r1) rs) $
      defaultMainWith myConfig (return ())
        [ bgroup "e1"
            [ bench "sol1" (whnf sol1 n) -- :|
            , bench "sol2" (whnf sol2 n) -- :|
            , bench "sol3" (whnf sol3 n) -- :O
            , bench "sol4" (whnf sol4 n) -- :(
            , bench "sol5" (whnf sol5 n) -- :(
            , bench "sol6" (whnf sol6 n) -- :(
            , bench "sol7" (whnf sol7 n) -- :)
            , bench "sol8" (whnf sol8 n) -- :^)=
            ]
        ]
  where
    n = 100000


sol1 :: Int -> Int
sol1 n =
    a+b-c
  where
    !a = sum [3,6..end]
    !b = sum [5,10..end]
    !c = sum [15,30..end]
    !end = pred n

sol2 :: Int -> Int
sol2 n =
    a+b
  where
    !a = sum [3,6..end]
    !b = sum [x | x <- [5,10..end], x `mod` 3 /= 0]
    !end = pred n

sol3 :: Int -> Int
sol3 n =
    sum [ x | x <- [3..end], x `mod` 3 == 0 || x `mod` 5 == 0 ]
  where
    !end = pred n

sol4 :: Int -> Int
sol4 n =
    f 3 + f 5 - f 15
  where
    f s = g 0 s
      where
        g !a !c
          | c >= n    = a
          | otherwise = g (a+c) (c+s)

sol5 :: Int -> Int
sol5 n =
    f + h
  where
    !f = let g !a !c = if c >= n then a else g (a+c) (c+3)
         in  g 0 3
    !h = let i !a !c = if c >= n then a else j (a+c) (c+5)
             j !a !c = if c >= n then a else k (a+c) (c+5)
             k !a !c = if c >= n then a else i a     (c+5)
         in i 0 5

sol6 :: Int -> Int
sol6 (I# n) =
    I# (f +# h)
  where
    !f = let g a c = if c >=# n then a else g (a+#c) (c+#3#)
         in  g 0# 3#
    !h = let i a c = if c >=# n then a else j (a+#c) (c+#5#)
             j a c = if c >=# n then a else k (a+#c) (c+#5#)
             k a c = if c >=# n then a else i a      (c+#5#)
         in  i 0# 5#

sol7 :: Int -> Int
sol7 n =
    sumOneToNStep 3 + sumOneToNStep 5 - sumOneToNStep 15
  where
    sumOneToNStep !x = x * sumOneTo (end `div` x)
    sumOneTo !x = (x*(x+1)) `div` 2
    !end = pred n

sol8 :: Int -> Int
sol8 (I# n) =
    I# (sumOneToNStep 3# +# sumOneToNStep 5# -# sumOneToNStep 15#)
  where
    sumOneToNStep :: Int# -> Int#
    sumOneToNStep x = x *# sumOneTo ((n -# 1#) `divInt#` x)
    sumOneTo :: Int# -> Int#
    sumOneTo x = (x *# (x +# 1#)) `divInt#` 2#

e1.pdf