From fd4a39f37e1e1604e589b89776fc15104b6029c3 Mon Sep 17 00:00:00 2001
From: Matthias Wisniowski <matthias.wisniowski@gmail.com>
Date: Sat, 24 Mar 2012 23:13:00 +0100
Subject: pps (1) and powFast (2) implemented

---
 AufgabeFFP2.hs | 41 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 41 insertions(+)
 create mode 100644 AufgabeFFP2.hs

diff --git a/AufgabeFFP2.hs b/AufgabeFFP2.hs
new file mode 100644
index 0000000..e66b7a8
--- /dev/null
+++ b/AufgabeFFP2.hs
@@ -0,0 +1,41 @@
+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)
+
+-------------------------------------------------------------------------------
\ No newline at end of file
-- 
cgit v1.2.3