星期一, 3月 08, 2010

Haskell Pratice - Prime

今日目標算是達成了,明天再繼續。原始想法很簡單,如何寫出一個 prime list ? 於是我就寫了第一版

prime :: Integer -> Bool
prime x 
    | x == 2 = True
    | otherwise = 
            isPrime [2..sq] x
            where sq = truncate (sqrt (fromIntegral x)) + 1

isPrime :: [Integer] -> Integer -> Bool
isPrime x y =
    case x of 
        [] -> False
        x:xs -> (y `mod` x == 0) || isPrime xs

makePrimeList :: [Integer] -> [Integer]
makePrimeList x =
    case x of
        [] -> [] 
        x:xs -> if prime x then  
                    [x] ++ makePrimeList xs
                else 
                    makePrimeList xs

其中的 where sq = truncate (sqrt (fromIntegral x)) + 1 是在 Josh Ko 的幫助下寫出來的,但是我得隔日再戰,我很明確的知道是轉型問題,但是並不是能夠完全說清楚為什麼要這樣做(他有說明,但是我得再看一下書)。

而且在這一版中的 isPrime 實在是太暴力了,其實可以用 map + and (or fold) 寫出來,並不一定要用 recursive 寫,所以我採用了另外一個寫法,即是檢查到 `mod` == 0 就停下來。

isPrime_2 :: Integer -> [Integer] -> Bool
isPrime_2 x y
    | x == 2 = True
    | otherwise =
        case y of
            [] -> True
            y:ys -> if y < sq then
                        if (x `mod` y == 0) then False
                        else isPrime_2 x ys
                    else True 
                    where sq = truncate (sqrt (fromIntegral x)) + 1

速度是明顯快上不少,但這版對我而言只剩最後一個問題,就是每呼叫一次 sq 就要算一次,我目前唯一想到的解法是,把 sq 也當成引數,於是我就寫成

isPrime_3 :: Integer -> [Integer] -> Bool
isPrime_3 x y 
    | x == 2 = True
    | otherwise =
        isPrime_3' x y (truncate (sqrt (fromIntegral x)) + 1)

isPrime_3' :: Integer -> [Integer] -> Integer -> Bool
isPrime_3' x y sq =
    case y of
        [] -> True
        y:ys -> if y < sq then
                    if (x `mod` y == 0) then False
                    else isPrime_3' x ys sq
                else True

最後,再寫一個 makePrimeList 的 code 就搞定了

makePrimeList :: Integer -> [Integer]
makePrimeList x = makePrimeList_2 [2..x] []

makePrimeList_2 :: [Integer] -> [Integer] -> [Integer]
makePrimeList_2 u v =
    case u of 
        [] -> []
        x:xs -> if isPrime_3 x v then
                    [x] ++ makePrimeList_2 xs (v++[x])
                else
                    makePrimeList_2 xs v

最後 run 一下成果

*Main> makePrimeList 100
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

其實還可以更快,但是就明天再來來,依現在的程度寫出的 code ,雖然普通,可是很開心。

---
本週目標:練習 Prime


馬上就打了自己的嘴吧,我試著嘗試產生 6n+1 6n+5 的 list 用以減少 prime 的檢查次數,於是很粗糙的寫了如下的 code

makeList :: Integer -> Integer -> Bool -> [Integer] -> [Integer]
makeList e c b x =
    if c < e then
        if b then
            makeList e (c+4) False (x ++ [c])
        else
            makeList e (c+2) True (x ++ [c])
    else
        x

然後將 makePrimeList 改成如下

makePrimeList :: Integer -> [Integer]
makePrimeList x = makePrimeList_2 ([2, 3] ++ makeList x 5 False []) []

結果速度反而慢到嚇人啊...Orz 完全不知道為什麼,看來要好好研究了 XD。

張貼留言