summary-week-3.md

Summary of Week 3 - Goldbach's Conjecture

• 總共有 7 位參與者
• 檢測質數的方法大同小異，但因為生成與檢驗的次序不同，造成執行速度極大的差異
• lazy evaluation 是個雙面刃：
  • 讓我們在 Haskell 可以用直覺且高效的方式去實作許多在其他語言看似不可能的方法（例如先將所有的質數枚舉出來）
  • 但同時也讓程式的 cost centre 非常難去分析
• 經過不科學 benchmark，小編挑出了跑得最快的前三名，在此各頒發 emoji 一枚 🎉🎉🎉
  1. Tai An Su 🥇
  2. 洪崇凱 🥈
  3. Yu-Ren Pan 🥉
• Goldbach's Conjecture 仍舊是個猜想

Solutions

1. 洪崇凱 🥈 https://gist.github.com/RedBug312/ca7d4dd1e9a8e22d82034f8c152347a4

• 利用質數 mod 6 一定會等於 1 或者 5 的性質，將輸入分成三種情形去加速檢測：
  1. 兩個質數都會落在 mod 6 == 1 的序列
  2. 兩個質數都會落在 mod 6 == 5 的序列
  3. 一個質數會落在 mod 6 == 1 的序列，而另一個落在 mod 6 == 5 的序列

-- Build prime number table would be much slower than performing prime tests,
-- since we check only x and n-x, and in most cases x < 10 (28.7% when n < 20000).

goldbach' :: Int -> Int -> Int -> [Int]
goldbach' n m1 m2 = filter (\x -> isPrime x && isPrime (n-x)) $ 3:5:[6+m1,12+m1..n-2]
    where isPrime x = null $ filter (\y -> x `mod` y == 0) [2..fsqrt x] -- expect x > 1
          fsqrt = floor.sqrt.fromIntegral

goldbach :: Int -> Maybe (Int, Int)
goldbach 4 = Just (2, 2) -- the only case 2 would showed up
goldbach n               -- expect n `elem` [4,6..]
    | null search = Nothing
    | otherwise   = let x = head search in Just (x, n - x)
    where search = case n `mod` 6 of 0 -> goldbach' n 1 5 -- (6k+1, 6k-1)
                                     2 -> goldbach' n 1 1 -- (6k+1, 6k+1)
                                     4 -> goldbach' n 5 5 -- (6k-1, 6k-1)
                                     otherwise -> []

-- main = print $ map goldbach [4,6..20000] -- takes 0.95 sec

2. 郭宗霆 https://gist.github.com/jc99kuo/339fd27d50ced55b19a062aa680b006b

• 先生成質數，再找出第一個湊起來剛好的組合

--  FLOLAC 2018 Week 3 -- Goldbach's conjecture

-- A simple, intuitive, straight fowward solution.
-- And may be not so efficient.  :-)   

goldbach :: Int -> Maybe (Int, Int)

goldbach nn
    | nn < 3  = Nothing
    | odd nn  = Nothing
    | otherwise =
        if null pairs
            then  Nothing
            else  Just $ head pairs
          where  
             pairs = [ (m,n) | m <- tryRange,
                               n <- tryRange,
                               (m + n) == nn ]
             tryRange = takeWhile (\x -> x < nn) primeList
             primeList = ppList [2 .. ]
             ppList (n : ns) = n : ppList (filter (\x -> (mod x n) /= 0 ) ns)

-- Thanks to the call-by-need lazy evaluation,
-- The efficiency is really not bad.  :-)

3. Wen-Shih Chao https://gist.github.com/yen3/3bd457b2be870a7ff8eb114285dff0a5#file-goldbach-hs

• 依序將輸入拆成兩個數字並且判斷他們是否都為質數

goldbach :: Int -> Maybe (Int, Int)
goldbach n = let ps = [(x, n-x) | x <- [2..(n `div` 2)], isPrime x, isPrime (n-x)]
             in safeFst ps
             where isPrime n = and (map (\x -> n `mod` x /= 0) [2..(n-1)])
                   safeFst [] = Nothing
                   safeFst (x:xs) = Just x

4. Tai An Su 🥇 https://gist.github.com/taiansu/138e32ee4464d3e28a8d1e9d501efdfa

• 先用基本的質數檢測生成一些質數（到輸入的一半），再依序看看輸入與質數的差是不是也是質數
• 看似簡單但卻是跑得最快的解法！

goldbach :: Int -> Maybe(Int, Int)
goldbach n = search halfOfPrimes where
  search [] = Nothing
  search (x:xs) = if isPrime (n - x) then Just (x,  n - x) else search xs
  halfOfPrimes = 2 : [ x | x <- [3, 5..half], isPrime x]
  half = div n 2

isPrime :: Int -> Bool
isPrime 2 = True
isPrime n = not $ any isFactor (2 : [3, 5 .. (square n)])
  where square = floor . sqrt . fromIntegral
        isFactor x = mod n x == 0

5. Shin-Cheng Mu https://gist.github.com/scmu/87335a044ecfe5143de83fa036b0f403

• 真・sieve of Eratosthenes！
• 對 List 做了許多資料結構上的操作

{-
   Richard Bird's quick algorithm for generating prime numbers.
   Note that the usual "one-liner" Haskell definition of the
   sieve is not an honest implementation of the sieve of Eratosthenes.
   The following algorithm by Bird is a more faithful implementation
   that is not asymptotically the best, but practically
   fast enough. Further more, we can reuse the "union" function.
   For more info see: Melissa E. O’Neill, The genuine sieve of
   Eratosthenes. Journal of Functional Programming 19(1), 2009.
-}

primes :: [Int]
primes = 2:([3..] `minus` composites)
  where composites = unionBy id [multiples p | p <- primes]
        multiples n = map (n*) [n..]
        (x:xs) `minus` (y:ys) | x < y  = x : (xs `minus` (y:ys))
                              | x == y = xs `minus` ys
                              | x > y  = (x:xs) `minus` ys

  -- merging sorted infinite lists of infinite lists.

unionBy :: Ord b => (a -> b) -> [[a]] -> [a]
unionBy f = foldr merge []
  where merge (x:xs) ys = x : merge' xs ys
        merge' (x:xs) (y:ys) | f x <  f y = x : merge' xs (y:ys)
                             | f x == f y = x : merge' xs ys
                             | f x >  f y = y : merge' (x:xs) ys

 -- the main function

goldbach :: Int -> Maybe (Int, Int)
goldbach n = check . head . dropWhile ((< n) . uncurry (+)) $ primepairs ()
  where check (p,q) | p + q == n = Just (p,q)
                    | otherwise  = Nothing
        -- all pairs of primes, sorted by their sums
        primepairs :: () -> [(Int, Int)]
        primepairs _ = unionBy (uncurry (+)) (primesMatrix primes)
          where primesMatrix (p:ps) = map (\q -> (p, q)) (p:ps) : primesMatrix ps

6. Yu-Ren Pan 🥉 https://gist.github.com/YuRen-tw/18e4e67431f48ba0d95cac00deca3fe5

• 做法和 Tai An Su 類似
• 但 listToMaybe 會叫 goldbachFull 把所有組合算出來，然後全部丟掉只留最後一組的樣子 XD

goldbach :: Int -> Maybe (Int, Int)
goldbach = listToMaybe . goldbachFull
    where listToMaybe = foldr (const . Just) Nothing

goldbachFull :: Int -> [(Int, Int)]
goldbachFull n = mkPairs . filter isNegPrime . takeHalfN $ primes
    where mkPairs = map (\p -> (p, n-p))
          isNegPrime p = isPrime (n - p)
          takeHalfN = takeWhile (\p -> p*2 <= n)

primes :: [Int]
primes = 2 : filter isPrime [3, 5 ..]

isPrime :: Int -> Bool
isPrime n | n <= 2    = n == 2
          | otherwise = all notDivisor . takeSqrtN $ primes
    where notDivisor p = mod n p /= 0
          takeSqrtN = takeWhile (\p -> p^2 <= n)

7. 張博凱 https://gist.github.com/zetavg/b03505c36a692d8bf8be14f48162098f

• 先用 sieve of Eratosthenes 生成質數
• 再找出第一個湊起來剛好的組合

sieve :: [Int] -> [Int]
sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

primes :: [Int]
primes = sieve [2..]

goldbachs :: Int -> [(Int, Int)]
goldbachs n = [(x, y) | x <- primesSmallerThenHalfOfN, y <- primesSmallerThenN, x < y, x + y == n]
  where primesSmallerThenHalfOfN = takeWhile (< n `div` 2) primes
        primesSmallerThenN = takeWhile (< n) primes

goldbach :: Int -> Maybe (Int, Int)
goldbach n = case take 1 $ goldbachs n of pair:_ -> Just(pair)
                                          otherwise -> Nothing