Parallelität in fkt.alen Spr., SS 06^{∗}

Jost Berthold

Aufgabe 2.2

Es ist ein Hauptprogramm zu schreiben, das als Parameter eine Zahl akzeptiert und etwas damit berechnet. Parameter bekommt man mit getArgs :: IO [String], die Funktion read :: String -> a konvertiert in den passenden Typ, hier Int. Fehlt: Fehlerbehandlung, falls kein Parameter vorhanden.

                                compiled code
import System
import List
main = do args <- getArgs
          let
            n = read (args!!0)
          putStrLn ("Sequenzielle Summe: " ++ (show (summePhi n)))
          putStrLn ("Mit Primzahlen:" ++ (show (summePhiO n)))

Berechnung

Zu berechnen: Summe der Werte φ(k) für k ∈ {1..n}.

                                compiled code
summePhi :: Int -> Int
summePhi n = sum ( map phi [1..n])
phi :: Int -> Int
phi n = length (filter (relprime n) [1..(n-1)])
hcf     :: Int -> Int -> Int
hcf x 0 = x
hcf x y = hcf y (rem x y)
relprime     :: Int -> Int -> Bool
relprime x y = hcf x y == 1

∗Dieses Programm ist in “literate-Haskell” geschrieben, daher die Dateiendung lhs. Der Quell-

text lässt sich sowohl mit L^{A}TEX setzen, als auch mit ghc compilieren.

… oder mit etwas Mathematik …

Quelle: de.wikipedia.org/wiki/Eulersche_%CF%86-Funktion

Falls p Primzahl ist, gilt φ(p) = p − 1.

Falls p und q teilerfremd sind, ist φ multiplikativ:

φ(p · q) = φ(p) · φ(q), falls ggt(p, q) = 1

Ferner: p^{k} ist teilerfremd zu allen kleineren Zahlen, die nicht Vielfache von p sind. Vielfache von p kleiner als p^{k} sind gerade {1 · p, 2 · p, 3 · p, …, (p^{k−1} − 1) · p}. Folglich gilt

φ(p^{k}) = (p − 1)p^{k−1}

Sei n ∈ ℕ beliebig, und die Primfaktorzerlegung für n sei p_{1}^{k_{1}} · ... · p_{m}^{k_{m}}.

Dann ist φ(n) = ∑_{j=1}^{m}((p_{j} − 1) · p_{k}^{k_{j}−1})

                                compiled code
summePhiO n = sum (map phiOpt [1..n])
phiOpt :: Int -> Int
phiOpt n = foldl (*) 1  [ (p-1)*p^(k-1)
                          | (p,k) <- primefactors n ]
primefactors :: Int -> [(Int,Int)]
primefactors n | n <= 1    = []
               | otherwise = primeList (primesIn primes n)
primeList :: [Int] -> [(Int,Int)]
primeList ps = [ (x, length (filter (==x) ps))
                 | x <- nub ps ] -- List::nub: Duplikate aus Liste entfernen
primesIn :: [Int] -> Int -> [Int]
primesIn [] _= error "no primes left!"
primesIn ps@(p:rest) n | p > n          = []
                       | n `mod` p == 0 = p:primesIn ps (n `div` p)
                       | otherwise      = primesIn rest n
-- Primzahlen, siehe Vorlesung:
primes :: [Int]
primes = sieve [2..]
sieve :: [Int] -> [Int]
sieve [] = []
sieve (x:xs) = x: (sieve (filter (not . multiple) xs))
    where multiple y = rem y x == 0