1 | |
---|
2 | module Main where |
---|
3 | |
---|
4 | import Data.Word |
---|
5 | import Criterion.Main |
---|
6 | import Control.Parallel.Strategies |
---|
7 | import Data.Array.Repa.Index |
---|
8 | import qualified Data.Array.Repa as R |
---|
9 | import qualified Data.Vector.Unboxed as V |
---|
10 | |
---|
11 | |
---|
12 | collatzLen :: Word32 -> Word32 -> Word32 |
---|
13 | collatzLen c 1 = c |
---|
14 | collatzLen c n | n `mod` 2 == 0 = collatzLen (c+1) $ n `div` 2 |
---|
15 | | otherwise = collatzLen (c+1) $ 3*n+1 |
---|
16 | |
---|
17 | pmax :: Word32 -> Word32 -> Word32 |
---|
18 | pmax x n = x `max` collatzLen 1 n |
---|
19 | |
---|
20 | solveAll :: Int -> Int -> Word32 |
---|
21 | solveAll step n |
---|
22 | = foldl max 1 . parMap r0 solve $ zip steps (tail steps) |
---|
23 | where |
---|
24 | steps = [2, 2 + fromIntegral step .. fromIntegral n] |
---|
25 | solve (from, to) = foldl pmax 1 [from..to] |
---|
26 | |
---|
27 | |
---|
28 | -- Solutions |
---|
29 | -- --------- |
---|
30 | |
---|
31 | strat :: Int -> Word32 |
---|
32 | strat n = |
---|
33 | let p = 100 -- chunk size |
---|
34 | in solveAll (n `div` p) n |
---|
35 | |
---|
36 | repa :: Int -> Word32 |
---|
37 | repa n = R.foldAll max 1 |
---|
38 | . R.map (collatzLen 1) |
---|
39 | . R.fromVector (Z:.n-2) |
---|
40 | $ V.enumFromN 2 (n-2) |
---|
41 | |
---|
42 | |
---|
43 | -- Main |
---|
44 | -- ---- |
---|
45 | |
---|
46 | main :: IO () |
---|
47 | main = defaultMain |
---|
48 | [ bgroup "hailstone" [ bench "strat" $ nf strat 1000000 |
---|
49 | , bench "repa" $ nf repa 1000000 ] |
---|
50 | ] |
---|
51 | |
---|