blob: e4e646b15d6a149624869b487972a4d3ddc9a52e (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
module AufgabeFFP2
where
-- 1
primes :: [Integer]
primes = sieve [2 ..]
-- sieve of eratosthenes (according to lecture slides)
sieve :: [Integer] -> [Integer]
sieve (x:xs) = x : sieve [ y | y <- xs, mod y x > 0]
-- generate all pairs with map and then filter only the valid ones
-- TODO: filtering should be optimized, still a bit slow
pps :: [(Integer, Integer)]
pps = filter validPair $ map (\x -> (x,x+2)) primes
where
-- pair is valid if the second component n is a prime
-- since simply checking if the Integer is element of the prime-list
-- does not terminate for non-primes, we take the first n primes
validPair :: (Integer,Integer) -> Bool
validPair (_,maybePrime) = elem maybePrime $ take (fromInteger maybePrime) primes
-------------------------------------------------------------------------------
-- 2
-- generates powers of 2
pof2s :: [Integer]
pof2s = [1] ++ (map (2*) pof2s)
pow :: Int -> Integer
pow 0 = 1
pow n = pow (n-1) + pow (n-1)
-- uses memtable for power-calculation
powFast :: Int -> Integer
powFast 0 = 1
powFast n = pof2s !! (n-1) + pof2s !! (n-1)
-------------------------------------------------------------------------------
-- 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)
-------------------------------------------------------------------------------
|
