{{ message }}

Instantly share code, notes, and snippets.

# banacorn/summary-week-3.md

Last active May 18, 2018

# Summary of Week 3 - Goldbach's Conjecture

• 總共有 7 位參與者
• 檢測質數的方法大同小異，但因為生成與檢驗的次序不同，造成執行速度極大的差異
• lazy evaluation 是個雙面刃：
• 但同時也讓程式的 cost centre 非常難去分析
• 經過不科學 benchmark，小編挑出了跑得最快的前三名，在此各頒發 emoji 一枚 🎉🎉🎉
1. Tai An Su 🥇
2. 洪崇凱 🥈
3. Yu-Ren Pan 🥉
• Goldbach's Conjecture 仍舊是個猜想

## Solutions

• 利用質數 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```
• 先生成質數，再找出第一個湊起來剛好的組合
```--  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
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.  :-)```
• 依序將輸入拆成兩個數字並且判斷他們是否都為質數
```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```
• 先用基本的質數檢測生成一些質數（到輸入的一半），再依序看看輸入與質數的差是不是也是質數
• 看似簡單但卻是跑得最快的解法！
```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```
• 真・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.
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```
• 做法和 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)```
• 先用 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```