From 12ad8b53c5be7e22975082baa715e96aa2f1b9dd Mon Sep 17 00:00:00 2001 From: Matthias Wisniowski Date: Sun, 25 Mar 2012 19:04:12 +0200 Subject: First implementation for 2.3 hFast and hSlow diverge in values, reason unknown. e.g. consider >> map (\x -> hFast x x) [1..15] << (similar for hSlow) hSlow has the wrong values after 10. --- AufgabeFFP2.hs | 38 +++++++++++++++++++++++++++++++++++++- 1 file changed, 37 insertions(+), 1 deletion(-) diff --git a/AufgabeFFP2.hs b/AufgabeFFP2.hs index e66b7a8..e4e646b 100644 --- a/AufgabeFFP2.hs +++ b/AufgabeFFP2.hs @@ -38,4 +38,40 @@ powFast :: Int -> Integer powFast 0 = 1 powFast n = pof2s !! (n-1) + pof2s !! (n-1) -------------------------------------------------------------------------------- \ No newline at end of file +------------------------------------------------------------------------------- + +-- 3 + +-- power series of N +pofNs :: Integer -> [Integer] +pofNs n = [1] ++ (map (n*) $ pofNs n) + +-- faculty function +fac :: Integer -> Integer +fac n = product [1..n] + +-- stream of faculties +facGen :: [Integer] +facGen = map (fac) [1..] + +-- function g with memoization (using hFast) +fMT :: Int -> Int -> Float +fMT z k = g z k hFast + +-- function g without memoization (uning hSlow) +f :: Int -> Int -> Float +f z k = g z k hSlow + +-- actual function g +g :: Int -> Int -> (Int -> Int -> Float) -> Float +g z k h = sum $ map (h z) [1..k] + +-- helper function h using mem-table for the power-series (z^i) and for faculty (i!) +hFast :: Int -> Int -> Float +hFast z i = (fromInteger $ pofNs (fromIntegral z) !! i) / (fromInteger $ facGen !! (i-1)) + +-- helper function h without memoization +hSlow :: Int -> Int -> Float +hSlow z i = (fromIntegral $ z^i) / (fromInteger $ fac $ fromIntegral i) + +------------------------------------------------------------------------------- -- cgit v1.2.3 From d01a91022cc55841cf968a60ecee8f27b57b88e2 Mon Sep 17 00:00:00 2001 From: Matthias Wisniowski Date: Sun, 25 Mar 2012 19:42:13 +0200 Subject: 2.4 implemented 2.3 still to be fixed. --- AufgabeFFP2.hs | 19 +++++++++++++++++++ 1 file changed, 19 insertions(+) diff --git a/AufgabeFFP2.hs b/AufgabeFFP2.hs index e4e646b..9e466b7 100644 --- a/AufgabeFFP2.hs +++ b/AufgabeFFP2.hs @@ -75,3 +75,22 @@ hSlow :: Int -> Int -> Float hSlow z i = (fromIntegral $ z^i) / (fromInteger $ fac $ fromIntegral i) ------------------------------------------------------------------------------- + +-- 4 + +-- gets the digits of an integer as a list +digits :: Integer -> [Integer] +digits x + | x<=0 = [] + | otherwise = (digits $ x `div` 10)++[x `mod` 10] + +-- calculates the goedel-number for the given integer +-- returns 0 for non-positive numbers +gz :: Integer -> Integer +gz n + | n<=0 = 0 + | otherwise = product $ zipWith (^) primes (digits n) + +-- goedel-number generator +gzs :: [Integer] +gzs = map (gz) [1..] -- cgit v1.2.3 From 8613f7154f815835fc5e6ddbe15e9aebc62109b1 Mon Sep 17 00:00:00 2001 From: Matthias Wisniowski Date: Mon, 26 Mar 2012 00:15:48 +0200 Subject: Fixed different values for h-function Using Integer instead of Int solved the difference in values for the different h-functions. Apparently they have equal performance. Added basic testcases. --- AufgabeFFP2.hs | 18 +++++++------- TestAufgabeFFP2.hs | 69 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 78 insertions(+), 9 deletions(-) create mode 100644 TestAufgabeFFP2.hs diff --git a/AufgabeFFP2.hs b/AufgabeFFP2.hs index 9e466b7..7993c01 100644 --- a/AufgabeFFP2.hs +++ b/AufgabeFFP2.hs @@ -56,23 +56,23 @@ facGen = map (fac) [1..] -- function g with memoization (using hFast) fMT :: Int -> Int -> Float -fMT z k = g z k hFast +fMT z k = g z k hMT -- function g without memoization (uning hSlow) f :: Int -> Int -> Float -f z k = g z k hSlow +f z k = g z k h --- actual function g -g :: Int -> Int -> (Int -> Int -> Float) -> Float -g z k h = sum $ map (h z) [1..k] +-- actual function g (converts Int to Integer for more precision) +g :: Int -> Int -> (Integer -> Integer -> Float) -> Float +g z k h = sum $ map (h $ fromIntegral z) [1..(fromIntegral k)] -- helper function h using mem-table for the power-series (z^i) and for faculty (i!) -hFast :: Int -> Int -> Float -hFast z i = (fromInteger $ pofNs (fromIntegral z) !! i) / (fromInteger $ facGen !! (i-1)) +hMT :: Integer -> Integer -> Float +hMT z i = (fromInteger $ pofNs z !! (fromInteger i)) / (fromInteger $ facGen !! ((fromIntegral i)-1)) -- helper function h without memoization -hSlow :: Int -> Int -> Float -hSlow z i = (fromIntegral $ z^i) / (fromInteger $ fac $ fromIntegral i) +h :: Integer -> Integer -> Float +h z i = (fromInteger $ z^i) / (fromInteger $ fac i) ------------------------------------------------------------------------------- diff --git a/TestAufgabeFFP2.hs b/TestAufgabeFFP2.hs new file mode 100644 index 0000000..0df8612 --- /dev/null +++ b/TestAufgabeFFP2.hs @@ -0,0 +1,69 @@ +module Main where + +import Test.HUnit +import Control.Monad +import AufgabeFFP2 + +assertBoolF :: String -> Bool -> Assertion +assertBoolF msg b = when b (assertFailure msg) + +------------------------------------------------------------------------------- +-- 1 + +pps1 :: Test +pps1 = TestCase (assertEqual "pps" + [(3,5),(5,7),(11,13),(17,19),(29,31),(41,43), (59,61),(71,73),(101,103),(107,109)] + (take 10 pps)) + +pps2 :: Test +pps2 = TestCase (assertEqual "pps" + (347,349) + (pps!!20)) + +pps3 :: Test +pps3 = TestCase (assertEqual "pps" + (809,811) + (head (drop 30 pps))) + +ppsTests = TestList [pps1, pps2, pps3] + +------------------------------------------------------------------------------- +-- 2 + +------------------------------------------------------------------------------- +-- 3 + +------------------------------------------------------------------------------- +-- 4 + +gz1 :: Test +gz1 = TestCase (assertEqual "gz" + 144 + (gz 42)) + +gz2 :: Test +gz2 = TestCase (assertEqual "gz" + 400 + (gz 402)) + +gzs1 :: Test +gzs1 = TestCase (assertEqual "gzs" + 144 + (gzs!!41)) + +gzs2 :: Test +gzs2 = TestCase (assertEqual "gzs" + 400 + (gzs!!401)) + + +gzTests = TestList [gz1, gz2, gzs1, gzs2] + +------------------------------------------------------------------------------- + +tests :: [Test] +tests = [ppsTests, gzTests] + +main = do + forM tests $ \test -> + runTestTT test -- cgit v1.2.3