Skip to content

Instantly share code, notes, and snippets.

@banacorn

banacorn/summary-week-3.md

Last active May 18, 2018
Embed
What would you like to do?

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
  1. 郭宗霆 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.  :-)
  1. 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
  1. 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
  1. 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
  1. 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)
  1. 張博凱 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment