30000! 빨리 계산하기 with Haskell
* 꼬리 재귀호출과 패턴 매칭을 이용하여 구현한 팩토리얼과 피보나치 수열 계산
Filename: fact.hs
Rapid factorial and fibonacci seq implementations
by pattern matching and tail recursive call
Compile: ghc fact.hs
Execute: main
Date: 2010/07/20
Author: phkim pkim (AT) scripts.pe.kr
-}
module Main where
factorial :: Integer -> Integer
factorial n = recfact 1 n
recfact :: Integer -> Integer -> Integer
recfact acc k = case k of
0 -> acc
k-> recfact (acc*k) (k - 1)
fib :: Integer -> Integer
fib n = fibGen 0 1 n
fibGen :: Integer -> Integer -> Integer -> Integer
fibGen a b n = case n of
0 -> a
n -> fibGen b (a + b) (n - 1)
main :: IO ()
main = do
print ("Factorial(30000) has " ++ show (length (show (factorial 30000))) ++ " digits")
print ("Fibonacci(200000) has " ++ show (length (show (fib 200000))) ++ " digits")
{-
Expected result:
"Factorial(30000) has 121288 digits"
"Fibonacci(200000) has 41798 digits"
-}